The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
71 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*)*
asked in Theory of Computation by (13 points) | 71 views
0
Is it b?
0
arden's theorem ans is B.
0
2nd option

3 Answers

+2 votes
$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^{*}$
answered by Active (2.2k points)
+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.

answered by Boss (20.7k points)
0 votes
Ardens theorem: (b) QP*
answered by Active (1.4k points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,235 questions
49,717 answers
163,877 comments
65,834 users