in Theory of Computation edited by
20,081 views
35 votes
35 votes

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
in Theory of Computation edited by
by
2261 2454 2576
20.1k views

2 Comments

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

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

 

 

1
1

Subscribe to GO Classes for GATE CSE 2022

2 Answers

68 votes
68 votes
 
Best answer

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$

edited by
by
212 350 586

5 Comments

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

1
1

@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.

1
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.

4
4

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

0
0
11 votes
11 votes
(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

5 Comments

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

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

9
9
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
2
2
@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
0
0
Answer:

Related questions