recategorized by
3,505 views
3 votes
3 votes

The language accepted by the non-deterministic pushdown automaton

$M=( \{ q_0, q_1, q_2\}, \{a, b\}, \{ a, b, z\}, \delta, q_0, z, \{q_2\})$ with transitions

$\delta (q_0 a, z) = \{ (q_1 a), (q_2 \lambda) \}$;

$\delta (q_1, b, a) = \{ (q_1, b) \}$

$\delta (q_1, b, b) = \{ (q_1 b) \}, \delta (q_1, a, b) = \{ (q_2, \lambda ) \}$ is

  1. $L(abb*a)$
  2. $\{a\} U L(abb*a)$
  3. $L(ab*a)$
  4. $\{a\} U L(ab*a)$
recategorized by

1 Answer

Best answer
1 votes
1 votes

A. abb*a will make pushdown automata to move from

  • q0-----(a)-----> {q2}------(b)---->X  Hanged.
  • But we can consider alternate transition in NPDA
  • q0------(a)------>q1-------(b)------>q1-------(b)*------>q1------(a)----->{q2} //Accepted

B. q0-----(a)-----> {q2}//accepted

  • Already proved that abb*a is accepted
  • Hence {a} U abb*a  is accepted and more accurate answer

C. ab*a

  • if b=0,  input is aa
  • q0------(a)------>q1------(a)------>X  //not accepted

D. aU{ab*a}

  • As ab*a is not accepted aU{ab*a} is also not accepted

Answer is B

selected by
Answer:

Related questions

1 votes
1 votes
1 answer
2
go_editor asked Jul 22, 2016
2,731 views
The language $L=\{a^n b^n a^m b^m \mid n \geq 0, m \geq 0 \}$ isContext free but not linearContext free and linearNot context free and not linearNot context free but line...
1 votes
1 votes
0 answers
3
go_editor asked Jul 22, 2016
972 views
Non-deterministic pushdown automaton that accepts the language generated by the grammar: $S \rightarrow aSS \mid ab$ is$\delta (q_0, \lambda , z)= \{ (q_1, z) \}; \delta...