Register

NFA/DFA

632 views

1 Answer

Best answer
3 3 votes

Here it is important to identify the language. 

As

I) is generating $(a+b)^*$ 

II) is generating $a(a+b)^*$ 

III) is generating $a^mb^n, \; m\geq n$. 

• selected by
Voting & Accepting an answer helps improve the community
← Previous · Memory Access TimeNext → · Probability of Succe...
← Previous in category · Is |L1. L2| = |L1| x...Next in category → · MadeEasy Test Series...
Position:
Show:

Related questions

2 2 votes
1 1 answer
157
157 views
GO Classes asked Oct 1
157 views
GO Classes DPP | GATE CS | Theory of Computation | NFA to DFA
Consider the NFA shown below, where $A$ is the initial state and $D$ is the only accepting state.Which DFA accepts the same language?Initial state: $A$Accepting states: $...
0 0 votes
1 1 answer
88
88 views
GO Classes asked Oct 1
88 views
GO Classes DPP | GATE CS | Theory of Computation | NFA to DFA
Let an NFA have $\mathbf{6}$ states.After applying the standard NFA-to-DFA conversion algorithm, what is the maximum possible number of states in the resulting DFA, inclu...
4 4 votes
2 2 answers
259
259 views
GO Classes asked Jul 10
259 views
GO Classes DPP | GATE CS | Theory of Computation | DFA-NFA Equivalence
Which of the following is true?A language $L$ is accepted by DFA iff it is accepted by some $\epsilon$-NFA. A language $L$ is accepted by $\epsilon$-NFA iff it is accepte...
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...