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.0k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Hemant Parihar commented Jul 1, 2017 i edited by Hemant Parihar Jul 5, 2017 reply Follow Share b(ab)*b and ba(ba)*a are accepted by the language but not your regular expression. The Regular expression I'm getting is (a+ba)(ba)*(bb+a) + bb. PS : Also (b + ab)(ab)*(b + aa) + aa. 1 votes 1 votes Shubhanshu commented Jul 1, 2017 reply Follow Share Please specify the steps you did. 0 votes 0 votes Deepak Kumar 12 commented Jul 3, 2017 i edited by Deepak Kumar 12 Jul 3, 2017 reply Follow Share Regular expression for above DFA-(a(ba)*(bb+a))+(b(b+a(ba)*(a+bb))) 0 votes 0 votes AnilGoudar commented Jul 3, 2017 reply Follow Share @Deepak, the RE generates ba , which is not in Language accepted by DFA. Please correct me if iam wrong RE : a(ba)*bb + bb + baa + abb + a(a+baa) 0 votes 0 votes Hemant Parihar commented Jul 3, 2017 reply Follow Share @deepak ba(ba)*a is present in the language. It can't be generated by your regular language. 0 votes 0 votes Deepak Kumar 12 commented Jul 3, 2017 i edited by Deepak Kumar 12 Jul 3, 2017 reply Follow Share @ Hemant yes ,for previous RE can't generated like baa... Modified RE-(a(ba)*(bb+a))+(b(b+a(ba)*(a+bb))) This RE is generated strings like- abb,ababababb,aa,abaa,abababaa....... bb,babb,bababb,bababababb,baa,babaa.... . 0 votes 0 votes Deepak Kumar 12 commented Jul 3, 2017 reply Follow Share @AnilGoduar Yes I am agree with your point. yes ,for previous RE can't generated like baa... Modified RE-(a(ba)*(bb+a))+(b(b+a(ba)*(a+bb))) This RE is generated strings like- abb,ababababb,aa,abaa,abababaa....... bb,babb,bababb,bababababb,baa,babaa.... Correct me If I am wrong. 0 votes 0 votes 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.