TAFL Unit 4 Handwritten Notes AKTU (BCS402)

AKTU · BTECH · Semester 4 · Theory of Automata and Formal Languages · Unit 4 · Handwritten Notes

AKTU Theory of Automata and Formal Languages (BCS402) Unit 4 handwritten notes for B.Tech Semester 4 – Push Down Automata and Properties of Context Free…

A preview is available. Sign in or check access options in the reader for the complete resource.

Unit 4: Push Down Automata and Properties of Context Free Languages – AKTU syllabus topics

  • Nondeterministic Pushdown Automata: NPDA Definition and Moves, Language Accepted by NPDA
  • Deterministic Pushdown Automata: Deterministic Context Free Languages
  • PDA and CFG Interconversion: PDA for Context Free Languages, CFG for Pushdown Automata
  • Two Stack Pushdown Automata
  • Pumping Lemma for CFL
  • Properties of Context Free Languages: Closure Properties of CFL, Decision Problems of CFL

Most asked AKTU PYQ questions from Unit 4

  1. Q2d. Design a PDA that accepts the language L = {ww^R | w ∈ {a, b}*}. (7 marks, 2024-25)
  2. Q2d. Design a PDA for the language L= {WW^T | W= (a+b)*} (10 marks, 2022-23)
  3. Q6a. 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, 2023-24)
  4. Q6b. 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, 2023-24)
  5. Q1f. 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, 2023-24)
  6. Q1h. Draw the graphical representation for PDA. (2 marks, 2022-23)
  7. Q6b. 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, 2022-23)
  8. Q2d. Convert the grammar S -> aAA, A -> a | aS | bS to a PDA that accepts the same language by Empty stack. (10 marks, 2021-22)
  9. Q2d. Differentiate between DPDA and NPDA. Construct a PDA that accepts language L = {aⁿbⁿ | n ≥ 1}. (7 marks, 2023-24)
  10. Q1g. Explain pumping lemma for context free language. (2 marks, 2022-23)

AKTU paper codes: BCS402, KCS402, RCS403

Other Theory of Automata and Formal Languages units

Theory of Automata and Formal Languages previous year papers

Browse all notes · Semester 4 notes