A DFA can be converted into a
RE by using the Arden
Arden
If P, Q, R are RE’s and P is
not NULL,
If R= Q + RP then,
R = QP*
This theorem can be proved in
2 ways
I)
Substitute R=QP* in R=Q+RP
R= Q + QP*P
= Q (ε + P*P) P*P=P+ (which means atleast 1 P has to be there)
= Q (ε + P+) Again ε + P+ means that
either nothing or atleast 1 P can come, which
means 0 or more P’s can come.
R = QP*
II)
Another way is to substitute
R=Q+RP in Q+RP and keep substituting it.
R=Q+RP
= Q + (Q+RP) P = Q+QP+RP2
= Q + QP+( Q + RP) P2
= Q +QP + QP + RP3
R = Q (ε + P +P2
+ P3 +…+Pi ) +RPi+1
R =
QP* RPi+1 is not included as string is
of
length
i
For
Example
Write the RE for the following DFA.
First create equations related to each state.
Write
a term for every incoming arrow.
On
the start state there is a compulsory term of ε as on the start state on a
nothing we go to the start state. q1 on a comes back to q1 and q2 on a b comes
to q1. Also the equation of the final state only in terms of a and b is the
final RE. So the equation for q1 is
q1
= ε +
q1.a + q2.b
Similarly
equations for q2 and q3 are
q2
= q2.b + q3.a + q1.a
q3=
q2.a
We
can write q2 = q1.a + q2. b +q3.a
Substitute
q3=q2. a in q2
q2=
q1.a +q2.b +q2.a.a
q2
= q1. a +q2 (b + a. a)
Using
Arden
R=
Q+RP è R=QP*
Here,
q1.a is Q
q2 is R
(b + a. a) is P
q2
= q1.a (b + a. a)*
Substitute
q2 = q1.a (b + a. a)* in q1 = ε + q1.a + q2.b
q1
= ε +
q1.a + (q1.a (b + a. a)*) b
q1
= ε +
q1 (a +a (b + a. a)*) b
Using
Arden
Q =
ε
R =
q1
P =
(a +a (b + a. a)*) b
q1=
ε. ((a
+a (b + a. a)*) b)*
q1
= ((a +a (b + a. a)*) b)*
Substitute
q1 = ((a +a (b + a. a)*) b)* in q2= q1.a (b + a. a)*
q2=
((a +a (b + a. a)*) b)*. a (b + a. a)*
Now
substitute q2= ((a +a (b + a. a)*) b)*. a (b + a. a)* in q3= q2.a
q3=
((a +a (b + a. a)*) b)*. a (b + a. a)*.a
This
is the final RE, as q3 is the final state and the expression is only in terms of
a and b.
Feel free to comment if you have any doubts.
Recommended articles:
Comments
Post a Comment