20,081 views

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

1. $n$ states
2. $n+1$ states
3. $n+2$ states
4. None of the above

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 :)

Subscribe to GO Classes for GATE CSE 2022

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$

by
212 350 586

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

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.

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}$?

(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..
by
155 291 532

DFA needs to cover all possibilities so sometimes we need dead or trap ..

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

1
5,855 views