+1 vote
82 views
can 0*1+1* generate 01 and 11 and 011?

what would be the minimal dfa ?
edited | 82 views
0
Yes..
0
Yes it will generate 01 and 11.

Check this 0*1 will give 01 and 1* will generate 11.
0

Siddharth Bhardawaj  I agree with you on the first part but why 1+1* to generate 11? Only 1* is enough to generate 11 right?

0
@MiniPanda
Yes, you are correct... Thanks though for correcting me and I corrected my comment....
0

1+1* means 1 + {epsilon, 1,11,111...}. Here the bold 1 doesn't have any contribution in generating 11. That is why i thought it isn't necessary to mention that 1 explicitly. Am i wrong?

+1
@MiniPanda

Yes , you are correct.
0
aint the dfa going to have 5states.
0

yes it can generate 01 and 11, but not 011

and DFA will be of 5 state

let 5 state be q0,q1,q2,q3,qd

 0 1 $\rightarrow$q0* q1 q2 q1 q1 q3 q2* qd q2 q3* qd qd qd qd qd

qd refers to dead state

0
@tesla wont this dfa accepts 101 which is not in RE
0

Yes, you are correct @arvin, let me correct it

+1
@tesla i think it will have 5states with 3 final states.
0
I am getting 4 states but my transitions are different.
0
@minipanda can u provide ur dfa
0
 0 1 ->q0* q2 q1 q1* qdead q1 q2 q2 q1 qdead qdead qdead

Is it accepting any invalid string?

0

@MiNiPanda yes it accepts 011,0111,01111... and so on which are not part of the language.

0
@minipanda yes dear i think it will accept 0111.... which is invalid.
0
Yup right.. Thanks  Tesla! and  arvin
0

dfa will look like this :p what i drew earlier

+1 vote
1
2