GATE CSE 1999 | Question: 1.4

Question

Consider the regular expression $(0 + 1) (0+1) \dots N$ times. The minimum state finite automaton that recognizes the language represented by this regular expression contains

• A. $n$ states
• B. $n+1$ states
• C. $n+2$ states
• D. None of the above

Comments

Minimal DFA includes dead states also, but not having unreachable or equal states. So here, MFA contains (n+2) states.

---

The minimum state finite automation that recognises the language represented by regular expression (0+1)(0+1)....n times is n+1 ​​​​​​.

This language contains string with exactly length n.

(n+1) states are required to count length up to n.No trap or dead state since we are making minimal FA , not minimal DFA.

Option b) is correct…

Hope it helps you :)

 

​

 

Answer 1

As far as for above problem say regular expression for $(0+1)(0+1)\ldots 3$ times $=(0+1)(0+1)(0+1)$

Having DFA:

So, for regular expression $(0+1)(0+1)...N$ times we have $\mathbf{N+2}$ states in DFA 

$N+1$ states in NFA ( we can remove dead state) 

When question is about minimum state finite automata (and nothing is mentioned NFA/DFA) then which ever having minimum number must be taken which here is $N+1$ states. 

Correct Answer: $B$

Comments

@Praveen sir then what answer was given in the official key?

should we consider (N+2) as default by DFA

---

No,if you put one state then there need to be a self-loop,right? and self loop can contain infinite length of string!

So, if n=1 then you need 2 states,(A-->B)

---

@Praveen sir I think Minimum Finite Automata means DFA without ( unreachable and equal states ).

But my above concept contradicts with ur ans

"When question is about minimum state finite automata (and nothing is mentioned NFA/DFA) then which ever having minimum no.  take that"

sir plz can u give any reference regarding ur statement. It would really a great help.

---

quite frequently asked question in one or other form

---

A finite automata may be

(1) An NFA

(2)DFA

They are asking that finite automata which has minimum number of states.

clearly for any regular language, NFA would have less number of states as compared to DFA because in NFA dead configuration is allowed and through use of dead configuration we can model the reject state of DFA .

So, here they are asking minimum number of states in NFA.

---

@Bikram sir

"When question is about minimum state finite automata (and nothing is mentioned NFA/DFA) then which ever having minimum no.  take that"

Any reference for this?

If this is true then an equivalent MINIMAL nfa would always have no. of states less than or equal to the equivalent dfa.

Then, in effect in such situations when nothing is mentioned we should take it to be nfa.

Is my conclusion right?

---

@VS

yes your conclusion is correct.

NFA have less state than DFA if we don't consider dead states.

For every n there is a language over {a,b} which is accepted by an NFA having n states, but its minimal DFA has 2ⁿ states.

Read this : https://cs.stackexchange.com/questions/59431/size-comparison-of-nfa-and-minimal-dfa/59435

---

if an NFA having n states, then

1<= no of states in DFA <= 2^n

---

shouldn't the statement be n<= no of states in DFA <= 2^n ??

---

i too think the same

---

susmita

No

---

Praveen Saini Sir please explain this in more detail and expalnation

---

Above NFA in comments having 2 states but its corresponding minimized dfa having 1 states.

nfa having n states, can have maximum of $2^n$ states in corresponding DFA.

say $\{q_0,q_1\}$ are states in nfa, then its corresponding DFA have maximum of 4 states, $\{\{\},\{q_1\},\{q_2\},\{q_1,q_2\}\}$

---

@Praveen Saini sir

this is correct approach$?$

They have asked minimum state finite automaton, so we can take non-deterministic finite automaton.

So, the answer will be $n+1$ states.

If they especially asked minimum state deterministic finite automaton, then the answer  will be $n+2$ states.

---

@Praveen Saini sir check his answer .. I am also thinking same as him 

---

@Lakshman Patel RJIT  here in question they are asking for minimal state FA means 'NFA' . So, it need not cover all transitions. So, here answer should be n+1.

---

@air1ankit

Yes 

$NFA\implies n+1$ states

$DFA\implies n+2$ states

Minimum state finite automaton $=min\left\{\begin{matrix} n+1\\ n+2\end{matrix}\right. = n+1$ states.

---

@Praveen Saini @Lakshman Patel RJIT

If a Minimal NFA has 'n' states, then this holds true,

n $\leq$ Minimal DFA $\leq$ $2^{n}$, instead of 1 $\leq$ Minimal DFA $\leq$ $2^{n}$?

Answer 2

(0+1)(0+1)......... n times

Length will be n..

No of states required for n length is n+1, one more for trap.. total n+2 states..

Comments

Not sometimes - we need to cover all possible transitions in a DFA- because the definition says "transition function" and not "transition relation" as for a PDA.

https://en.wikipedia.org/wiki/Deterministic_finite_automaton

---

But here in question they are asking for minmal state FA means 'nfa' . So, it need not cover all transitions. So, here answer shud be n+1

---

@Arjun sir please confirm answer according to me it should be n+2 bcz by default Finite automata is DFA so dead state also need to consider .... Is it? If n+1 then plz explain