The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
123 views

I tried applying a method where we write equation as state with incoming transition on given dfa -

q1 = $\epsilon$ + bq1+bq2

q2 = aq1+aq2

but then able to reach till this conclusion only:

q2 = ab*+aq2+abq2b*

How to solve further?

Here q1 is a start state.

in Theory of Computation by Active (3k points) | 123 views
+2

the way of writing eqn is wrong...

the eqn R = Q+RP, ===> R = QP* when P is free from ϵ

Q1 = ϵ + Q1 b + Q2 b  ====> Q1 = ( ϵ + Q2 b ) b*

Q2 = Q1.a + Q2.a = ( ϵ + Q2 b ) b* a + Q2 . a = b* a + Q2 . b . b* . a + Q2 . a

 = b* a + Q2 . ( b . b* . a + a ) = b* a + Q2 . ( b+ a + a ) = b* a + Q2 . ( b+ + ϵ ) a = b* a + Q2 . ( b* ) a .

∴ Q2 = b* a + Q2 . ( b* a ) ====> Q2 = b* a ( b*  a )*

only Q2 is the final state, RE = b* a ( b*  a )*

0
if it is multiple choice question, just check the each RE can deployed by the given FA or not?
0
yeah that was the reason I wasn't able to take common Q2 outside. Thanks Shaik
0

Kindly Tell me where I went wrong . Thanks 

+2

@Pawan Kumar 2

you got b* a ( a + $b^{+}$ a)* = b* a ( a + $b^{+}$ a)* = b* a (  ( ∈ + $b^{+}$ ) a )* = b* a ( $b^{*}$a )* 

Both are equivalent

 

Note that, For a language may be more than one RE exist !

0

Thanks for confirming

brother

0
That also given in Peter Linz book

Please log in or register to answer this question.

Related questions

+2 votes
4 answers
5
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
49,830 questions
54,807 answers
189,530 comments
80,840 users