GATE IT 2006 | Question: 33

Question

Consider the pushdown automaton (PDA) below which runs over the input alphabet $(a, b, c)$. It has the stack alphabet $\{Z_0, X\}$ where $Z_0$ is the bottom-of-stack marker. The set of states of the PDA is $(s, t, u, f\}$ where $s$ is the start state and $f$ is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition $(s, b, X) \rightarrow (t, XZ_0)$ means that if the PDA is in state $s$ and the symbol on the top of the stack is $X$, then it can read b from the input and move to state $t$ after popping the top of stack and pushing the symbols $Z_0$ and $X$ (in that order) on the stack.

$(s, a, Z_0) \rightarrow  (s, XXZ_0)$
$(s, \epsilon, Z_0) \rightarrow  (f, \epsilon)$
$(s, a, X) \rightarrow  (s, XXX)$
$(s, b, X) \rightarrow  (t, \epsilon)$
$(t, b, X) \rightarrow  (t,\epsilon)$
$(t, c, X) \rightarrow  (u, \epsilon)$
$(u, c, X)  \rightarrow  (u, \epsilon)$
$(u, \epsilon, Z_0) \rightarrow  (f, \epsilon)$

The language accepted by the PDA is

• A. $\{a^lb^mc^n \mid  l = m = n\}$
• B. $\{a^l b^m c^n \mid l = m\}$
• C. $\{a^lb^mc^n \mid 2l = m + n\}$
• D. $\{a^lb^mc^n \mid m = n\}$

Comments

I finally understand this for more understanding refer to : GOCLASSES PDA PYQ PART 1 on Youtube . GATE IT 2004 PDA Question Analysis

---

Option D is correct.

Becz for each a  we put on stack XX and agar b ya c koi aaya tho pop kar dena X 

overall PDA banega 

 

---

D is wrong, for every a we are pushing exactly 2 X's & for every b we pop one X & then for C also we are popping exactly one X till it leads to deletion of all the X's in the stack then only we are moving to final State. So C is CORRECT option.

Answer 1

For every $a$ we put two $X$ in stack [at state $s$]

After that for every $b$ we pop out one $X$    [reach to state $t$ ( getting $b$ after $a$) ]

After that for every $c$ we pop out one $X$    [reach to state $u$ (getting $c$ after $b$)]

If all $X$ are popped  out  then reached to final state $f$ , mean for every $b$ there is $a$, for every $c$ there is $a$ .

$a$ was followed by $b$ and $b$ was followed by $c$ [ state $s$ to $t , t$ to $u , u$ to $f$, final]

means sum of no of $b$'s  and no of $c$'s $=$ twice of no of $a$'s      [ one $a$ for one $b$ , one $a$ for one $c$ ]

i.e. $\{a^lb^mc^n \mid 2l = m + n\}$

Correct Answer: $C$

Comments

@Rishabh1006will the string "aabccc" accepted by this pda ?
if no ,why ?

---

Bhai aab yaad nahi 😅 .. ho gaya GATE 4 saal pehle.. abhi toh job kar raha hoon

---

@Sarah Sayed it will be accepted whats the problem?

 

Answer 2

clearly, after reading "a"  XX add on to the stack and after reading "b" or  "c" X get pop from stack. hence option(C) is our answer i.e 2l=m+n.

Comments

@Tushar Garg

how u make transitiontransition on 's' , plz explain

 

 

Answer 3

PDA for the given CFG is

consider ^ to be epsilon

 

             ip: (a, Z0 -> XXZ0 )  | (a, X -> XXX)

                |

--------->( s ) ----  ip: (^, Z0 -> ^ )  ------------------>( ( f ) )

                |                                                               ^

                |                                                                |

                | ip: ( b, X -> ^ )                                       | ip: ( ^, Z0 -> ^)

                |                                                                |

                v                                                               |

              ( t )  ----  ip:( c, X -> ^ )   ------------------> ( u )

                ^                                                              ^

                 |                                                              |

           ip: b, X -> ^                                        ip: c, X -> ^

 

Strings that are accepted are { ^ , abc , aabbbc , aabccc , aabbcc ,...............}

For a string S = aabccc

Stack = [Z0 ] ( Initial State )

i) For ip = a

       Stack = [ Z0 ] ==> pop 'Z0' and add 'XXZ0' to the stack.

       Stack = [ X , X , Z0]

       Transition : S --> S.

ii) For ip = a

    Stack = [ X , X , Z0 ] ==> pop 'X' and add 'XXX' to the stack.

    Stack = [ X , X , X , X , Z0 ]

    Transition : S --> S.

iii) For ip = b

     Stack = [ X , X , X , X , Z0 ] ==> pop 'X' and add nothing to the stack.

     Stack = [ X , X , X , Z0]

     Transition : S --> t.

iv) For ip = c

     Stack = [ X , X , X , Z0 ] ==> pop 'X' and add nothing to the stack.

     Stack = [ X , X , Z0 ]

     Transition : t --> u.

v) For ip = c

    Stack = [ X , X , Zo ] ==> pop 'X' and add nothing to the stack.

    Stack = [ X , X , Z0 ]

    Transition : u --> u.

vi) For ip = c

    Stack = [ X , Zo ] ==> pop 'X' and add nothing to the stack.

    Stack = [ Z0 ]

    Transition : u --> u.

vii) For ip = ^

    Stack = [ Zo ] ==> pop 'Z0' and add nothing to the stack.

    Stack = [  ]

    Transition : u --> f.

As the stack is empty and also we reached the final state 'f' the string is accepted.

S = a**2 b**1 c**3

l = 2

m = 1

n = 3

==> 2l = m+n 

       2(2) = 1+3

      Therefore option C is correct.

Answer 4

ans (C)...

Comments

i think it shud be A

---

Sir , please give me example of language accepted by option c which is different from language accepted by option a.

Because I am getting only languages like

L={abc,aabbcc,aaabbbccc....}

---

@neenu

language given in option a)  is subset of language given in option c). So all strings belong to language given in option a) is present in language of option c), will be accepted by given pda.

the pda also accepts strings like aabbbc,aabccc

Answer 5

option C

For 1 a, 2 x is pushed into the stack 

for 1 b, 1 x is popped 

then for 1 c, 1 x is popped

so string will consist of a followed by b followed by c. there is no way we can make c count as zero as at stage t, (b,E/#) moved is not defined so PDA will die here, so c will come in string.

Comments

@manikantsharma will the string "aabccc" accepted by this pda ?
if no ,why ?

---

@Sarah Sayed

Our equation was

           2l = m + n    

Check:

           2 (2) = 1 + 3  

               4  =  4

Hence, it will be accepted.

Consider, aabcc 

here, l = 2,  m = 1,  n = 2 

Now, substitute in equation, 

            2l = 4 

            m + n = 3        

Not equal, hence rejected.

Now, with the simulation method, 

 After reading      aa,

the string has     4X,

and we left is      bcc,

Hence,      3X  will be popped out   leaving the stack 

          X
          Z₀

Now there is no transition from state u on ε, X.

The only ε-transition is

(u, ε, Z₀) → (f, ε)

But the top of the stack is X, not Z₀.

So the PDA gets stuck.

Hence, rejected.

---

thankyou @Siddharth_Perkar