Register

GO Classes DPP | GATE CS | Theory of Computation | PushDown Automata

91 views
2 2 votes

For $L=\{w\in{a,b}^* \mid n_a(w)=2n_b(w)\}$, which invariant should a PDA maintain using stack symbols $A$ and $B$ for surplus?

  1. $n_a(\text{read})-2n_b(\text{read})=\#A-\#B$
     
  2. $2n_a(\text{read})-n_b(\text{read})=\#A-\#B$
     
  3. $n_a(\text{read})-n_b(\text{read})=\#A-2\#B$
     
  4. $n_a(\text{read})+n_b(\text{read})=\#A+\#B$

1 Answer

1 1 vote

The target condition is $n_a(w)=2n_b(w)$, so the final difference $n_a(w)-2n_b(w)$ must be $0$. 

A PDA can store this signed difference on the stack. 

Extra $a$s are stored as $A$ symbols. 

If there is a shortage of $a$s because too many $b$s have appeared, that deficit can be stored using $B$ symbols. 

At the end, the string is accepted exactly when this difference becomes $0$, meaning no unmatched surplus remains.
 

Answer : A

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

Related questions

1 1 vote
1 1 answer
85
85 views
GO Classes asked Sep 11
85 views
GO Classes DPP | GATE CS | Theory of Computation | PushDown Automata Design
Let $L=\{x?y \mid x,y\in{0,1}^*$ and $y=x^R\}$. Which of the following strings belong to $L$?$01?10$ $01?01$ $10?01$ $110?110$ $?$
1 1 vote
1 1 answer
94
94 views
GO Classes asked Sep 11
94 views
GO Classes DPP | GATE CS | Theory of Computation | PushDown Automata Design
For the language $L=\{w\in{a,b}^* \mid n_a(w)=n_b(w)\}$, which statements describe a correct PDA design idea?Use the stack to store the currently unmatched majority symbo...
1 1 vote
1 1 answer
118
118 views
GO Classes asked Sep 11
118 views
GO Classes DPP | GATE CS | Theory of Computation | Nested matching
A PDA accepts properly nested strings over $\{(,),[,]\}$ by pushing every opening symbol and popping only when the closing symbol matches the top of stack. Which strings ...
1 1 vote
1 1 answer
87
87 views
GO Classes asked Sep 11
87 views
GO Classes DPP | GATE CS | Theory of Computation | Nondeterministic Matching
Let $L=\{a^m b^n \mid m\le n\le 2m,\ m,n\ge 0\}$. Which strings belong to $L$?$\epsilon$ $ab$ $abb$ $aabbb$ $aabbbbb$ $aaabb$