0 votes 0 votes Consider the given dfa What is the regular expression of the given dfa? I am getting :- a(ba)*bb + a(ba)*a + bb Is it correct or not? Theory of Computation theory-of-computation finite-automata regular-expression + – Shubhanshu asked Jul 1, 2017 Shubhanshu 3.1k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments manish.anand commented Jul 5, 2017 reply Follow Share @Hemant I also got one of the regular expression as (ab+b)(ab)*b+aa but the other one that I got is a(ba)*(a+bb)+bb and is accepting every string accepted by DFA. 0 votes 0 votes Hemant Parihar commented Jul 5, 2017 reply Follow Share @manish I added my comment. (ab + b)(ab)*b + aa is wrong because baa is present in the language but it can't be produced by this regular expression. Also your a(ba)*(a+bb) + bb is not generating baa. I used state elimination method to give the regular expression. 0 votes 0 votes manish.anand commented Jul 5, 2017 reply Follow Share Thanks I got it. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes At the initial state, we can either scan an 'a' or scan a 'b' . So we have two paths to follow : If we scan an 'a', RE will be a(ba)*(a+bb) If we scan a 'b' RE will be b(ab)*(b+aa) So final RE = a(ba)*(a+bb) + b(ab)*(b+aa) Udit Gupta 1 answered Sep 16, 2017 Udit Gupta 1 comment Share Follow See all 2 Comments See all 2 2 Comments reply Ashwani Kumar 2 commented Sep 16, 2017 reply Follow Share Can we write r= aa+bb+a(ba)*bb 0 votes 0 votes BASANT KUMAR commented Aug 17, 2019 reply Follow Share yes we can write R.E=bb+aa+a(ba)*bb 0 votes 0 votes Please log in or register to add a comment.