GATE CSE 2006 | Question: 34

Question

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

• A. $3$
• B. $5$
• C. $8$
• D. $9$

Comments

After reading solution, I was like "F*** Awesome Question".

---

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.

Answer 1

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.

Comments

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

---

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?

---

@Nithish

3+3+3+5=14

3+5+5+3=16

---

Yeah I missed that. So this DFA would accept string of any length greater than 8 right?

---

yeah

---

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?

---

and for 12???

---

This DFA will accept the string of length 17 but this language does not have one?Please help me with my doubt

---

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.

---

if it isGREATER THAN 9, CAN WE WRITE AS 5a+4b?

---

@Sachin Mittal you always answer some of most difficult question, I wonder how you do that.

---

Since zero is not under consideration according to the RE, set of symbols of the language = {1}

---

How 14 one accepted

---

14 can be accepted by forming 9 using 3 times (111) and 1 time (11111) viz. 3*3 + 1*5 = 14.

---

This DFA accept all string which has length greater than 8 . But with the help of (111+11111)* we can't derive 13  1's so DFA should reject the string which has length 12

---

Why do you need 3 base case to prove it, cant we just do it like this:

let it be true for any x such that x = 3a +5b

then for x+1, we can write it as : 3a+5b+1
                                                    3a+5b+6-5
                                                    3(a+2) + 5(b-1)
                                                    3a’+5b’, thus proved by induction.

---

@Astha20 we can derive 13 by concatenating 3 1’s with 10 1’s(111 11111 11111)

---

@Omkar Gurav, 17 = 3+3+3+3+5 !

---

If you take any pair of prime numbers from 2,3,5,7 then after some particular number, there sum is able to generate any number. 

2&3 able to generate any number from 2 onwards
2&5 able to generate any number from 4 onwards
2&7 able to generate any number from 6 onwards
3&5 able to generate any number from 8 onwards
3&7 able to generate any number from 12 onwards
5&7 able to generate any number from 19 onwards

Note: I don’t have any formal proof, but I think for any two prime numbers after certain number onwards, there sum is able to generate all the numbers.

---

@Pratik2404 ! Awesome!   thank you!

---

I like to add on statement:
given co-prime positive integers n,m , every integer z greater than or equal to (n−1)(m−1) can be written in the form

z=an+bm

for non-negative integers a,b.

proof:https://math.stackexchange.com/questions/481240/idea-of-the-proof-existence-of-a-b-so-that-any-integer-greater-than-8-3a

---

3 and 5 can generate any number 8 onwards

3 + 5 --> 8 (nothing fancy!)

For 3k >= 9, I will prove that we can generate 3k+1 as well as 3k+2 for all k. That proves that we can generate any number because all numbers will belong to either 3k, 3k+1 or 3k+2

Now, let say, x = 3k (3k >= 9)

x + 1 = 3k +1 (+1 both sides)

= (k-3) 3 + [3 + 3 + 3 + 1] (rewriting in different way)

= (k-3) 3 + 10

10 can be generated easily by removing 111 three times and adding (11111) two times thus we can generate 3k+1 for any k >= 3

Similarly, for 3k+2,

3k + 2 = (k-1) 3 + 3 + 2

= (k-1) 3 + 5

So, we can easily generate 3k + 1 and 3k + 2 for every such k >= 3 easily

 I hope it helps.

Answer 2

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.

Comments

I misinterpreted perhaps what he said. Thank you. :)

---

Generally we ignore dead/trapped states while counting number of states ..

---

not for DFA.

Answer 3

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 :

Comments

thanks  for your explanation .i had made a mistake.

---

My pleasure.

Answer 4

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.