in Theory of Computation recategorized by
859 views
1 vote
1 vote

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)^{*}$
in Theory of Computation recategorized by
859 views

2 Comments

Option B is correct
1
1
Option B
0
0

1 Answer

3 votes
3 votes

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

Answer:

Related questions