Basic Definitions

Alphabet and Regular Expressions

• Alphabet ($\Sigma$): A finite set of symbols
• Regular Expression: Built from alphabet symbols using:
  • Union ($+$): $r_1 + r_2$ matches either $r_1$ or $r_2$
  • Concatenation ($\cdot$): $r_1 \cdot r_2$ matches $r_1$ followed by $r_2$
  • Kleene Star ($*$): $r^*$ matches zero or more repetitions of $r$

Formal Definition

A regular expression over alphabet $\Sigma$ is defined recursively:

1. Base Cases:

   • $\emptyset$ is a regular expression denoting the empty language
   • $\epsilon$ is a regular expression denoting $\{\epsilon\}$
   • For each $a \in \Sigma$, $a$ is a regular expression denoting $\{a\}$

2. Inductive Cases:

   • If $r_1$ and $r_2$ are regular expressions:
     • $(r_1 + r_2)$ is a regular expression
     • $(r_1 \cdot r_2)$ is a regular expression
     • $(r_1^*)$ is a regular expression

Precedence Rules

When parentheses are omitted, the following precedence applies (highest to lowest):

1. Kleene Star ($*$)
2. Concatenation ($\cdot$)
3. Union ($+$)

Tips

Always use parentheses to clarify precedence when combining operators

Examples

Simple Regular Expressions

Regular Expression	Language Description	Example Strings
$a$	Single 'a'	"a"
$a + b$	'a' or 'b'	"a", "b"
$a \cdot b$	'a' followed by 'b'	"ab"
$a^*$	Zero or more 'a's	"", "a", "aa", "aaa", ...
$(a + b)^*$	Any combination of 'a' and 'b'	"", "a", "b", "aa", "ab", "ba", "bb", ...

More Complex Examples

Regular Expression: $(a + b)^* \cdot a \cdot (a + b)^*$

This describes all strings over $\{a, b\}$ that contain at least one 'a'.

1. $(a + b)^*$ matches any prefix (including empty)
2. $a$ matches exactly one 'a'
3. $(a + b)^*$ matches any suffix (including empty)

Fundamental Properties

Union Properties

• Commutative: $r_1 + r_2 = r_2 + r_1$
• Associative: $(r_1 + r_2) + r_3 = r_1 + (r_2 + r_3)$
• Identity: $r + \emptyset = r$

Concatenation Properties

• Associative: $(r_1 \cdot r_2) \cdot r_3 = r_1 \cdot (r_2 \cdot r_3)$
• Identity: $r \cdot \epsilon = \epsilon \cdot r = r$
• Annihilator: $r \cdot \emptyset = \emptyset \cdot r = \emptyset$

Kleene Star Properties

• Basic: $\emptyset^* = \epsilon^* = \epsilon$
• Iteration: $(r^*)^* = r^*$
• Closure: $\epsilon + r \cdot r^* = r^*$

Language Operations

Important Language Classes

1. Finite Languages: Can be expressed using union

   • $L = \{w_1, w_2, ..., w_n\} = w_1 + w_2 + ... + w_n$

2. Infinite Languages: Require Kleene star

   • $L = \{a^n \mid n \geq 0\} = a^*$
   • $L = \{a^n \mid n \geq 1\} = a \cdot a^*$

3. Concatenation of Languages

   • If $L_1 = \{ab, a\}$ and $L_2 = \{b, bc\}$
   • Then $L_1 \cdot L_2 = \{abb, abbc, ab, abc\}$

Practical Considerations

Shorthand Notation

In practice, we often use:

• $ab$ instead of $a \cdot b$
• $r^+$ for one or more repetitions: $r^+ = r \cdot r^*$
• $r?$ for optional elements: $r? = \epsilon + r$

Common Patterns

Pattern	Meaning	Example
$a^*$	Zero or more 'a's	"", "a", "aa", ...
$a^+$	One or more 'a's	"a", "aa", "aaa", ...
$a?$	Zero or one 'a'	"", "a"
$a^n$	Exactly n 'a's	"a" (when n=1), "aa" (when n=2)

Summary

Regular expressions provide a powerful and concise way to describe patterns in strings. By combining the three fundamental operations (union, concatenation, and Kleene star), we can express both finite and infinite languages with remarkable precision.

The key insight is that regular expressions correspond to the class of regular languages, which can be recognized by finite automata, forming an important equivalence in automata theory.

Changelog

8/8/25, 4:17 AM

View All Changelog

• 2aa48-web-deploy(Auto): Update base URL for web-pages branchon 8/8/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)