Question
01:
Note
that L(A) ≠ L(B) if either
1.
there is an x Î L(A) Ç L(B)
2.
there is an x Î L(B) Ç L(A)
In
short if (L(A) Ç
L(B)) È (L(B) Ç L(A)) = Ǿ then L(A) = L(B)
Now,
we know that the following properties of regular languages.
1. If
P is regular and Q is regular then P È Q is regular. Furthermore,
given two DFAs D1
and D2 we can construct a DFA such
that D such that L(D) = L(D1) È L(D2).
2. If
P is regular then P is regular. Furthermore, given a DFA D‟ we can construct a DFA
D0 such that L(D‟) = L(D).
Hence
we can make a DFA C such that: L(C) = (L(A) Ç L (B)) È (L(B) Ç
L (A)) = Ǿ
1. On
input <A, B>
2.
Construct the DFA C described above.
3. If L(C) = Ǿ accept. Else reject.
Question
02:
Turing
Machine
A Turing machine has a input tape which is infinite.
Hence, the machine has unlimited memory. It has a read/write tape head which
can move left and write and change symbols while the machine is performing its
computation. The tape initially is blank everywhere. We write an input on the
tape and turn the machine on by putting it in a start state. The machine starts
a computation and (may) eventually produces an output. The output can be either
accept or reject. The machine produces by going into designated two designated
states.
Formally
a Turing machine M is a 7tuple, (Q, Σ, Г,d , q0, qa, qr ), where Q, Σ, Г are all
finite
sets.
1. Q
is the set of states.
2. Σ
is the input alphabet not containing the special blank symbol _.
3. Г
is the tape or work alphabet. Σ Í
Г and □ Î
Г
4. q0 is the start state.
5. qa is the accept state.
6. qr is the reject state.
7. d : Q × Г → Q × Г × {L,R} is the transition function.
Let us
discuss these one by one.
1. The
tape is initially empty. The user can write an input only using symbols of the
input
alphabet
Σ on the tape. The rest of the tape is left blank. Hence Ï Σ. Which means
cannot
be a part of the input. Therefore, when the machine reads the first blank it
knows
that
the input has ended.
2. Q
is the set of states that the machine can be in.3
3. Г
is the set of symbols that the machine is allowed to write on the input tape.
It can write
a
blank or any other symbol.
4. q0 is the start state of the
machine. Each time the machine performs a computation it
starts
from the start state.
5. qa is the accept state,
machine enters qa it declares that it has accepted the input.
6. qr is the reject state,
machine enters qr it declares that it has rejected the input.
7. d is the transition function. It describes how
the machine will perform its computation.
Question
03:
The Acceptance Problem for DFAs:
You must have studied DFAs in your previous automata course. DFAs are
simple machines with a read only head. Let us look at the following problem:
ADFA = {<B, w> : B is a DFA that accepts the input
string w}.
The input of this problem consists of two parts. The first part is going
to be a description of a deterministic finite automata B. The second part is
going to be a string w. We have to decide if the DFA B accepts the string w.
Note that the input will not be a DFA B but a suitable encoding of B.
Let us look at the following picture which shows two DFAs:
In this case:
We want to show ADFA is decidable.
The question that we want to ask is: Is ADFA decidable? Lets
ponder on this question for a bit.
We are asking if we can make an algorithm (Turing machine) that will
take as input a description of a DFA B and a string w{0, 1}* and tell us if B
accepts w?
The answer is yes. We can devise such an Turing machine. Since, aTuring
machine can “simulate the behavior of a DFA.”Here is a highlevel description
of such a Turing machine MD.
1. On input
<B, w>
2. Simulate B
on w.
3. If B reaches an accepting state then accept. If it reaches a
rejecting state then reject.
Question
04:
Show that the Post Correspondence Problem (PCP) is decidable over unary
alphabet.
Answer:
The Post Correspondence Problem (PCP) is
decidable over unary alphabet. We can describe a Turning Machine M that decides
unary PCP.
Given
unary PCP instance
Let
us design a TM M as given below:
M
= “On Input<a_{1}b_{1},………,a_{n}b_{n}>”
 Check if a_{i }=b_{i} for some i. if
so, accept.
 Check if
there exist i=j such that a_{i} >b_{i} and a_{i} <b_{i}. If so, accept otherwise reject.
Question
05: Prove
that every t(n)time ktape TM has on equivalent O(t^{2}(n))time single tape TM.
Answer:
Given
a ktape TM M, we can make 1tape TM N. N works as follows:
 On input x,
convert input x to #q0#x#, …. #(the start configuration of M). This
configuration says that x is on the first tape. The rest of the tape is
empty and the machine is in q0.
 In each
pass over the tape, change the current configuration to the next one.
 If an
accepting configuration is reached, accept.
 If a
