edited by
3,344 views

4 Answers

1 votes
1 votes

The regular expression (1+1111)* matches any string consisting of any number of 1's and any number of substrings "1111".

Since the pattern "1111" can overlap with itself, there is no need to distinguish between different occurrences of "1111". Therefore, the minimal DFA for this regular expression has only one state, which is both the initial and final state.

In this state, any input symbol transitions to the same state, since any input symbol can be part of a "1111" substring.

0 votes
0 votes

 IT IS 1 STATE

I did by drawing ϵ-NFA and then converting it to nfa by ϵ closure rule ,my resulting nfa comprised of only one state.Bt even without all these we can see if there is one loop of 1 over the initial state which would be our final state even we can satisfy our regular expression.

But i am not confident.if i am wrong plz someone rectify me. 

0 votes
0 votes
You can Obtain This type of problems by simplifying the given equation

Let us Consider above equation as R=(R1+R2)* so this equation we can convert as some basics forms

R=(R1*+R2*)*

R=(R1+R2*)*

R=(R1*.R2*)*

let us take L=(1+1111)*as L=(R1+R2)*

from R1 we can get min length of strings are=0,1,2,3,4,5,6,...etc(all are multiple of 1)

from R2 we can get min length of string are =0,4,8,12,16 (all are multiple of 4)

by observing above min.length string from R1 you can Implement R2 (because R2 subset of R1 we can consider or GCD(R1,R2) is 1)

so With only R1 you can implement whole Language generated by (R1+R2)*

so the Languages is L=1*

so to construct L we need 1 min no of DFA's

Related questions

0 votes
0 votes
1 answer
2
srestha asked Oct 6, 2018
1,327 views
Number of $2$ state DFA with designated initial state can be constructed over alphabet $\sum_{.}^{.}=\left \{ 0,1 \right \}$ and that accept empty language $\Phi$ is____...
0 votes
0 votes
2 answers
3
rahul sharma 5 asked Nov 20, 2017
1,033 views
Consider the following NFA:-How many final states required in the equivalent DFA?
2 votes
2 votes
1 answer
4
rahul sharma 5 asked Nov 9, 2017
938 views
Minimum number of states in DFA where:, Number of a's and Number of b's are even and epsilon is not accepted.Langugae is defined over {a,b}