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.