Regular Expressions Notes & Formulas

1. Definition

A regular expression (RE) is a formal notation for describing regular languages using algebraic operations on alphabets.

2. Formal Definition (Very Important)

Base cases (over alphabet Σ):

• ∅ - empty language
• ε - language containing only empty string {ε}
• a (for each a ∈ Σ) - language {a}

Recursive cases: if R and S are regular expressions:

• R + S (or R|S) - union: L(R) ∪ L(S)
• RS (concatenation) - L(R)·L(S)
• R* (Kleene star) - L(R)*
• (R) - grouping

3. Operator Precedence

(high to low): * > concatenation > + (union)

• a+bc* = a + (b(c*))
• ab* ≠ (ab)*

4. Standard Regular Expressions (Very Important)

| Language | Regular Expression |
|---|---|
| All strings over {a,b} | (a+b)* |
| Strings starting with a | a(a+b)* |
| Strings ending with b | (a+b)b |
| Strings containing ab | (a+b)ab(a+b) |
| Even length strings | ((a+b)(a+b)) |
| Strings with even number of a's | (baba)b |
| No two consecutive a's | (b+ab)(a+ε) |
| Strings NOT containing aa | (b+ab)(ε+a) |

5. Algebraic Laws (Very Important)

• R + S = S + R (union commutative)
• (R+S)+T = R+(S+T) (associative)
• R·(S·T) = (R·S)·T (concatenation associative)
• R·(S+T) = RS + RT (distributive)
• R*(R*) = R* (idempotent)
• (R*)* = R*
• ε* = ε, ∅* = ε
• R·ε = ε·R = R (identity)
• R·∅ = ∅·R = ∅ (zero element)
• R + ∅ = R (identity for union)
• R + R = R (union idempotent)
• (ε + R)* = R*
• RR = R*

6. RE ↔ FA Conversion

RE to NFA (Thompson's construction):

• ∅ → NFA with no accepting path
• ε → two states with ε-transition
• a → two states with a-transition
• R+S, RS, R* → combine NFAs with ε-transitions

DFA to RE (State elimination):

• Generalized NFA (GNFA) with RE labels on transitions
• Eliminate states one by one, updating transitions with RE
• Final RE when reduced to start → accept state

7. GATE Trick

RE for "strings with even number of a's": b*(abab)* or (baba)b - both equivalent. Simplify using algebraic laws before constructing NFA. (R+ε)* = R* is a key identity. RE equivalence: two REs equivalent iff they describe same language (construct DFAs and check equivalence). L((a+b)(aa+bb)(a+b)) = strings containing aa or bb as substring.