Question

Consider the pushdown automation (PDA) below which runs over the input alphabet(a,b,c). It has the stack alphabet
{$z_0,x$} where $z_0$ is the bottom-of stack marker. The set of states of the PDA is {s,t,u,f} where s is the start state and f is the final state. The PDA accepts by final state.The transitions of the PDA given below are depicted in a standard manner. For example, the transition(s,b,X)$\to$(t,X$Z_0$) means that if the PDA is in state s and the symbol on the top of the stack is X. then it can read b from the input and move to state t after popping the top of stack and pushing the symbols $Z_0$ and X (in that order) on the stack.
(s,a,$Z_0)\to (s,XX{Z}_0$)
$(s,ϵ,Z_0)\to (f,ϵ$)
(s,a,X) $\to (s,XXX$)
(s,b,X) $\to (t,ϵ$)
(t,b,X) $\to (t,ϵ$)
(t,c,X) $\to (u,ϵ$)
(u,c,X) $\to (u,ϵ$)
(u,c,$Z_0$) $\to (f,ϵ$)
The language accepted by the PDA is

• A. {$a^l{b}^m{c}^n|l=m$}
• B. {$a^l{b}^m{c}^n|2l=m+n$}
• C. {$a^l{b}^m{c}^n|m=n$}
• D. {$a^l{b}^m{c}^n|l=m=n$}

Answer 1

The correct option is B {$a^l{b}^m{c}^n|2l=m+n$}

Equivalent PDA of is given transition below:






At state s for every a, we push two X in stack. And when first b is come then for every b we pop out one X and reaches to state t. And after all b are over if we get c then for every c we pop out one X and reaches to state u.
If all X are popped out then reached to final state f, means that, sum of number of b's and number of c's = twice of number of a's
i.e. L={$a^l{b}^m{c}^n|2l=m+n$}