edited by
33,974 views
93 votes
93 votes

Consider the regular language $L=(111+11111)^{*}.$ The minimum number of  states in any DFA accepting this languages is:

  1. $3$
  2. $5$
  3. $8$
  4. $9$
edited by

8 Answers

Best answer
110 votes
110 votes

Given language $L = (111 + 11111)^* $
Strings , that belongs to the language 

$L = \{\epsilon , 111 , 11111, 111111 , 11111111 , 111111111 , 1111111111 , \ldots $

Due to concatenation with $(111)^*$ if we have three consecutive string lengths in $L,$ then all higher string lengths will be in $L.$

We have strings of length $8,9,10$ in $L$ and so all higher length strings are also in $L.$
So, required DFA will be:

So, there are $5$ states are final states and $4$ states are non-final states ,total number of states are $9$ states.
Hence, option D is true.

18 votes
18 votes
there will be 9 states. with 1st,4th,6th,7th and 9th state being the final states. with a loop on the ninth state.

 {0,3,5,6,8,9,10,11,12,........} this is the set which will be accepted by the min dfa for this expression.
12 votes
12 votes

Minimum number of states in the DFA will be 9, under the assumption that Alphabet consist of only one symbol {1}, using the fact that all the strings can be generated using the given regular expression except 1, 11, 1111, 1111111 since all of the +ve integers can be expressed as a linear combination of 3 & 5 except 1, 2, 4 & 7.

DFA will be as :

5 votes
5 votes

he finite state automata is :

DFA

Explanation:

It is given that language L = (111 + 11111)*
Strings , that belongs in the language are
L = {null , 111 , 11111, 111111 , 11111111 , 111111111 , 1111111111 , ……. form string length 8 , (number of 1’s) , now we can can generate any length of string from length 3 and 5 (i.e. length 8 ,length 9, length 10 , length 11 ,…etc)}
L = {null , 111 , 11111, 111111 , 11111111 , 111111111* }
Strings in length , that belongs in the language
L = {0 ,3, 5, 6, 8, 9, 10, 11, …}
So, there are 5 states that are final states and 4 states that are non-final states
Therefore total number of states are 9 states .
hence option D is true.

Answer:

Related questions