Question

P, O, R be regular expression over ∑, P is not ε, then R=Q + RP has a unique solution:

(a) Q*P

(b) QP*

(c) Q*P*

(d) (P*O*)*

I got this question during an interview for a job.

Asked question is from Operators of Regular Expression in chapter Regular Expressions and Languages of Automata Theory

Answer 1

Correct answer is (b) QP*

To elaborate: The given statement is the Arden’s Theorem and it tends to have a unique solution as QP*.

Let P and Q be regular expressions,

R=Q+RP

R=Q+(Q+RP) P

R=Q+((Q+RP) +RP) +P=Q+QP+RPP+RPP=Q+QP+(Q+RP) PP+(Q+RP) PP=Q+QP+QPP+RPPP+QPP+RPPP,

If we do this recursively, we get:

R= QP*