3 Regular Languages

In this lecture we will

1. introduce regular expressions, an alternative notation for specifying languages that are accepted by FSAs.

2. look a bit closer at the relation between regular expressions and FSAs and provide an algorithm for constructing FSAs from regular expressions.

3. learn about certain nice properties of regular languages (the languages characterized by regular expressions or FSAs) and see how to make use of these properties in an implementation.

• 3.1 Regular Languages and Relations
  • 3.1.1 FSAs, Regular Expressions, and Regular Languages
  • 3.1.2 Examples of Regular Expressions
  • 3.1.3 Definition of Regular Expressions
  • 3.1.4 Regular Expressions and FSAs
  • 3.1.5 From Regular Expressions to FSAs
  • 3.1.6 Regular Relations and Rewriting Rules

• 3.2 Properties of Regular Languages
  • 3.2.1 Concatenation, Kleene Closure and Union
  • 3.2.2 Intersection, Complementation
  • 3.2.3 The ``Pumping Lemma''

• 3.3 Implementing Operations on FSAs
  • 3.3.1 The scan-Predicate
  • 3.3.2 Implementation of scan/1
  • 3.3.3 scan_state/2
  • 3.3.4 Recursion
  • 3.3.5 Intersection
  • 3.3.6 Union

• 3.4 The Complete Code

• 3.5 Practical Session

• 3.6 Exercises

• 3.7 Further Reading