Consider the NPDA M = ({q0, q1, qf}, {a, b}, {1, z}, δ, q0, z, {qf}) with
δ(q0, λ, z) = {(qf, z)}
δ(q0, a, z) = {(q1, 11z)}
δ(q1, a, 1) = {(q1, 111)}
δ(q1, b, 1) = {(q1, λ)}
δ(q1, λ, z) = {(qf, z)}
Which language L is accepted by the NPDA?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. L = {anb2n : n ≥ 0}
Explanation
Each a pushes two 1's (11z on the first a, 1 → 111 afterwards) and each b pops one, so z is exposed again only after 2n b's. The λ-move from q0 also accepts the empty string: {anb2n : n ≥ 0}.More Theory of Computation and Compilers questions
- Consider two instances X and Y of the Post Correspondence Problem, each with lists A and B of three strings over {0, 1}. Which of the follo…
- Consider the following properties of recursively enumerable sets: (A) Finiteness (B) Context-freedom (C) Emptiness Which of the following i…
- Consider the grammar S → SbS | a and the string abababa. Consider the statements: the string has (A) two parse trees (B) two leftmost deriv…
- Match List I with List II. Choose the correct answer from the options given below:List I List II A. Type 0 I. Finite automata B. Type 1 II.…
- Consider the following statements: Statement I: An LALR parser is more powerful than a canonical LR parser. Statement II: An SLR parser is…
- Consider the following statements about context-free languages (CFL): Statement I: CFLs are closed under homomorphism. Statement II: CFLs a…