edited by
1,067 views
4 votes
4 votes

If L is any regular language accepted by Minimal Finite Automaton with $n$ states, then the number of states in Minimal Finite Automaton to accept Prefix(L) is:

  1. $n$
  2. $n+1$
  3. $n+2$
  4. $2n$
edited by

1 Answer

Best answer
4 votes
4 votes

1) If minimal FA is NFA then make all states as final to get Prefixes

2) If minimal FA is DFA then make all states as final except dead state to get prefixes

In both the case no of states will not be changed and remains same as the original FA hence n states.

Option A) is correct

selected by
Answer:

Related questions

6 votes
6 votes
2 answers
1
Bikram asked Nov 26, 2016
1,174 views
Given a regular grammar $G_1$ and a context free grammar $G_2$, the problem of deciding if $L(G_1)$ is a proper subset of $L(G_2)$ is:DecidableUndecidable but semi-decida...
0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
295 views
$G1$ and $G2$ are regular grammars and the language generated by any grammar $G$ is represented by $L(G)$. In this case, $L(G1) \cap L(G2) = \phi$ is a/an:Decidable prob...
0 votes
0 votes
1 answer
3
Bikram asked Nov 26, 2016
203 views
Recursive Enumerable Languages are NOT closed under :UnionIntersectionComplementHomomorphism
0 votes
0 votes
1 answer
4