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

@Deepak Poonia Sir, 2025 version of PYQ booklet is having B as answer. 

---

Option D is correct

---

many people are worried that option b is correct they are thinking because the book/resource they are seeing this question from have transiton ((s,a,epsilon),(s,a)) but  in above mentioned question we can clearly see it is
((s,a,a),(s,a)

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

@Deepak Poonia Best answer which covers everything. 

Thanks.

---

@Shaik Masthan sir please clear this question. How to identify which option is correct? (i'm thinking in a same way like ayush sir was thinking )

Thanks

---

@halfcodeblood, added my answer.

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?

---

many people are worried that option b is correct they are thinking because the book/resource they are seeing this question from have transiton ((s,a,epsilon),(s,a)) but  in above mentioned question we can clearly see it is
((s,a,a),(s,a)

also a bit correction in your explantion is that epsilon while reading stack here means skipping reading the stack but if in question in output/desitnation if epsilon given it simply means pop you can refer sipser toc book altough i have not read it but i got to know via lectures

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

nice and simple explanation.

---

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

---

@Aditi Tiwari but where transition (s,a,a) is defined?

Answer 4

Context Free Language can be accepted either by empty stack or final state.

Given PDA is non-deterministic due to on state 's' and input 'a' two possibilities exist. (i.e., either push 'a' into the stack without seeing the top of the stack or pop 'a' only from the stack).

Note that, (s,a,a)  ---> (f,epsilon) is the only transition that lead to final state. After that it is popping 'a' from stack for every 'a' or 'b' of input.

Hence, there are two possibilities after reaching to the final state:- 

1. no.of remaining symbols (consider only 'a' and 'b') in input string are less than (or equal) to the no.of symbols in the stack. Then we will end up with some symbols in stack. However, as we are in final state, and complete input string processed $\Rightarrow$ input string is accepted.
2. no.of remaining symbols (consider only 'a' and 'b') in input string are grater than the no.of symbols in the stack. Then we will end up with some symbols in input string but stack is empty. There is no other transitions (except popping from stack) exist on final state, and input string is not completely processed $\Rightarrow$ input string is rejected.

Therefore we can conclude that input string should be something like : (X).a.(Y) and length of Y should be less than length of X.

Therefore pattern = (a+b)^m . a . (a+b)^n and m>n ---- 

[Note: 'a' is non-determinstically determined by PDA]

 

One possible doubt is : why not m $\geq$ n ?

We are sure about m>n. we need to understand what if m = n.

let consider this scinario : X part of the input string is processed. Therefore we have m symbols in stack and we need to process remaining input string. 
on processing 'a', as (s,a,a)  ---> (f,epsilon), one element is popped from stack and no push into the stack.

Therefore we have m-1 symbols in the stack. and we have to process Y part in the input string. As stack size is m-1, the remaining input string should be atmost m-1 size. Otherwise, input will be rejected.

Therefore m > n but not m $\geq$ n.

if we check the options one by one :-

1. $aaa $: push $a$....push $a$....pop $a\qquad$Final State, ACCEPTED
2. $aabab$: push $a$....push $a$...push $a$...pop $a$...pop $a$$\qquad$Final State, ACCEPTED
3. $baaba$ : push $a$...push $a$....push $a$....push $a$....pop $a$$\qquad$Final State, ACCEPTED
4. $bab$ : push $a$....pop $a$....dead state$\qquad$ REJECTED

Comments

Then you can't get correct answers for this question.

---

but now understand the flow of this question.

---

completely understand,probably this could be the best answer

Answer 5

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

Answer 6

The question above is wrong..

Instead of ((s,a,epsilon),(f,epsilon)) , it should be ((s,a,a),(f,epsilon)).

Comments

 Aditya Bahuguna

what are all the right transition?

---

Δ={((s,a,ϵ),(s,a)),((s,b,ϵ),(s,a)),((s,a,ϵ),(f,ϵ)),((f,a,a),(f,ϵ)),((f,b,a),(f,ϵ))}

what is this line trying to convey?

((s,a,ϵ),(s,a)) - this says when epsilon is top of stack ,  if a comes push a  right ?

what are the rest conveying