The Gateway to Computer Science Excellence
0 votes
710 views

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?

in Theory of Computation by Boss (18.2k points) | 710 views
+1

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.

0
Please specify the steps you did.
0

 Regular expression for above DFA-(a(ba)*(bb+a))+(b(b+a(ba)*(a+bb)))

0
@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
@deepak
ba(ba)*a is present in the language. It can't be generated by your regular language.
0

@ 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

@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

@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
@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
Thanks I got it.

1 Answer

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)
by Junior (551 points)
0
Can we write r= aa+bb+a(ba)*bb
0
yes we can write R.E=bb+aa+a(ba)*bb
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,459 answers
195,378 comments
100,272 users