Register

GO Classes DPP | GATE CS | Theory of Computation | Empty-Stack Reasoning

ago
24 views
1 1 vote

Let $M$ be a PDA that accepts by empty stack. Suppose every transition of $M$ reads exactly one input symbol, and every transition either pushes one stack symbol or pops one stack symbol, but never both. Which statement is correct?

  1. Every string in $L(M)$ has even length.
     
  2. Every string in $L(M)$ has odd length.
     
  3. $M$ accepts every even-length string.
     
  4. $M$ cannot accept any non-empty string.

1 Answer

1 1 vote

Since $M$ accepts by empty stack, an accepting computation must have the same number of pushes and pops. 

Every transition reads exactly one input symbol. 

Also, every transition is either one push or one pop. 

So the total number of input symbols read is $\text{pushes}+\text{pops}=2\cdot\text{pushes}$, which is even. 

Therefore, every accepted string has even length.

Answer : A

ago
Voting & Accepting an answer helps improve the community
Answer:
← Previous · Identification of re...Next → · GO Classes DPP | GAT...
← Previous in category · Identification of re...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

1 1 vote
1 1 answer
35
35 views
GO Classes asked 3 days ago
35 views
GO Classes DPP | GATE CS | Theory of Computation | PDA Trace Analysis
A PDA accepts the language $L=\{a^n b^m \mid m>n\ge 0\}$. Which of the following strings are accepted?$aabbb$ $bbbb$ $aaab$ $abb$ $\epsilon$
1 1 vote
2 2 answers
80
80 views
GO Classes asked 5 days ago
80 views
GO Classes DPP | GATE CS | Theory of Computation | Acceptance Conversion
A PDA $P$ accepts a language by final state. We want to construct another PDA $P_1$ such that $N(P_1)=L(P)$, meaning $P_1$ accepts by empty stack exactly the language acc...
1 1 vote
1 1 answer
41
41 views
GO Classes asked 5 days ago
41 views
GO Classes DPP | GATE CS | Theory of Computation | Trace Accepted Strings
States $q_1$ and $q_4$ are final states. The PDA pushes one $a$ for every input $a$, pops one $a$ for every input $b$, and then reads any number of $c$'s. Which strings a...
1 1 vote
1 1 answer
40
40 views
GO Classes asked 5 days ago
40 views
GO Classes DPP | GATE CS | Theory of Computation | PDA Language Analysis
The PDA first pushes either two or three $\#$ symbols for every input $0$, then pops one $\#$ for every input $1$. Which language is accepted? $\{0^n1^m \mid 2n\le m\le 3...