CS4384 Project 2 1) Using the techniques described in the online lectures and in the textbook, Convert the following PDA to a context free grammar and use the grammar you constructed to derive the...

It's the homework for my automata theory class!


CS4384 Project 2 1) Using the techniques described in the online lectures and in the textbook, Convert the following PDA to a context free grammar and use the grammar you constructed to derive the string caedbe. Do not add a production S → caedbe or similarly degenerate ways to derive the string. The whole point of showing how to derive the string is to demonstrate you understand how the grammar works. (10 points) 1 2 3 ε,ε→$ 4 ε,$→ε c,ε→x d,ε→y e,x→ε f,y→ε a,ε→x b,y→ε 2) Convert the following context free grammar to a PDA (10 points) S → SA | ε A → BxC | CyB B → zBz | x C → Cx | z Recall L4 from project 1: L4 = {w1#w2 | w1, w2 ∈ {0, 1}∗ and |w1| = |w2| and #0(w1) = #0(w2)} (That is, some number of bits, followed by #, followed by the same number of bits, and the number of 0 bits is the same in each of the two groups.) 3) Give an informal description of a Turing machine which accepts L4. (You don’t need to give an explicit state diagram). (10 points) Don’t forget the second page! 1 4) Give an informal description of a Turing machine which, given as input a Turing machine M , decides if M accepts the empty string within 100 steps. (You don’t need to give an explicit state diagram). (10 points) 5) Based on the halting problem being undecidable, Show that given a Turing machine M , it is undecidable if M eventually returns to its initial state when started with a blank tape. (10 points) 2