Identities Related to Regular Expressions
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 state that: “If P and Q are two regular expressions over , and if P does not contain , then the following equation in R given by R = Q + RP has an unique solution i.e., R = QP*.” That means, whenever we get any equation in the form of R = Q + RP, then we can directly replaced by R = QP*. So, here first we will prove that R = QP* is the solution of this equation and then we will also prove that it is the unique solution of this equation.
Comments
Post a Comment