The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+22 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

- $n$ states
- $n+1$ states
- $n+2$ states
- None of the above

+39 votes

Best answer

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

$=(0+1)(0+1)(0+1)$

Having **DFA: **

So, for regular expression $(0+1)(0+1)...N$ times 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 no.

$N+1$ states.

+2

sir as stated in this link . should we consider dfa if nothing is given . https://goo.gl/P2jLLi

what u think .

+2

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

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

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

0

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)

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

+1

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

0

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.

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

0

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

+6

@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

nstates, but its minimal DFA has2states.^{n}

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

+9 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..

Length will be n..

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

0

but is it necessary that you will always need a dead state for dfa ,as you are adding 1 dead state every time for the dfa (minimal) asked.

+6

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,903 questions

47,558 answers

146,289 comments

62,306 users