  This report is mostly written for educational purposes. It is meant as a self
contained introduction to regular languages, regular expressions, and regular
expression matching by using Brzozowski derivatives. As such it is mostly based
on the work by Brzozowski[4] and Owens et al.[12] The language basics material
have been inspired by books[2] and web material[16].
  Chapter 1 introduces the fundamental concepts of formal languages, as well as
the idea of string derivatives. In chapter 2 we define the class of regular
languages, and further develops the theory of derivatives for that class. We
use derivatives to prove the Myhill-Nerod theorem, the Pumping lemma, and the
closure of regular languages under all Boolean connectives. In chapter 3 we
introduce regular expressions and regular expression matching. Chapter 4
connects the theory of regular languages and derivatives with that of finite
automata. Chapter 5 looks at the concept of anchors, and how this can be
incorporated into a matcher based on derivatives. Chapter 6 discusses
submatching using derivatives with an approach inspired by Laurikari and his
work on tagged transitions[11]. This is the part we consider as our main
contribution to the field. In the last chapter, chapter 7, we summarize by
giving a regular expression matching algorithm using the previously discussed
techniques. We also discuss related work by others.
