Sipser 4.10 Show INFINITE is decidable.

Solution:

Turing machine INFINITE<PDA>:
On input <M>,
1. Convert given M to CFL using algorithm for converting PDA to CFL.
2. Run INFINITE<CFL> , If it accepts then accept, else if it rejects reject.

Daksh Parshan

Daksh Prashan (Questions) : Can you answer them.

1. If we limit length of tape of Turing Machine, what language exactly will it accept.

2. Language of pairs of CFGs descriptions, such that language of first grammar is equal to second. Sipser says it is not decidable.

But we can always convert two grammers in Chomsky Normal Form. And map every rule of first grammer with some suitable rule in second. We can think of this as follow:

1. Consider all terminals marked. Find one rule each from both grammars, having same RHS side. Now replace Non-terninal in second rule with non terminal of first. Replace it throughout the second grammar. 

     2. If we get some rule whose RHS have all non-terminals, that are replaced by non-terminals of first grammar, consider this rule to be checked for replacing non-terminal on LHS. 

3. Repeat until no further rule can be mapped. Check if both grammars are exactly equal. If yes then accept otherwise reject.

Sipser 3.19 Show that every infinite Turing- recognizable language has an infinite Turing-decidable subset.

Solution:
From last problem (sipser 3.18) : If we have an enumerator which enumerates a language in lexicographic order, then we can make a decider using it.

Now. given a Turing recognizable language L, R be Turing machine which recognizes it. Clearly we can make an enumerator E using R, which enumerates L. Not necessarily, it enumerates in lexicographic order. But we can always pick lexicographic subset from the enumerated set.

My new enumerator E<prime> will work as follow :

Run E, print newly generated string if it is max(lexicographically) in all generated strings till this point.

Otherwise reject it, And wait for next string to be generated by E.

And definitely this subset is Turing-decidable.

Sipser 3.18 show that a language is decidable iff some enumerator enumerates the language in lexicographic order.

Let D be decider for language. Now I will simulate an enumerator E using D.

Take all strings in lexicographic order and  run D on each one by one. If D accepts then print out this string otherwise skip to next string and run D on it.

Vice versa follows:
Let E be enumerator for given language which enumerates in lexicographic order. Make decider D using E as follow.

Run E, it will generate strings one by one in lexicographic order. Compare given string when every time E generates a new string. If matches then halt E, and consider D accepts the input string. Else if decider have generated a string which comes later than input string in lexicographic order, reject input string. Because E is enumerating language in Lexicographic order and all next coming strings will be those who fall after input string.

Sipser 3.13 : A Turing machine with stay put instead of left

Solution: Because head of TM can't move left, it will behave like a finite automata. Motion of head in right is equivalent to consuming next symbol, and staying at a place is equivalent to consuming an epsilon symbol. When we hit blank symbol check if last state was accept state of TM, if yes then our finite automata accepts. Otherwise automata will reject the input string.

Not giving a formal definition of this TM and finite automata, because it is quite easy to visualise. Comment if doubtful. 

Sipser Queue automaton vs Turing machine

Sipser 3.14

