5,078 views
1 votes
1 votes
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*)*

3 Answers

4 votes
4 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^{*}$
3 votes
3 votes

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.

Related questions

0 votes
0 votes
1 answer
1
rapidxy asked Dec 14, 2021
379 views
Let $C(n,r)= \binom{n}{r}$.The value of $\sum_{k=0}^{20}(2k+1)C(41,2k+1)$ is :A)40(2)^40 B)40(2)^39C)41(2)^40D)41(2)^39
1 votes
1 votes
0 answers
2
rsansiya111 asked Dec 6, 2021
392 views
If a hash table is implemented asa search tree, the expected time required to enter n names and make m searches is proportional to: (n + m) $log_{2} n$(n + m) $log_{2} m$...
0 votes
0 votes
0 answers
3
rsansiya111 asked Dec 6, 2021
183 views
Consider a relation R with attributes {A,B,C} and functional dependency set S ={A → B, A → C}. Then relation R can be decomposed into two relations: R1{A,B} AND R2{A...
0 votes
0 votes
1 answer
4
rsansiya111 asked Dec 6, 2021
705 views
Total number of nodes at the nth level of a full binary tree can be given as___________. 2n + 1$2n^{2}$2^n2n – 1