1 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 ___________ . $Q^{*}P$ $QP^{*}$ $Q^{*}P^{*}$ $\left ( P^{*}O^{*} \right)^{*}$ Theory of Computation nielit2017dec-assistanta theory-of-computation regular-expression + – admin 1.8k views answer comment Share Follow Print See all 2 Comments 2 2 Comments reply Hradesh patel commented Mar 31, 2020 reply Follow flag Option B is correct 1 1 replyShare chinmayc commented Nov 13, 2021 reply Follow flag Option B 0 0 replyShare Please log in or register to add a comment.
5 5 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}+....)] $ Mohit Kumar 6 answered May 20, 2020 Mohit Kumar 6 comment Share Follow 0 reply Please log in or register to add a comment.
