Home › AKTU PYQ › Theory of Automata and Formal Languages › Important Questions › Unit 4

Theory of Automata and Formal Languages Unit 4 – Push Down Automata and Properties of Context Free Languages: important questions for AKTU

Unit 4 (Push Down Automata and Properties of Context Free Languages) questions that AKTU repeats most often. This unit carries about 23 marks per paper. Start with the repeated questions, then the most asked topics.

Most repeated Unit 4 questions

  • Design a PDA that accepts the language L = {ww^R | w ∈ {a, b}*}. (7 marks, 2025, Nondeterministic Pushdown Automata) – also asked in 2018, 2019, 2022, 2023
  • Construct PDA equivalent to the following CFG G = ({S, A}, {0,1}, P, S} where P is defined by: S → 0S1 | A, A → 1A0 | S | ε (7 marks, 2024, PDA and CFG Interconversion) – also asked in 2018, 2022, 2023
  • Find the equivalent CFG of the following PDA P = ({q0, q1}, {a, b}, {a, z0}, δ, q0, z0) where δ is given by: δ(q0,a,z0)=(q0,az0), δ(q0,a,a)=(q1,aa), δ(q1,a,a)=(q1,ε), δ(q1,ε,z0)=(q1,ε) (7 marks, 2024, PDA and CFG Interconversion) – also asked in 2018, 2019, 2023

Most important Unit 4 topic

  • Nondeterministic Pushdown Automata (Unit 4: Push Down Automata and Properties of Context Free Languages) – asked 8 times in 2018, 2019, 2022, 2023, 2025

Most asked Unit 4 topics

  • Nondeterministic Pushdown Automata – asked 8 times
  • PDA and CFG Interconversion – asked 6 times
  • Two Stack Pushdown Automata – asked 4 times

More Unit 4 previous year questions

  • Design a PDA to accept palindromes over {a, b}. (7 marks, 2025, Nondeterministic Pushdown Automata)
  • Explain the concept of two stack PDA. Give an example of a language that is accepted by two stack PDA but not accepted by normal one stack PDA. (2 marks, 2024, Two Stack Pushdown Automata)
  • Differentiate between DPDA and NPDA. Construct a PDA that accepts language L = {aⁿbⁿ | n ≥ 1}. (7 marks, 2024, Deterministic Pushdown Automata)
  • Explain pumping lemma for context free language. (2 marks, 2023, Pumping Lemma for CFL)
  • Draw the graphical representation for PDA. (2 marks, 2023, Nondeterministic Pushdown Automata)

Unit 4 syllabus topics

  • Nondeterministic Pushdown Automata
  • Deterministic Pushdown Automata
  • PDA and CFG Interconversion
  • Two Stack Pushdown Automata
  • Pumping Lemma for CFL
  • Properties of Context Free Languages