GATE CSE 2023 | Question: 30

Question

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 ?$

• A. $\left\{a^{m} b^{n} \mid 1 \leq m\right.$ and $\left.n \lt m\right\}$
• B. $\left\{a^{m} b^{n} \mid 0 \leq n \leq m\right\}$
• C. $\left\{a^{m} b^{n} \mid 0 \leq m\right.$ and $\left.0 \leq n\right\}$
• D. $\left\{a^{m} \mid 0 \leq m\right\} \cup\left\{b^{n} \mid 0 \leq n\right\}$

Answer 1

Detailed Video Solution: PDA Push Down Automata Question

$\color{\red}{\text{ALL Theory of Computation Questions:}}$

Question 2: Context Free Grammar But Language Regular

Question 3: Number of States in the Minimal DFA

Question 4: Intersection Closure Property based Question

Question 5: DFA to Regular Expression question: 1(0+11)*

Answer 2

in this pda emtpy string wont be accepted considering empty stack acceptance. Only in option A empty string isn’t part of the language.

Answer 3

Video Solution:

https://www.youtube.com/live/WlzfxlVU6HI?feature=share&t=1004 

Comments

@Deepak Poonia what will be the answer, I think option A is correct, because how number n and m can be equal??

---

A is indeed the correct answer because m needs to be >= 1, because atleast 1 A must be present in stack to reach state p or q, where the popping happens.

Answer 4

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.