Consider the transition diagram of a PDA given below with input alphabet ∑ = {a, b} and stack alphabet Γ = {X, Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA. Which one of the following is TRUE?

Consider the transition diagram of a PDA given below with input alphabet ∑ = {a, b} and stack alphabet Γ = {X, Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA. Which one of the following is TRUE? Correct Answer L = { aⁿ|n ≥ 0} ∪ {aⁿbⁿ|n ≥ 0} and is deterministic context-free

Concept:

Acceptance of given string by a push down automata in two ways either by

• Acceptance by final state: if machine at the end of the string enters to one of the final states then string is accepted.

• Acceptance by Empty state: if at the end of the string, stack is empty then string is accepted.

Explanation:

In this PDA, initial state is also the final state it means null string is accepted by the given push down automata (PDA). Consider the states as q₁, q₂ and q₃ where q₁ is the final state.

Transition of given PDA are:

1) (q₁, a, Z) => (q₁, XZ)

2) (q₁, a, X) => (q₁, XX)

3) (q₁, b, X) => (q₂, ϵ)

4) (q₂, b, X) => (q₂, ϵ)

5) (q₂, ϵ, Z) => (q₃, Z)

First two transition show that after giving input a at transition state remains same. With every input ‘a’ we push X into stack. It means aⁿ is always accepted for n>= 0. Transition 3 and 4 shows that for every b input a X is popped out of the stack until stack symbol is Z and string becomes empty. It means ‘b’ occurred same number of times as ‘a’. It represents language of the form {aⁿbⁿ for n>=0 }. It is a DCFL.