864 views

Let $P, Q, R$ be a regular expression over $\Sigma$. If $P$ does not contain null string, then $R=Q+RP$ has a unique solution ___________ .

1. $Q^{*}P$
2. $QP^{*}$
3. $Q^{*}P^{*}$
4. $\left ( P^{*}O^{*} \right)^{*}$

Option B is correct
Option B

According to arden's theorem, we can directly find the answer is QP*
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+RP^{2}$
When we put the value of $R$ recursively again and again, we get the following equation:
$R=Q+QP+QP^{2}+QP^{3}....$
$R=Q(\epsilon +P+P^{2}+P^{3}+....)$
$R=QP^{*} [ P^{*} = (\epsilon +P+P^{2}+P^{3}+....)]$

1 vote