The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+30 votes

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

- $3$
- $5$
- $8$
- $9$

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

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

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?

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?

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.

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

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

I mean if our input alphabet={0,1} then 10 states would be required.......(since 0 from each state will go to dead state...)?

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.

+9 votes

DFA will be as :

+3 votes

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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 278
- Exam Queries 396
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 7

33,687 questions

40,230 answers

114,269 comments

38,799 users