Is it b?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 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*)*

1)Q*P

2)QP*

3) Q*P*

4)(P*Q*)*

+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^{*}$

$=Q+QP+QP^{2}+RP^{3}=Q(\epsilon +P+PP+PPP+...)=QP^{*}$

+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 + QP^{2} + QP^{3}…..

R = Q (ε + P + P^{2} + P^{3} + …. )

R = QP* [As P* represents (ε + P + P2 + P3 + ….) ]

Hence, proved.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,751 questions

46,767 answers

140,662 comments

58,537 users