Theory of Automata and Formal Languages Unit 4 – Push Down Automata and Properties of Context Free Languages: AKTU previous year questions
23 AKTU questions from Unit 4 (Push Down Automata and Properties of Context Free Languages) asked in 2018–2025, tagged by marks, year and topic. In short: about 23 marks of every paper come from this unit; the most asked topic is Nondeterministic Pushdown Automata (8 times); 14 questions came back in a later year. The latest ones are listed below; on the page you can filter them by 2-mark or long questions, topic and repeats.
Unit 4 previous year questions
- Design a PDA that accepts the language L = {ww^R | w ∈ {a, b}*}. (7 marks, 2025, Nondeterministic Pushdown Automata)
- 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)
- 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)
- 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)
- 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)
- Design a PDA for the language L= {WW^T | W= (a+b)*} (10 marks, 2023, Nondeterministic Pushdown Automata)
- Design a two stack PDA for the language L={a^n b^n c^n | n>=1} (10 marks, 2023, Two Stack Pushdown Automata)
- Generate CFG for the given PDA M = ({q0, q1}, {0,1}, {x, z0}, δ, q0, z0, q1) where δ is given as: δ(q0,1,z0)=(q0,xz0), δ(q0,1,x)=(q0,xx), δ(q0,0,x)=(q0,x), δ(q0,ε,x)=(q1,ε), δ(q1,ε,x)=(q1,ε), δ(q1,0,x)=(q1,xx), δ(q1,0,z0)=(q1,ε) (10 marks, 2023, PDA and CFG Interconversion)
- Discuss briefly about the Push Down Automata (PDA). (2 marks, 2022, Nondeterministic Pushdown Automata)
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
Unit 4 question pattern
- 2-mark questions: 7 asked in 2018–2025
- 7-mark questions: 12 asked in 2018–2025
- 10-mark questions: 4 asked in 2018–2025
- About 23 marks from Unit 4 in every paper
- 14 questions were asked again in a later year
Unit 4 questions year by year
- 2025: 2 Unit 4 questions asked (14 marks across that year's papers)
- 2024: 4 Unit 4 questions asked (23 marks across that year's papers)
- 2023: 5 Unit 4 questions asked (34 marks across that year's papers)
- 2022: 3 Unit 4 questions asked (14 marks across that year's papers)
- 2019: 5 Unit 4 questions asked (30 marks across that year's papers)
- 2018: 4 Unit 4 questions asked (23 marks across that year's papers)