there are two different ways to define pda acceptability.

final state acceptability

in final state acceptability, a pda accepts a string when, after reading the entire string, the pda is in a final state. from the starting state, we can make moves that end up in a final state with any stack values. the stack values are irrelevant as long as we end up in a final state.

for a pda (q, ∑, s, δ, q₀, i, f), the language accepted by the set of final states f is −

l(pda) = {w | (q₀, w, i) ⊢* (q, ε, x), q ∈ f}

for any input stack string x.

empty stack acceptability

here a pda accepts a string when, after reading the entire string, the pda has emptied its stack.

for a pda (q, ∑, s, δ, q₀, i, f), the language accepted by the empty stack is −

l(pda) = {w | (q₀, w, i) ⊢* (q, ε, ε), q ∈ q}

example

construct a pda that accepts l = {0ⁿ 1ⁿ | n ≥ 0}

solution

this language accepts l = {ε, 01, 0011, 000111, ............................. }

here, in this example, the number of ‘a’ and ‘b’ have to be same.

• initially we put a special symbol ‘$’ into the empty stack.

• then at state q₂, if we encounter input 0 and top is null, we push 0 into stack. this may iterate. and if we encounter input 1 and top is 0, we pop this 0.

• then at state q₃, if we encounter input 1 and top is 0, we pop this 0. this may also iterate. and if we encounter input 1 and top is 0, we pop the top element.

• if the special symbol ‘$’ is encountered at top of the stack, it is popped out and it finally goes to the accepting state q₄.

example

construct a pda that accepts l = { ww^r | w = (a+b)* }

solution

initially we put a special symbol ‘$’ into the empty stack. at state q₂, the w is being read. in state q₃, each 0 or 1 is popped when it matches the input. if any other input is given, the pda will go to a dead state. when we reach that special symbol ‘$’, we go to the accepting state q₄.