rejecting configuration is reached, Reject.
Now
we have to estimate, how much time does N require?
On
any input x of length n, we make the following claims:
 M uses at
most t(n) cells of its ktape.
 Each
configuration has length at most k t(n) = O(t(n)).
 Each pass
of N requires at most O(t(n)) steps.
 N makes at
most t(n) passes on its tape.
This
shows that N run in time O(t(n)×t(n))=O(t^{2}(n)). Here, we use the fact t(n)≥n.
Thus, the machine convert x to the initial
configuration. This takes time O(n). So total time is given below:
O(n)+O(t^{2}(n))=O(t^{2}(n))
Question
06: Show
that A_{TM }is not mapping reducible to E_{TM.}
Answer:
Recall
that A_{TM }is undecidable, but it is recognizable so its complementis not recognizable. Note that the
complement of E_{TM }is recognizable, and so since we know E_{TM} is undecidable, It is
also not recognizable.
Proof: We give a
proof by contradiction.
Assume, it is false that A_{TM} is not mapping reducible to E_{TM},
So A_{TM} ≤_{m} E_{TM}.
Question 07:
Which of the following pair of numbers are relatively prime? Show the
calculations that lead to your conclusions. A) 1274 & 10505 B) 7289 & 8029
Answer:
A)
For checking the given
number 1274 & 10505 that they are relatively prime or not we use Euclidean
algorithm to find Greatest Common Divisor (GCD).
The
greatest common divisor of 105050 and 1274 is 1. There for they are relatively
prime.
B)
For checking the given number 7289 & 8029 that
they are relatively prime or not we use Euclidean algorithm to find Greatest
Common Divisor (GCD).
The
greatest common divisor of 7289 & 8029 is 37. There for they are not relatively
prime.
Question
08: G is a digraph and show that PATH is in
Class P. OR Design a polynomial time algorithm that takes as input a graph G
and two vertices s and t and decides if there is a path from s to t.
Answer:
We
have to give a polynomial time algorithm for this problem. That is “Start BFS
or DFS from s and if t appears then there is a path from s to t”.
Algorithm:
I.
On input <G,s,t> where G is a
digraph,
II.
Mark s.
III.
Repeat till no additional nodes are
marked:
IV.
Scan the edges of G, if an edge (a,b) is
found going from a, marked node a to an unmarked node b, mark b.
V.
If t is marked, accept, otherwise
reject.
Now
we have to compute the size of input. We know that input size is at least m,
where m is the number of nodes in G. Thus we have to show that algorithm runs
in the time polynomial in m.
The
repeat loop can at most run for m time. Each time all the edges are scanned.
Since the number of edges is al most m^{2}, thus step 2 takes at most m^{2
}time. So the total time is at most m^{3}. Hence, we have shown
that PATH is in p.
Question
09:
A Turning Machine with stay put instead of left is similar to an ordinary
turning machine, but the transition function has the form: . At each point the machine can move its head right or left
it stay in the same position.
Show
that this turning machine variant in not equivalent to the usual version. What
class of language does this machine recognize?
Answer:
Remembering
what it has written on the tap cells to the left of the current head position
is unnecessary, because the TM is unable to return to these cells and read them.
Using
NFA in the actual construction is convenient because it allows E moves which
are useful for simulating the “Stay Put” TM Transition.
The
transition function for the NFA is
constructed according.
 First, we
set ,
where q_{0} is the start state of the TM variant.
 Next, we
set for any i.
 If where w=R or S,
we set .
 If where w=R or S,
we set .
Question
10:
Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. We describe
the functions f: X  Y and g: X Y in the following tables.
N

F(n)

1

6

2

7

3

6

4

7

5

6

N

G(n)

1

10

2

9

3

8

4

7

5

6

