84 views
Let P,Q,R be a regular expression over Σ. If P does not contain null string ,then R=Q+RP, has a unique solution

1)Q*P

2)QP*

3) Q*P*

4)(P*Q*)*
0
Is it b?
0
arden's theorem ans is B.
0
2nd option

$R=Q+RP=Q+(Q+RP).P=Q+QP+RP^{2}=Q+QP+(Q+RP)P^{2}$

$=Q+QP+QP^{2}+RP^{3}=Q(\epsilon +P+PP+PPP+...)=QP^{*}$
+1 vote

Arden's theorem Statement −

Let P and Q be two regular expressions.

If P does not contain null string, then R = Q + RP has a unique solution that is R = QP*

Proof −

R = Q + (Q + RP)P [After putting the value R = Q + RP]

= Q + QP + RPP

When we put the value of R recursively again and again, we get the following equation −

R = Q + QP + QP2 + QP3…..

R = Q (ε + P + P2 + P3 + …. )

R = QP* [As P* represents (ε + P + P2 + P3 + ….) ]

Hence, proved.

Ardens theorem: (b) QP*

1
2