0 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 4.4k views answer comment Share Follow Print See all 10 Comments 10 10 Comments reply Hemant Parihar commented Jul 1, 2017 i edited by Hemant Parihar Jul 5, 2017 reply Follow flag 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 1 replyShare Shubhanshu commented Jul 1, 2017 reply Follow flag Please specify the steps you did. 0 0 replyShare Deepak Kumar 12 commented Jul 3, 2017 i edited by Deepak Kumar 12 Jul 3, 2017 reply Follow flag Regular expression for above DFA-(a(ba)*(bb+a))+(b(b+a(ba)*(a+bb))) 0 0 replyShare AnilGoudar commented Jul 3, 2017 reply Follow flag @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 0 replyShare Hemant Parihar commented Jul 3, 2017 reply Follow flag @deepak ba(ba)*a is present in the language. It can't be generated by your regular language. 0 0 replyShare Deepak Kumar 12 commented Jul 3, 2017 i edited by Deepak Kumar 12 Jul 3, 2017 reply Follow flag @ 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 0 replyShare Deepak Kumar 12 commented Jul 3, 2017 reply Follow flag @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 0 replyShare manish.anand commented Jul 5, 2017 reply Follow flag @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 0 replyShare Hemant Parihar commented Jul 5, 2017 reply Follow flag @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 0 replyShare manish.anand commented Jul 5, 2017 reply Follow flag Thanks I got it. 0 0 replyShare Please log in or register to add a comment.
0 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 2 2 Comments reply Ashwani Kumar 2 commented Sep 16, 2017 reply Follow flag Can we write r= aa+bb+a(ba)*bb 0 0 replyShare BASANT KUMAR commented Aug 17, 2019 reply Follow flag yes we can write R.E=bb+aa+a(ba)*bb 0 0 replyShare Please log in or register to add a comment.
