Pda and transition function


Question: Let M be the PDA with states Q = {q0, q1, and q2}, final states F = {q1, q2} and transition function:
 
δ(q0, a, λ) = {[q0, A]}
δ(q0, λ , λ) = {[q1, λ]}
δ(q0, b, A) = {[q2, λ ]}
δ(q1, λ , A) = {[q1, λ ]}
δ(q2, b, A) = {[q2, λ ]}
δ(q2, λ , A) = {[q2, λ ]}

a) Draw the state diagram for M.
b) Using set notation, describe the language accepted by M.
c) Trade a computation of the word aaaabb.

Question: Construct a grammar G such that L(G) = L(M) where M is the PDA in the previous question. Then show that the word aaaabb is generated by G.

Question: Prove, using the Pumping Lemma for Context-Free Languages, that the language L = {ak | k is a perfect square} is not context-free.

Question
: Consider the language L = {ak bk | k > 0}. Explain whether this language is context-free, context-sensitive, recursive, recursively, enumerable, and/or regular. While formal proofs are not required, justify your assertions.

Question: Construct a one-tape Turing machine M that accepts the language L of the previous question.

Question: Construct a two-tape Turing machine M that accepts the language L of the previous question. Discuss the relative time complexity (number of Turing machine transitions) between your answer to this question and the previous one.

Question
: Design an Unrestricted Grammar G such that L(G) = {am bn am bn | m, n ≥ 0}.

Request for Solution File

Ask an Expert for Answer!!
Theory of Computation: Pda and transition function
Reference No:- TGS0266

Expected delivery within 24 Hours