edited by
38,477 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

2 votes
2 votes
The question above is wrong..

Instead of ((s,a,epsilon),(f,epsilon)) , it should be ((s,a,a),(f,epsilon)).
1 votes
1 votes
If you draw the machine, you will see ,initially for all a and b we are pushing a's into stack and then we skip one a.And then for remaining we are just poping the pushed a's for each alphabet we process.

So language is L={ W1 a W2 |  |W1| = |W2| } // read W1 ,push a to stack and then skip a(which is middle of the string) and then for next half check if its length is same as first half.

Basically, odd length string with a as the middle .So, option b do not satisfy and is the answer.
0 votes
0 votes

@ Arjun sir , please check my answer 

As per the question it is not given that (a,E /aa) i.e., on seeing any symbol we just have to replace whatever on the top of the stack with a and not to push a with every input alphabet . 

Here according to the question given we can logically interpret fig(1) as fig(2).

(A) push a, skip a , pop a and accept

(B) push a , replace with a on seeing a , replace with a on seeing b , skip a , pop a on seeing b and accept

(D) push a on seeing b , skip a , pop a on seeing b and accept 

(C) push a on seeing b , replace tos with a on seeing a , replace tos with a on seeing a, now for b as input we have to be in state 's' only and thus replacing tos with a on seeing b and at last skip a and goto final state f . But as stack is not empty , string is not accepted 

We can conclude the language by PDA as (a+b)*a(a+b)

Answer:

Related questions

28 votes
28 votes
5 answers
2
Ishrat Jahan asked Nov 1, 2014
8,793 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^* ...