a. Is f onetoone? b. Is f onto? c. Is f a correspondence?
d.
Is g onetoone? e. Is g
onto? f. Is g a correspondence?
A)
f is not onetoone because f(1)=f(3) on
the other hand g is onetoone.
B)
f is not onto because there does not
exist x belongs to X such that f(x)=10. But g is onto.
C)
g is a correspondence because g is
onetoone and onto. f is not correspondence because f is not onetoone and
onto.
Question 11: Show
that MPCP is undecidable.
Answer:
Assume that MPCP
is decidable. Let us say we have a decider R for MPCP. Consider the following
decider S
1. On input <
M, w >
2. Construct , p
as described in the seven parts.
3. Run R on P‟.
4. If R accepts,
accept.
5. If R rejects,
reject.
Then
S is a decider for A_{TM}, which is a contradiction to the fact that A_{TM}
is undecidable.
Question
12:
show that the collection of Turningrecognizable language is closed under
operation of (i) Union (ii) Concatenation.
Answer:
I.
For any two turning recognizable
languages L1 and L2, let M1 and M2 be the TMs that recognizes the union of L1
and L2:
“On input w
Rum M1 and M2
alternatively on w step by step. If either accept, accept. If both halt and
reject, then reject”
If any of M1 and
M2 accepts w, M1 will accepts w since the accepting TM will come to its
accepting state after a finite number of steps. Note that if both M1 and M2
reject and either of them does so by looping, then TM will loop.
II.
Form any two Turningrecognizable
languages L1 and L2, let M1 and M2 are the TMs that recognize them. We
construct a NTM M’ that recognizes the concatenation of L1 and L2;
“On Input w;
1.
None deterministically cut w into two
parts w = w1w2.
2.
Run M1 on w1. If it halts and reject,
reject. If it accepts, go to stage 3.
3.
Run M2 on w2. If it accepts, accept. If
it halts and reject, reject.”
If there is a
way to cut w into two substrings such that M1 accepts the first part and M2
accepts the second part, w belongs to the concatenation of L1 and L2 and M1
will accept w after a finite number of steps.
Question 13: If A
≤m B and B is decidable, then A is decidable.
Answer:
Proof:
Since B is decidable hence there is a decider M that decides B.
Now, consider
the following decider N:
1. On input x
2. Compute y =
f(x)
3. Run M on y
4. If M accepts,
accept.
5. If M rejects,
reject.
Since f is a
computable function and M is a decider therefore N is a decider. Furthermore, x
is accepted by N if and only if y is accepted by M. However, y is accepted by M
if and only if .
Since f is a
reduction therefore, if
and only if . Which implies that N accepts x if and only if. This shows that N is a decider for A.
Question
14:
If
A ≤m B and B is Turning Recognizable, then A is Turning Recognizable.
Answer:
Let A ≤m B and let f be the reducibility from
A to B, Furthermore, since B is turning recognizable, there is a TM M such that
L(M)=B
Consider
N:
“On input x
1.
Computer y=f(x)
2.
Run M on y
3.
if M accepts, accept.”
Then
it is easy to see that L(N) = A.
Question
15:
let .show that T is countable.
Answer:
We
need to demonstrate a onetoone. Let. Function f is onetoone because. Therefore, T is countable.
Question
16: Let
A be a regular expression. Show that A is decidable.
Answer:
1. Proof is actually one line.
2. If we have a decider M that accepts
A.
3. We can switch the accept and reject
states to make another decider M‟.
4.
M‟ accepts. A
Lets recall that a language A is Turing recognizable if there is a
TM M such that L(M) = A.
Question
17:
Answer:
For
checking the given number “234 and 399” that they are relatively prime or not
we use Euclidean algorithm to find Greatest Common Divisor (GCD).
The
greatest common divisor of “234 and 399” is 3. There for they are not relatively
prime
Question
18:
Show that some true statement in TH(N, +, X) are
not provable
Answer:
Consider
the following algorithm:
1. On input Ф
2. Enumerate all possible proofs
3. Check if is a proof of Ф. If it is accept.
4.
Check if is a proof of ¬Ф. if it is reject.
If
all true statements are provable then since each statement is either true or
false hence Ф or ≠ Ф is provable. Thus the above algorithm will be a decider
for TH(N,+,×) . This is a contradiction as we have already proved that
TH(N,+,×) is not decidable.
Question 19: Show
that A<TB , B<TC, A< TC
Question 20: MIN_{TM}
is not TuringRecognizable.
Answer:
Two
facts about MIN_{TM}.
 1
MIN_{TM}
is infinite.
 2
MIN_{TM}
contains TM’s whose length is arbitrarily large.
If
MIN_{TM} is Turing Recognizable then there is a TM E that enumerates MIN_{TM}.
We will use E and the recursion theorem to construct another TM C.
On
input w
 2
Obtain
own description <C>.
 3
Run
E until a machine D appears with a longer description than that of C.
 4 Simulate D on input w.
