An important category of languages is the regular languages. These can be characterised in a variety of ways, via regular grammars, finite state automata, regular expressions, or syntactic monoids. It’s important to understand all of these points of view because often a problem which is hard to solve using one description is easy in another.
To simplify things all of our examples in this chapter will be
languages where the tokens are single characters and we’ll write lists
of tokens as strings. When writing grammars each terminal symbol will
have only a single token, i.e. character, and will be denoted by that
character. The characters :, " and
| which have a special meaning in our language for
describing languages, will not be tokens in any of our example
languages, nor will any whitespace characters. Non-terminal symbols will
always be denoted by a string more than one character long. These aren’t
limitations imposed by the theory, just ways of making the examples
easier for you to read.
List of characters are strings. Because all tokens in our examples are characters all lists of tokens are strings. Strings are more familiar than lists of tokens so I’ll often refer to them as strings when doing examples. I may occasionally make the mistake of referring to strings rather than lists of tokens in the general theory as well.