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

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.

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.

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

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

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.

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 construct an equivalent CFG.

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.

Mention the transition function of PDA. List the two ways that PDA accepts the string. Convert the following CFG to PDA. S → AS | ε A → Ab | Bb | ab