edited by
38,220 views
55 votes
55 votes

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)$?

  1. $aaa$
  2. $aabab$
  3. $baaba$
  4. $bab$
edited by

9 Answers

Best answer
62 votes
62 votes

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. 

  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

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. 

edited by
19 votes
19 votes

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.

17 votes
17 votes

@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

6 votes
6 votes
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.
Answer:

Related questions

28 votes
28 votes
5 answers
2
Ishrat Jahan asked Nov 1, 2014
8,780 views
Which one of the following regular expressions is NOT equivalent to the regular expression $(a + b + c)^*$?$(a^* + b^* + c^*)^*$$(a^*b^*c^*)^*$$((ab)^* + c^*)^*$$(a^*b^* ...