All we have to
note that eventually D will appear as MIN_{TM}
contains TM with arbitrarily large descriptions. L(C) = L(D).
However, C has a
smaller description than D. So D cannot be in MIN_{TM}.
Question 21: A={<R>R is a regular expression describing a
language containing at least one
string w that has 111 as substring(i.e.w=x111y for some x,y } show A is decidable.
Answer:
The following TM
X decide A.
X = “On input where
R is regular Expression:
1. Construct DFA
E that accepts.
2. Construct DFA
B such that.
3. Run TM T on
input where T decides E_{DFA}.
4. If T accepts, reject. If T rejects, accept.”
Question
22: Consider
following instance of PCP. Is it possible to find a match? If yes then give
the dominos arrangements. If NO then
prove. 1/0. 101/1. 1/001 (5).
Answer:
We can give the number to instances as :
We have choice for start matching that
is pair B where 1 is at start from top and bottom so pair B is,
Form
pair B we can see that 1 is match in top and bottom string but 01 is left in
the upper so we need a pair whose
bottom string starts with 0. There are
twp pairs A and C.
OR We
can not use C because there will be a mismatch so use A.
After using B,A from upper 10 and bottom 10 is matched but 11 is left
from upper so we need a pair whose bottom string starts with 1. That is B.
Upper = 101 , Bottom =
101
After using B,A,B from upper 101 and bottom 101 is matched but 1101 is
left from upper so we need a pair whose bottom string starts with 1. That is B.
Upper = 1011 , Bottom
= 1011
After using B,A,B,B from upper 1011 and bottom 1011 is matched but 101101
is left from upper so we need a pair whose bottom string starts with 1. That is
B.
Upper = 10111 , Bottom
= 10111
After using B,A,B,B,B from upper 10111 and bottom 10111 is matched but
01101101 is left from upper so we need a pair whose bottom string starts with
0. That is A and C. If we use C there will a mismatch.
Upper = 1011101 , Bottom = 1011100
So we use A
Upper = 101110 ,
Bottom = 101110
After using B,A,B,B,B,A from upper 101110 and bottom 101110 is matched
but 11011011 is left from upper so we need a pair whose bottom string starts
with 1. That is B.
We observe that Upper Values are increasing,
we can not use C having bottom 001 because in upper there will not 00 in it.
So, it is not possible to find a match for this instance.
Question 23: In the silly Post Correspondence
Problem, SPCP, in each pair the top string has the same length as the bottom
string. Show that the SPCP is decidable. 10
Answer: The SPCP problem is decidable. It follows from
the following claim.
Claim: A
given SPCP instance has a match if and only if there is a domino such that
Proof of the
claim:
” ”: If a SPCP instance has a match it has to start
with some domino. Because the length of the top and the bottom string is the
same in all dominos, the first domino in the match must surely have the same
top and bottom string.
” ”: If there is a domino with the same top and bottom
string then this single domino forms a trivial match of SPCP.
Finally,
checking whether there is a domino with the same top and bottom string is
easily decidable by examining the SPCP instance.
Question 24:
Solution:
We can give the
number to instances as:
We have choice for start matching that
is pair C where 0 is at start from top and bottom so pair C is,
Form pair c we can see that 01 is match in top
and bottom string but 1 is left in the bottom so we need a pair whose upper string starts with 1 that is
pair A
Now 0110 string is match from top and bottom,0 is
left from bottom so we need a pair, who’s upper string starts with 0, there are
two choice either select pair B or C. Let’s first try with pair B,
It does not match, so let’s try pair C,
Again
we have a mismatch. There is no other pair left. So, it is not possible to find
a match for this instance.
Question 25:
Solution:
We
can give the number to instances as
Numbering
the instances as follows:
The
dominos arrangement which will gives the matching of top and bottom string is:
A,
B, A, A, B, C,
C
Now
if we note the top string that is 1001100100100
If we
note bottom string that is
1001100100100
Now
the matching is found so this list is called match.
Question 26:
Solution:
We
can give the number to instances as :
We have choice for start matching that is pair C
where 1 is at start from top and bottom so pair C is,
Form pair c we can see that 10 is match in top
and bottom string but 1 is left in the bottom so we need a pair whose upper string starts with 1 that is
pair D
Now 010 is left
from bottom and we need a string that is start from 0 at the top which is A
Now the matching
string is 10101, 0100 is left in the bottom , we need string with 0 from top
that is E
now matching string is
101010, 10010 is left in the bottom, so the best choice pair B
matching is 101010100,
100 is left from bottom
So choose pair B
again
now 0 is left from
bottom so choose pair E
now 10 s left from
bottom, choose pair B
So the matching
string is 1010101001000100
Theorem: ALLCFG is undecidable.
If
ALL_{CFG} is decidable then there is a decider R such that L(R) = ALL_{CFG}
Suppose
R decides ALL_{CFG} then consider S
1. On input <M, w>
2. Construct and LBA D as described
earlier.
3. Convert D into an equivalent CFG G.
4.
Run R on G. If R accepts reject. If R rejects accepts.
Note that S is a decider for
A TM. A contradiction.
Theorem:
HALT_{TM} is undecidable.
Suppose
that HALT_{TM} is decidable and R decides HALT_{TM}. If we have
R then we have no problem on TM that loop endlessly. We can always check if a
TM will loop endlessly on a given input using R. We can use R to make a decider
for ATM. We know that ATM is undecidable. We have a contradiction and that is
why R cannot exist.
Given
R we can construct S which decides ATM that operates as follows:
1. On input <M, w>
2. Run TM R on input <M, w>.
3. If R rejects, reject.
4. If R accepts, simulate M on w until
it halts.
5.
If M has accepted w, accept; if M has rejected w, reject.
Note that S will reject
<M, w> even if M loops on w.
No comments:
Post a Comment