CSC448: Overview: Review of Regular Expressions [19/133]

A language is a set of strings over some alphabet.

Consider the following operations on languages over the same alphabet:

• The empty string: epsilon
• A symbol from the alphabet: a
• Union: r | s
• Concatenation: r s
• Iteration: r*

Regular expressions are a syntax for describing these operations.

See sections 3.1, 3.3, 3.5 of the Dragon book.