The Gateway to Computer Science Excellence
0 votes
in Theory of Computation by Active (2.5k points) | 653 views

3 Answers

+2 votes
(1+1111)* is same as 1*.  Single state DFA with same starting and final state.
by Boss (14.3k points)
0 votes


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. 

by Junior (777 points)
you`re right only 1 state req .
1 is correct answer but cudn't understand your method!

ok i am just trying to go from basics it would be easy for me even,

,at first draw the ϵ nfa .. if that is correct then apply ϵ closure procedure or any other way in any standard books to get ur nfa without ϵ. then you will find out that your resulting nfa is of  1 state and it has even just 1 alphabet acording to question that is 1. so its equivalent minimal dfa would be of 1 states and even your nfa witout ϵ would represent your dfa once you draw it(you can easily recognize it once you draw it eg state qn  with self loop of 1 over itself which is our nfa and even dfa as only one transition for 1).

but plz be careful to draw you ϵ nfa .. it is where we all make mistake .if the mistake is there, your procedure may be going in wrong way  and your answer may end up wrong

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




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
by Active (2.5k points)
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
50,737 questions
57,397 answers
105,456 users