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

@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