Homework SourseI need help on this question Please provide the solution wit
I need help on this question. Please provide the solution with explaination. Thank you!
Turing machines are definitely stronger than PDAs (why?). But it is interesting to investigate some restricted forms of TMs and see if the restrictions we apply could maintain the computing power of TMs. Here is an example. Consider a restricted TM M, called a one-turn Turing machine, such that during any executions on any input, M makes at most one turn on the tape (i.e., the tape head either always moves to the right, or moves to the left later but never moves to the right again. However, the tape head could stay at any moment.) Show (describe) that languages accepted by one-turn Turing machines are context-free.
Solution
Context Free languages (CFLs) are languages that are recognised by Context Free Grammars, i.e., grammars whose production rules are of the form N ->[N )*. They are also languages that are recognised by a type of machine called Pushdown automata. The type we considered in an earlier course were actually Nondeterministic PushDown Automata (NPDAs). We shall used this key information to show how languages recognised by Turing Machines relate to CFLs.
The relationship we will show is outlined on Slide 61, i.e., that there is a strict inclusion between CFL and recursive languages. In order to show this we have to demonstrate that
1. Every CFL can be decided by some Turing Machine.
2. There are recursive languages that are not CFL.
As in the case of Slide 60, in order to prove the second point above, we only need to find one witness language, which together with the first point above would mean that the set of Recursive languages is
Theorem:
Context Free Languages are strictly included in Recursive Languages.
LCFG Rec
Proof. Consider both inclusion relations:
CFG can be converted in Chomsky Normal Form where derivations for strings w are bounded by at most 2|w| - 1 steps.
The language {anbncn | n >= 0} is in LRec but not in LCFG.
