The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+31 votes
4.8k views

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$
asked in Theory of Computation by Active (3.7k points)
edited by | 4.8k views
0
After reading solution, I was like "F*** Awesome Question".

6 Answers

+36 votes
Best answer

Given language $L = (111 + 11111)^* $
Strings , that belongs in the language 
$L = \{null , 111 , 11111, 111111 , 11111111 , 111111111 , 1111111111 , ....... $ form string length $8$ , (number of $1$'s) , you 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 , 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.

answered by Loyal (5.9k points)
edited by
+15
Here we need to proof that any length of string that is greater or equal to 8 can be generated with 3 or 5.
In number theory, we can define problem like that:
"Any arbitrary integer x that is greater or equal to 8 can be written in form of 3a+5b."

Proof:
Using induction,
Base case: for x=8, this is true, 8 = 3(1)+5(1)
Inductive Step: assume it is true for x-3, i.e x-3 = 3a+5b
now we need to prove for x
x-3 = 3a+5b (from inductive step)
=> x=3(a+1)+5b               Proved.

Actually this prove is wrong :o
U know why ?
I can't jump over 3, i.e if formula is true for x-3, then i can't say it is true for x also. I can only say it is true for x-2.
But if we define three base cases then we can say.

Correct Proof:
Base case: for x=8, this is true  8 = 3(1)+5(1)
                   for  x=9, this is true  9 = 3(3)+5(0)
                   for  x=10, this is true 10 = 3(0)+5(2)
Inductive Step: assume it is true for x-3, i.e x-3 = 3a+5b
now we need to prove for x
x-3 = 3a+5b
=> x=3(a+1)+5b             Hence  Proved.

We can see more rigorous proves here: http://math.stackexchange.com/questions/481240/idea-of-the-proof-existence-of-a-b-so-that-any-integer-greater-than-8-3a

(I don't want to complicate this problem, but if one wonder why greater or equal to 8 length string can always be derived. Then, here is the proof.)
+1
This DFA will accept strings of length 14, 16 .. also right? But given RL cannot produce stings of length 14,16 .. so on. Am I missing something?
+2
@Nithish

3+3+3+5=14

3+5+5+3=16
+2
Yeah I missed that. So this DFA would accept string of any length greater than 8 right?
0
yeah
0
where are the transition on zeros. This is a DFA so there should be a dead or trap state to reject all the strings which are not in the language. Am I wrong?
0
and for 12???
0
This DFA will accept the string of length 17 but this language does not have one?Please help me with my doubt
0

Another way to prove that any length of string that is greater or equal to 8 can be generated with 3 or 5:

Proof: Clearly length 8(by taking one time 11111 and one time 111) and 9 can be generated(by taking three times 111).

Now lets prove that any length of string that is greater or equal to 10 can be generated as well.

Any length of string that is greater or equal to 10 can have 10*N+r number of 1s(where N is any integer  value and r is less than equal to 9(0<= r <=9)). 

Case when r=0: 10*N number of 1s can be generated by taking 11111  ---> 2N times.

Case when r=1: take  11111, 2*(N-1) times, now we are left with eleven 1s which can be generated by taking 111  two times and 11111 one time.

Example 1: 11111111111( Eleven 1s, length=11 --> 10*1+1, here r=1) can be generated by taking 11111 , 2(1-1)=0 times, 111 two times and finally 11111 one time.

11111111111----> 111 111 11111

Example 2: 111111111111111111111(21 ones)------> length=21= 10*2 +1

take 11111  2*(2-1)=2 times, then 111 two times and finally again 11111 one time

11111 11111 111 111 11111

Case when r=2: take  11111, 2*(N-1) times, now we are left with twelve 1s which can be generated by taking 111  four time.

Case when r=3: take  11111, 2*(N-1) times, now we are left with thirteen 1s which can be generated by taking 111  one time and 11111 two times.

Case when r=4: take  11111, 2*(N-1) times, now we are left with fourteen 1s which can be generated by taking 111  three times and 11111 one time.

Case when r=5: take  11111, 2*(N-1) times, now we are left with fifteen 1s which can be generated by taking 11111 three times(or 111 five times).

Case when r=6: take  11111, 2*(N-1) times, now we are left with sixteen 1s which can be generated by taking 111  two times and 11111 two times.

Case when r=7: take  11111, 2*(N-1) times, now we are left with seventeen 1s which can be generated by taking 111  four times and 11111 one time.

Case when r=8: take  11111, 2*(N-1) times, now we are left with eighteen 1s which can be generated by taking 111 six times.

Case when r=9: take  11111, 2*(N-1) times, now we are left with nineteen 1s which can be generated by taking 111  three times and 11111 two times.

 

 

+14 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.
answered by Boss (19.7k points)
0
why we did not considered dead state for transition on 0 here since 0 should not be accepted...
0
0 means null right? and null is accepted by this dfa. No?
0
I mean if our input alphabet={0,1} then 10 states would be required.......(since 0 from each state will go to dead state...)?
0
Why will 0 go to dead state? It is accepted by the dfa. look at my answer. It contains set of elements that are accepted by the dfa.
+2
@Gate-Keeda he is mentioning about 0 and not 1. If the language is over {0, 1} we must have an extra dead state. But since it is not mentioned in the question we can assume language is over {1} as 0 is not mentioned anywhere.
+1
I misinterpreted perhaps what he said. Thank you. :)
0
Generally we ignore dead/trapped states while counting number of states ..
+1
not for DFA.
+9 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 :

answered by Boss (13.6k points)
0
thanks  for your explanation .i had made a mistake.
0
My pleasure.
+3 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.

answered by Loyal (8.6k points)
+1 vote

he finite state automata is : DFAExplanation: 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 

answered by Loyal (8.6k points)
–3 votes

1 state in minimal state DFA if only 1 is given as the lone alphabet in the language .if any other alphabets are also given ,then the minimal DFA would have 2 states,one for accepting any number of 1's and other for rejecting other alphabets.

answered by Junior (731 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,528 questions
42,803 answers
121,625 comments
42,167 users