GATE IT 2004 | Question: 40

Question

Let $M = (K, Σ, Г, Δ, s, F)$ be a pushdown automaton, where

$K = (s, f), F = \{f\}, \Sigma = \{a, b\}, Г = \{a\}$ and
$Δ = \{((s, a, \epsilon), (s, a)), ((s, b, \epsilon), (s, a)), (( s, a, a), (f, \epsilon)), ((f, a, a), (f, \epsilon)), ((f, b, a), (f, \epsilon))\}$.

Which one of the following strings is not a member of $L(M)$?

• A. $aaa$
• B. $aabab$
• C. $baaba$
• D. $bab$

Comments

Correction needed in Question third given transition –

 

(s,a,€) ---> (f,€)

@arjun sir please correct it .

---

@itsmeeLucifer Hows that correct?

---

@Abhineet Singh(s,a,€) ---> (s,a) means going from state s to state s  by reading input a, popping nothing and pushing a into the stack

same you can do for others to

Answer 1

Answer is D.

First of all the transition $(s, a, \epsilon) , (s, a)$ means on input $a$, the PDA stays in same state and pushes $a$ on stack irrespective of the current stack top value ($\epsilon$ means read nothing from stack and is not the stack bottom symbol). Like $epsilon$ moves in NFA, this makes the given PDA non-deterministic. 

The language is like:

In start state $a$'s or $b$'s come, just push $a$'s on stack except for the last $a$ which is used to shift from "start state" to "final state" (non-determinism) without consuming any stack symbol. Now in "final state", for equal no's of $a$'s and $b$'s just pop $a$'s from stack. This is the interpretation of transitions given for the language. So, it accepts strings of the form $wab^n$ where $w \in (a+b)^*$ and $n < |w|.$ This is violated only for option D and hence it is not in $L.$ 

For any string push 'a' on stack except for the final 'a' which will cause a move to final state and a pop. Then for every 'b', stack is popped. If stack becomes empty before string end, we reach a dead state and string is rejected. Else, accepted. 

• A. $aaa $: push $a$....push $a$....pop $a\qquad$Final State, ACCEPTED
• B. $aabab$: push $a$....push $a$...push $a$...pop $a$...pop $a$$\qquad$Final State, ACCEPTED
• C. $baaba$ : push $a$...push $a$....push $a$....push $a$....pop $a$$\qquad$Final State, ACCEPTED
• D. $bab$ : push $a$....pop $a$....dead state$\qquad$ REJECTED

PS: This PDA is an NPDA and acceptance is by FINAL State. If no valid move is given for any state in NPDA, then the corresponding transition goes to a dead state. 

Comments

@Manu Shaurya

”Reading a symbol x” from stack itself means “Popping symbol x” from the stack. So, nothing is missed in the previous comment. The second line of previous comment is:

Reading symbol "y" on stack implies "pop y"

---

What does the transition (s, a, €) --> (s, a) mean? Does it mean that we are pushing a on to the top of stack or are we replacing the top of stack with a ​​. I got this confusion because in some other question I saw that the transition (q, x, z) ---> (q', az) means pushing a on top of stack 

@Deepak Poonia 

---

@soukarsha

Your doubt is answered HERE.

 (s, a, €) --> (s, a) means that we are pushing a on to the top of stack (& since we are not reading the stack, so no stack symbol is popped).

Answer 2

First have a look on the PDA for the given transitions:

now here transition ((s,a,ϵ),(s,a)) implies reading input symbol 'a' in state 's' we have to move 's' having any symbol on the top of stack...epsilon here implies "anything on the TOS".

Now observe the PDA carefully, it is saying that in the starting you have to push one 'a' for each of 'a' and 'b'. And in the end you have to pop one 'a'  by one 'a' or one 'b'. Thus the count of a's and b's  in first half of the string should be equal second half of string. Now to move from first half to the second half we are required one 'a' i.e. moving from s to f.

So, all odd strings in which 'a' is the middle symbol will be accepted. For eg. aab a bbb

Thus, in our question option B. is (aa b ab) having 'b' in the middle...and thus can't be accepted.

Comments

sir here should we consider that not all transitions(specially acceptance by empty stack or acceptance by final state) are given?

Answer 3

@Arjun Sir pls check this ans

1.((s, a, ε)---> (s, a))

2.((s, b, ε)---> (s, a))

3.((s, a, ε)---> (f, ε))

4.((f, a, a)---> (f, ε))

5.((f, b, a)---> (f, ε))

option A---  aaa

 (s,a,ε)---transition 1-->(s,a)

 (s,a,a)---transition 3-->(f,a) //just consume the input and move to final state

                                                      don't change stack symbol

 (f,a,a)---transition 4-->(f,ε) //pop the topmost symbol

  since the stack is empty now and string is also complelety read so it is accepted

option C---  baaba

 (s,b,ε)---transition 2-->(s,a) //read symbol b and push a onto stack

                      

 (s,a,a)---transition 1-->(s,a) // just consume the input without seeing the stack symbol

    and push a onto stack

(s,a,ε)---transition 3-->(f,a)// just consume the input without seeing the stack symbol

    and move to final state

 (f,b,a)---transition 5-->(f,ε) //pop the top of stack

 (f,a,a)---transition 4-->(f,ε) //pop the top of stack 

  since the stack is empty now and string is also complelety read so it is accepted

option D---  bab

 (s,b,ε)---transition 1-->(s,a)

 (s,a,a)---transition 3-->(f,a) //just consume the input and move to final state

                                                 don't change stack symbol

 (f,a,a)---transition 4-->(f,ε) //pop the topmost symbol

  since the stack is empty now and string is also complelety read so it is accepted

Option B—aabab

 (s,a,ε)---transition 1-->(s,a) //read symbol a and push a onto stack

 (s,a,a)---transition 3-->(s,a) // just consume the input without seeing the stack symbol

and move to final state

(s,b,a)---transition 5-->(f, ε)// pop the top of stack

Now we are stuck as no move is defined so this is not accepted by PDA

Comments

@Ankgkit

Without (s,a,a)-> (f,a) transition both option (b) and (c) will be rejected.

---

nice and simple explanation.

---

This is npda , so there are multiple ways . What is transitions are 2,1,3,5,4 for option C.

Answer 4

acc. to the transitions given, the machine will reach the final state.. only when stack contains null.. but the moment. input symbol b is provided..symbol a will be pushed in the stack.. so acc. to me.. neither of c) or d) is a member.

Comments

According to what I have perceived  the terminology here is at state s we  read  a. And top of the symbol is anything we go to state s with top of the a   so  by this explanation of transition rule   as explained by Rohan above similar argument give ans b.    The epsilon is not a symbol of stack set so it correspond to any

---

http://www.geeksforgeeks.org/gate-gate-it-2004-question-40/

c and d both will be the answer because it is NPDA not PDA

---

@Arjun sir  please correct me (( s, a, ε), (f, ε)) condition is not correct means somethink is wrong in th question