edited by
7,481 views
30 votes
30 votes

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

  1. $\{a^lb^mc^n \mid  l = m = n\}$
  2. $\{a^l b^m c^n \mid l = m\}$
  3. $\{a^lb^mc^n \mid 2l = m + n\}$
  4. $\{a^lb^mc^n \mid m = n\}$
edited by

4 Answers

Best answer
39 votes
39 votes
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$
edited by
2 votes
2 votes

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.

0 votes
0 votes
ans (C)...
0 votes
0 votes

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.

Answer:

Related questions

32 votes
32 votes
3 answers
1
45 votes
45 votes
4 answers
4