Redirected
edited by
6,760 views
12 votes
12 votes

Consider the pushdown automaton $\text{(PDA)}\;P$ below, which runs on the input alphabet $\{a, b\}$, has stack alphabet $\{\perp, A\}$, and has three states $\{s, p, q\}$, with $s$ being the start state. A transition from state $u$ to state $v$, labelled $c / X / \gamma$, where $c$ is an input symbol or $\epsilon, X$ is a stack symbol, and $\gamma$ is a string of stack symbols, represents the fact that in state $u$, the $\text{(PDA)}$ can read $c$ from the input, with $X$ on the top of its stack, pop $X$ from the stack, push in the string $\gamma$ on the stack, and go to state $v$. In the initial configuration, the stack has only the symbol $\perp$ in it. The $\text{(PDA)}$ accepts by empty stack.


Which one of the following options correctly describes the language accepted by $P ?$

  1. $\left\{a^{m} b^{n} \mid 1 \leq m\right.$ and $\left.n \lt m\right\}$
  2. $\left\{a^{m} b^{n} \mid 0 \leq n \leq m\right\}$
  3. $\left\{a^{m} b^{n} \mid 0 \leq m\right.$ and $\left.0 \leq n\right\}$
  4. $\left\{a^{m} \mid 0 \leq m\right\} \cup\left\{b^{n} \mid 0 \leq n\right\}$
edited by

5 Answers

2 votes
2 votes
in this pda emtpy string wont be accepted considering empty stack acceptance. Only in option A empty string isn’t part of the language.
1 votes
1 votes
1 votes
1 votes
Only state q empties all the symbols from the stack, so the string must reach to state q in order to get accepted.

Several ways to get into state q are – {$a^{m} | m>1$}  U  {$a^{m}b^{n} | n<m$}  

combining them we will get,

$L(P) = $ {$a^{m}b^{n} | 1\leq m\ and\ n<m$}, so option (A) is the answer.
Answer:

Related questions