1 votes 1 votes can 0*1+1* generate 01 and 11 and 011? what would be the minimal dfa ? Theory of Computation theory-of-computation + – Abhishek Kumar 40 asked Aug 7, 2018 • edited Aug 7, 2018 by Abhishek Kumar 40 Abhishek Kumar 40 757 views answer comment Share Follow See all 18 Comments See all 18 18 Comments reply MiNiPanda commented Aug 7, 2018 reply Follow Share Yes.. 0 votes 0 votes Siddharth Bhardawaj commented Aug 7, 2018 i edited by Siddharth Bhardawaj Aug 7, 2018 reply Follow Share Yes it will generate 01 and 11. Check this 0*1 will give 01 and 1* will generate 11. 0 votes 0 votes MiNiPanda commented Aug 7, 2018 reply Follow Share 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 votes 0 votes Siddharth Bhardawaj commented Aug 7, 2018 i edited by Siddharth Bhardawaj Aug 7, 2018 reply Follow Share @MiniPanda Yes, you are correct... Thanks though for correcting me and I corrected my comment.... 0 votes 0 votes MiNiPanda commented Aug 7, 2018 reply Follow Share 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? 0 votes 0 votes Siddharth Bhardawaj commented Aug 7, 2018 reply Follow Share @MiniPanda Yes , you are correct. 1 votes 1 votes arvin commented Aug 8, 2018 reply Follow Share aint the dfa going to have 5states. 0 votes 0 votes Tesla! commented Aug 8, 2018 i edited by Tesla! Aug 8, 2018 reply Follow Share 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 votes 0 votes arvin commented Aug 8, 2018 reply Follow Share @tesla wont this dfa accepts 101 which is not in RE 0 votes 0 votes Tesla! commented Aug 8, 2018 reply Follow Share Yes, you are correct @arvin, let me correct it 0 votes 0 votes arvin commented Aug 8, 2018 reply Follow Share @tesla i think it will have 5states with 3 final states. 1 votes 1 votes MiNiPanda commented Aug 8, 2018 reply Follow Share I am getting 4 states but my transitions are different. 0 votes 0 votes arvin commented Aug 8, 2018 reply Follow Share @minipanda can u provide ur dfa 0 votes 0 votes MiNiPanda commented Aug 8, 2018 reply Follow Share 0 1 ->q0* q2 q1 q1* qdead q1 q2 q2 q1 qdead qdead qdead Is it accepting any invalid string? 0 votes 0 votes Tesla! commented Aug 8, 2018 reply Follow Share @MiNiPanda yes it accepts 011,0111,01111... and so on which are not part of the language. 0 votes 0 votes arvin commented Aug 8, 2018 reply Follow Share @minipanda yes dear i think it will accept 0111.... which is invalid. 0 votes 0 votes MiNiPanda commented Aug 8, 2018 reply Follow Share Yup right.. Thanks Tesla! and arvin 0 votes 0 votes arvin commented Aug 8, 2018 reply Follow Share dfa will look like this :p what i drew earlier 0 votes 0 votes Please log in or register to add a comment.