A queue automaton is like a push-down automaton except that the stack is replaced
by a queue. A queue is a tape allowing symbols to be written only on the left-hand
end and read only at the right-hand end. Each write operation (we'll call it a push)
adds a symbol to the left-hand end of the queue and each read operation (we'll
call it a pull) reads and removes a symbol at the right-hand end. As with a PDA,
the input is placed on a separate read-only input tape, and the head on the input
tape can move only from left to right. The input tape contains a cell with a blank
symbol following the input, so that the end of the input can be detected. A queue
automaton accepts its input by entering a special accept state at any time. Show that
a language can be recognized by a deterministic queue automaton iff the language
is Turing-recognizable.

Solution:
Turing machine can simulate a Queue Automaton easily. Consider whole tape as queue.
Pop operation of queue: alter a symbol and move to right. If more than one symbols are to be pushed
then do it by shifting the contents right and insert symbols. Once you hit end of tape, go to leftmost symbol of tape.

Now simulating Turing machine in a Queue automata.
Insert a left end marker say # first to queue. Then push all the symbols of tape in queue and finally a blank symbol. We are pushing symbols to the left and reading(popping) from right.
When ever this blank symbol is read and overwritten by some other symbol, push a blank symbol to queue before pushing overwritten symbol. For example : ABCDEF_ was the configuration of queue and T.M. write a G on place of _ . Then new configuration is G_ABCDEF.
Whenever a symbol is read and pushed back to queue, you push a symbol which will tell queue that next symbol to be read is actually last symbol read. e.g. -  
ABCDEF
F is read and overwritten by symbol say 'f' then insert last symbol read marker ( | ) before you push f.
f|ABCDE
Now I am reading symbol E and moving to left on T.M. tape then we will have to push 'e' on behalf of E and this is new 'last symbol read' . so new configuration should be e|f|ABCD . Now we have to remove marker before 'f' keeping in mind that next symbol to read is 'D'. Now roll whole queue. Insert $ i.e. next symbol to read marker.
D$e|f|ABC
CD$e|f|AB    rolled once.
roll until you get first '|' on rightmost of the queue.
ABCD$e|f|
remove this marker '|'.
ABCD$e|f
now roll until we reach to $
e|fABCD$
remove $.
e|fABCD

If T.M. wants to move to last symbol read. then roll until do e| and roll until first | is exposed to right side like below
e|f|ABCD
ABCDe|f|
remove rightmost |
ABCDe|f
now you are reading f as desired.

Sipser 3.9 Let a k-PDA be a pushdown automaton that has k stacks. Thus a 0-PDA is an NFA and 1-PDA is a conventional PDA. You already know that 1-PDAs are more powerful(recognize a larger class of languages) than 0-PDAs.

3.9 Let a k-PDA be a pushdown automaton that has k stacks. Thus a 0-PDA is an NFA and 1-PDA is a conventional PDA. You already know that 1-PDAs are more powerful(recognize a larger class of languages) than 0-PDAs.

a. Show that 2-PDAs are more powerful than 1-PDAs.

Solution:  Clearly, 2 PDA can do any thing which 1-PDA can. Now I will give a language which is accepted by 2-PDA not 1-PDA.  { w |w ∈ aⁿbⁿcⁿ } is one I want to consider. This is not A CFL and so not accepted by a 1-PDA. But if there are 2 stacks then do as follow:
Read input a^*b^*c^*
1. Initially PDA is in state q_accept. If an 'a' is read then push it in stack 1 and go to q₁. Else if read a 'b'        or 'c', go to q_reject and stay there for rest of input.
2.Being in state q₁ and reading input 'a', push it inside stack 1. Go to state q₂ if a 'b' is read and pop one 'a' from stack 1 and also push a 'b' on stack 2. If a 'c' is read then go to q_reject and stay there for rest of input.
3. Being in state q2 and reading input 'b', pop 'a' and push 'b' in stack 2. If a 'c' is read then go to state q3 and pop 'b' from stack 2. If no a is remaining on stack with 'b' still in hand, go to q_reject. Reject if 'a' is read again.
4. Being in state q3 and reading input 'c', pop 'b' from stack 2. Reject if 'a' or 'b' is read.
5. Accept if both of the stacks are empty otherwise reject.






b. Show that 3-PDAs are not more powerful than 2-PDAs.


Solution: 3-PDAs can do whatever 2-PDAs can do. With a 2-PDA, I can simulate a Turing Machine so anything solvable can be done by 2-PDAs as well.
                       
1. Put a input tape in stack 2 such that its left end is on top. Well if some one objects that input is read from left and so left most will be at bottom of stack, then I will suggest to put whole string in stack 1. And pop from stack 1, push the popped symbol into stack 2.  Finally we will get what we require.
2. The symbol at top of stack 2 is the currant symbol, TM is reading.
3. Suppose current symbol to be read is 'a' and TM will write here a 'b' and moves left, then we will pop 'a' from stack 2 and push 'b' into stack and further pop a symbol from stack1 to push it into stack 2.
4. If machine have made a right move then we would have poped 'a' from stack 2 and push 'b' in stack1.