ARDEN'S THEOREM FOR REGULAR EXPRESSIONS
Identities for Regular Expression:- Given R, P, L, Q as regular expressions, the following identities hold β β
* = Ξ΅ Ξ΅* = Ξ΅ RR* = R*R R*R* = R* (R*)* = R* RR* = R*R (PQ)*P =P(QP)* (a+b)* = (a*b*)* = (a*+b*)* = (a+b*)* = a*(ba*)* R + β
= β
+ R = R (The identity for union) R Ξ΅ = Ξ΅ R = R (The identity for concatenation) β
L = L β
= β
(The annihilator for concatenation) R + R = R (Idempotent law) L (M + N) = LM + LN (Left distributive law) (M + N) L = ML + NL (Right distributive law) Ξ΅ + RR* = Ξ΅ + R*R = R* Arden's Theorem:- In order to find out a regular expression of a Finite Automaton, we use Ardenβs Theorem along with the properties of regular expressions. 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 + ...
Comments
Post a Comment