Test by Bikram | Theory of Computation | Test 1 | Question: 6

Question

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:

• A. $n$
• B. $n+1$
• C. $n+2$
• D. $2n$

Comments

because epsilon is a empty string .

The empty string is the special case where the sequence has length zero, so there are no symbols in the string. This is called Epsilon.

There is only one empty string, because two strings are only different if they have different lengths or a different sequence of symbols.

---

@bikram

hi

let take a regular language (00)*

it has minimum dfa has 2 states .

Now u r saying prefix(L) .what is signify ?

i will appreciate ur reply..

---

@wanted Its prefix would be epsilon, 0, 00,000,... so on. So basically, we have to make all the states of the given Language as final state to accept prefixes. Therefore, no. of states is same as in the language given.

Answer 1

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

Comments

Atmost n, means it can be n.. Right ?

Then why to prefer exactly n over atmost n?

---

The counterexample is not minimal DFA. Then how it's the counterexample for this question.

---

@Rusty_01 

Then can you give minimal DFA for it ?