Regular Expressions

 

🔶 What Are Regular Expressions?

Regular expressions (RE) are formulas used to describe regular languages.

They serve as a compact and symbolic way to represent patterns that finite automata can recognize.

---

🔷 Formal Definition of Regular Expressions

Let Σ be an alphabet (a finite set of symbols).
The set of regular expressions over Σ is defined recursively as follows:

Basic Rules (Base cases):

1. ∅ is a regular expression — denotes the empty language (no strings).

2. ε is a regular expression — denotes the language {ε} (only the empty string).

3. a, where a ∈ Σ, is a regular expression — denotes the language {a}.

Recursive Rules (Building larger expressions):

If r and s are regular expressions representing languages L(r) and L(s), then:

1. (r + s) is a regular expression — union:

   L(r + s) = L(r) ∪ L(s)

2. (rs) is a regular expression — concatenation:

   L(rs) = L(r) ⋅ L(s)

3. (r*) is a regular expression — Kleene star (zero or more repetitions):

   L(r*) = (L(r))*

---

🔶 Examples

Regular Expression	Describes language…
a	{a}
a + b	{a, b}
ab	{ab}
a*	{ε, a, aa, aaa, ...}
(a + b)*	All strings over {a, b}, including ε
a*b	All strings with zero or more a’s followed by a single b
(ab)*	{ε, ab, abab, ababab, ...}

---

🔷 How to Build Regular Expressions

When constructing a regular expression for a given language:

🧩 Step 1: Understand the Pattern

• What kinds of strings should be accepted?

• What do they have in common?

🧰 Step 2: Use Building Blocks

Use the base rules and combine them using:

• + for choice (union)

• concatenation

• * for repetition

✅ Step 3: Apply Grouping

Use parentheses to control grouping and precedence.

---

🧪 Example: Build a regular expression for

All strings over {0,1} that end in 01

• All prefixes can be any combination of 0 and 1: (0 + 1)*

• Ends in 01

• So, RE: (0 + 1)*01

---

🔶 Why Are Regular Expressions Important?

• They describe the same class of languages as finite automata.

• Can be converted into NFA (via standard constructions).

• The main uses of regular expressions in TOC are

• Pattern Recognition: Represent patterns that can be recognized by finite automata (DFA and NFA).
• Compiler Design: Used in lexical analysis to tokenize input strings during compilation.
• Automata Conversion: Enable conversion between regular expressions and finite automata for language recognition.
• Theoretical Analysis: Help analyze and prove properties of languages within formal language theory.