Regular Expressions
Regular expressions describe exactly the regular languages. They're built from ∅, ε and symbols using union (+), concatenation and Kleene star (*).
| Regular expression | Language |
|---|---|
| (0 + 1)* | All binary strings |
| (0 + 1)*01 | Strings ending in 01 |
| 0*10* | Exactly one 1 |
| (0 + 1)*00(0 + 1)* | Contains 00 |
| ((0 + 1)(0 + 1))* | Even length |
| (1 + 01)*(ε + 0) | No two consecutive 0s |
Useful Identities
∅ + R = R ∅R = R∅ = ∅ εR = Rε = R
ε* = ε ∅* = ε R + R = R
R*R* = R* (R*)* = R* RR* = R*R = R⁺
(P + Q)* = (P*Q*)* = (P* + Q*)* ε + RR* = R*Arden's Theorem
If P doesn't contain ε, the equation R = Q + RP has the unique solution R = QP*. It's used to convert a finite automaton into a regular expression.
DFA: q1 (start), q2 (final)
δ(q1, a) = q1, δ(q1, b) = q2, δ(q2, a) = q2, δ(q2, b) = q2
Equations:
q1 = ε + q1·a
q2 = q1·b + q2·a + q2·b
q1 = ε·a* = a* (Arden: Q = ε, P = a)
q2 = a*b + q2(a + b) ⇒ q2 = a*b(a + b)* (Arden)
RE = a*b(a + b)* (strings with at least one b)RE to ε-NFA (Thompson's Construction)
Build small NFAs for each symbol, then combine them: union adds a new start with ε-moves to both; concatenation links final to start with ε; star adds ε-loops back and an ε-bypass.
Track your progress through the Theory of Computation course