The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+13 votes

Give a deterministic PDA for the language $L=\{a^ncb^{2n} \mid n \geq 1\}$ over the alphabet $\Sigma = \{a,b,c\}$. Specify the acceptance state.

+16 votes

Best answer

$L=\{a^n c b^{2n}\}$

$\qquad=\{acbb,aacbbbb,aaacbbbbbb,\ldots\}$

Here, $\textbf{c}$ acts as center. Push $2$ $a$'s for each $\textbf{a}$ and after $\textbf{c}$ start popping an $\textbf{a}$ for each $\textbf{b}$. If stack is empty and string is finished we move to $q_2$ which is the acceptance state.

0 votes

Two way to draw it

2 figure) For single input a push two a's on stack for state 0 and when c comes then don't do anything and change the state to 1 now as b will come the then top of the stack will have a then pop the a's for b's ,so when stack becomes empty then on seeing the input Null we can accept it by changing state to 2 (final) state.

1 figure) by pushing a's then don't do anything as c comes and move to state to 1 now if b comes then top of stack has a, don't do anything for first b (move to state 2)then for second b pop the a(move to state 3) repeat steps if there are more a's on the stack (as shown in figure,by moving from state 3 to state 2 ) otherwise accept it by moving from state 3 to 4.

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,541 questions

54,071 answers

187,187 comments

70,978 users