Bsc CSIT Semester 4 – Theory of Computation – Unit V: Push Down Automata (7 Hrs.)

Question 1

How can you define the language accepted by a PDA? Explain how a PDA accepting language by empty stack is converted into an equivalent PDA accepting by final state and vice-versa.

Marks: 10

Year: 2076 Final TU

Language Accepted by a Pushdown Automaton (PDA) Definition A Pushdown Automaton (PDA) is a 6-tuple: M = (Q, Σ, Γ, δ, q₀, Z₀, F) Where: - Q → Finite set of states - Σ → Input alphabet - Γ → Stack

Question 2

Construct a PDA accepting language over {0, 1} representing strings with equal no of 0s and1s. Show by sequence of IDs that 0101 is accepted by this PDA.

Marks: 5

Year: 2076 Final TU

Language: L = { w ∈ {0,1} | number of 0s = number of 1s } --- Idea: The PDA uses its stack to store unmatched symbols. - When reading 0: - Push 0 if top is 0 or Z₀. - Pop if top is 1.

Question 3

Define a Push Down Automata. Construct a PDA that accepts L = {a b | n > 0}

Marks: 5

Year: 2078 Final TU

Push Down Automata (PDA) Definition A Push Down Automata (PDA) is a computational model that extends finite automata with a stack memory. It can recognize context-free languages. Formal Definition P

Question 4

Give the formal definition of Push Down Automata. How CFG can be converted into equivalent PDA. Explain with an example.

Marks: 5

Year: 2079 Final TU

Push Down Automata (PDA) and CFG to PDA Conversion 1. Formal Definition of PDA A Push Down Automata (PDA) is a mathematical model that extends a finite automata with a stack. Formally, a PDA is a

Question 5

Design a PDA over {x,y} which accepts strings defined by the language \(L = \{\,x^n y^n x y \mid n \ge 0\,\}\). Show acceptance of xyxy.

Marks: 5

Year: 2080 Final TU

PDA for \(L = \{\,x^n y^n x y \mid n \ge 0\,\}\) and acceptance of xyxy --- 1. Informal idea - The PDA uses the stack to match the first block x^n with the next block y^n (push an X for each x, pop

Question 6

How is PDA to CFG conversion done? Consider a PDA that accepts by empty stack, P=({p,q},{0,1}, {Z},δ,p,z); with δ defined as δ(p,0,z)=(p,0z), δ(p,0,0)=(p,00), δ(p,1,0)=(p,ε), δ(p,ε,z)=(q,ε), Now const

Marks: 5

Year: 2080 Final TU

Given PDA (accepts by empty stack) \(P=(\{p,q\},\{0,1\},\{Z\},\delta,p,Z)\) with transitions: - \(\delta(p,0,Z) = (p,0Z)\) — push 0 on top of Z when reading 0 - \(\delta(p,0,0) = (p,00)\) — push

Question 7

Construct a PDA that accepts string over Σ ={a,b} that contains equal number of a’s followed by equal number of b’s. Show acceptance of aabb and aab.

Marks: 5

Year: 2080 Final TU

PDA for L = { aⁿbⁿ | n ≥ 0 } (Equal number of a’s followed by equal number of b’s) --- Intuition The PDA pushes an A for every a and pops an A for every b. If all As are popped and the input is fin