Register

GO Classes DPP | GATE CS | Theory of Computation | NFA Representation

283 views

4 Answers

2 2 votes

From state $B$, there are two cycles that bring the automaton back to $B$. 

One cycle is $B \xrightarrow{1} A \xrightarrow{1} B$, which gives the block $11$. 

Another cycle is $B \xrightarrow{1} C \xrightarrow{1} D \xrightarrow{0} B$, which gives the block $110$. 

These blocks may repeat any number of times. 

Finally, from $B$, the automaton goes to final state $F$ on input $0$. 

Hence, the language is $(11+110)^*0$.

Answer : C

0 0 votes
  • here first shortest accepted string is 0
  • b as central hub it take 110 to go final state
  • b with A transition again take 11 strings now combing both
  • (11+110)*0
0 0 votes
To go to final state we need to be in B and then we need to get a zero.
From B if you get a 1 to can end up in one of two branches both of which end up in B, and then 0 can take you to final state.
From the options the only one that satisfies is C (11 + 110)*0

Answer: C
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

5 5 votes
3 3 answers
221
221 views
GO Classes asked Jul 8
221 views
GO Classes DPP | GATE CS | Theory of Computation | NFA Equivalence
Given NFA in the first figure is equivalent to the given DFA in the second figure. Is the given statement true?True False
6 6 votes
4 4 answers
326
326 views
GO Classes asked Jul 8
326 views
GO Classes DPP | GATE CS | Theory of Computation | NFA to DFA
Which of the following statements are correct?There is a $2^k$-state DFA for every $k$-state NFA. There is a $k$-state DFA for every $2^k$-state NFA. There is a $k$-state...
4 4 votes
3 3 answers
220
220 views
GO Classes asked Jul 8
220 views
GO Classes DPP | GATE CS | Theory of Computation | NFA Language
Which of the following best describes the language accepted by the non-deterministic automaton below?$(a+b)^*a(a+b)^*b(a+b)^*$  $(a+b)^*$  $(a+b)^*a(a+b)b$  $(abb)^*$
4 4 votes
2 2 answers
221
221 views
GO Classes asked Jul 8
221 views
GO Classes DPP | GATE CS | Theory of Computation | Accepting States
What should be the accepting state(s) in order to accept $1^*00$?$\{Y\}$ $\{Z\}$ Any one of $Y$ and $Z$ can be accepting state $\{X,Y\}$