6.5k 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$
edited | 6.5k views
+1
After reading solution, I was like "F*** Awesome Question".
0

Note: The answer is 9 not because there are 9 states in the DFA. It is 9 because 9 is the the minimum number of states in any DFA accepting the language. That means, you need to show that this DFA is not just any DFA, but the minimum DFA, that is, this DFA cannot be minimized further (There are no unreachable states, and each state is distinguishable from every other state so no two states can be merged together).

Watch this video if you don't know how to minimize a DFA.

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.

edited by
+25
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
+1
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.

0
if it isGREATER THAN 9, CAN WE WRITE AS 5a+4b?
+3
@Sachin Mittal you always answer some of most difficult question, I wonder how you do that.
0
Since zero is not under consideration according to the RE, set of symbols of the language = {1}
0
How 14 one accepted
0
14 can be accepted by forming 9 using 3 times (111) and 1 time (11111) viz. 3*3 + 1*5 = 14.
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.
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.
+3
@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 ..
+2
not for DFA.

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 :

0
0
My pleasure.

he finite state automata is :

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.

+1 vote

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

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.

1
2