NIELIT 2017 DEC Scientific Assistant A - Section B: 19

Question

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 ___________ .

• A. $Q^{*}P$
• B. $QP^{*}$
• C. $Q^{*}P^{*}$
• D. $\left ( P^{*}O^{*} \right)^{*}$

Comments

Option B is correct

---

Option B

Answer 1

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}+....)] $