0 votes 0 votes Can someone show how we can systematically come up with regular expression for language not containing string 101 on alphabet {0,1} by first creating DFA and then converting it to regular expression? Theory of Computation theory-of-computation regular-expression + – GateAspirant999 asked Jul 6, 2018 GateAspirant999 14.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes At first you make a DFA for this . After we can find regular expression . abhishekmehta4u answered Jul 6, 2018 abhishekmehta4u comment Share Follow See all 7 Comments See all 7 7 Comments reply MiNiPanda commented Jul 6, 2018 reply Follow Share From the third state can't we make a transition to the 2nd state on 0 without adding one extra state ? 0 votes 0 votes Shubham Shukla 6 commented Jul 6, 2018 reply Follow Share well in DFA for accepting 101 we can make transition of 0 from 3rd state to 1st state...so we will need 4 states only...dnn need that extra stage 0 votes 0 votes MiNiPanda commented Jul 6, 2018 reply Follow Share Yes sorry.. 1st state not 2nd.. 0 votes 0 votes Shubham Shukla 6 commented Jul 6, 2018 reply Follow Share @mini panda yes that can be done..! 0 votes 0 votes GateAspirant999 commented Jul 6, 2018 reply Follow Share well, I was also able to come up with the DFA, point was how do I reduce this DFA to regex. I have come up with following reduction of dfs to regex. Tell me if it looks correct: 1 votes 1 votes Shubham Shukla 6 commented Jul 7, 2018 reply Follow Share answer is correct..! 0 votes 0 votes rajatmyname commented Mar 13, 2019 reply Follow Share Can you please explain the way to get regular expression from dfa? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes (λ + 0)( 1+ 000* )(λ + 0) + 0*1*0* is this a possible regular exprssion?? please correct me if not. JAINchiNMay answered Oct 5, 2020 JAINchiNMay comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes After getting this Just Do complement of it. Amartya answered Jun 26, 2021 Amartya comment Share Follow See all 0 reply Please log in or register to add a comment.