The simplest family of languages – and correspondingly, the simplest kind of computing machine – deal with regular languages. A regular language is very limited: there’s no counting, no deep patterns. They really don’t have much in the way of computational power. But they’re still very useful – the ubiquitous regular expression libraries in most programming languages are just easy ways of using regular languages to decompose simple patterned inputs.

The regular languages can be described in three ways: as regular grammars; as regular expressions; or as a kind of computing machine called a finite state machine or finite state automaton.

We’ll start with the machines. For each regular language, you can define a simple finite state machine that will determine whether or not a particular string is in the language. In a finite state machine, the machine has a small piece of state – a single atomic value, called the state, and it’s allowed to look at exactly one character of input. It’s not allowed to sneak a peak ahead; it’s not allowed to look at any previous characters to see how it got into its current state.

Let’s get precise. A FSM can be described by a tuple: , where:

• is a set of symbols, called an alphabet;
• is a set of states;
• is a special distinguished state called the start-state or initial state;
• is a subset of the states called the final states; and
• is a transition relation which maps pairs of machine state and input symbol to target states. This relation defines how the machine actually works: if there is a relation , that means that when the machine is in state , and it sees an input symbol , it will transition to state .

The machine starts to look at an input string in state . For each symbol in the input string in sequence, it performs a single transition, consuming that input symbol. When it’s consumed every symbol in the input string, if it’s in a state that’s part of the set , then it accepts the string.

For example, we can create a machine which accepts strings that consist of any string containing at least one a, followed by at least one b. In tuple form, that would be (, , , , t = { , , , , , , , }). In graphic form:

In the picture, the initial state is marked with a big blue arrow, and the final states are outlined in green.

Let’s step through a couple of examples.

1. Suppose the input is “aaabb”. The machine starts in state . It consumes the first “a”, and follows the transition labelled “a” into state . The remaining input is “aabb”. It follows the transition from state labeled “a”, which again leads to state , leaving the remaining input a “abb”. It consumes another “a”, doing the same thing, leaving the remaining input “bb”. It consumes a “b”, following the transition labelled “b” to state , and leaving the remaining input as just “b”. Finally, it does the transition labeled from state , and again goes to state . The input is gone, and it’s in state . Since is one of the final states, the machine accepts the string.
2. Suppose the input is “baab”. The machine starts in . It consumes the first , which moves it to state . The rest of the characters get consumed one at a time, but all of the transitions from in this machine return to : it’s a dead end. Once it’s consumed all of the characters, it will still be in , so it won’t accept the string.
3. Suppose the input is the empty string. The machine starts in , and never runs any transitions at all, so it ends in state . Since isn’t a final state, it doesn’t accept the empty string.

When you look at this, it’s really a trivial machine. It seems like there’s very little that it can do. And yet, at least in theory, any computation that can be performed with a fixed, finite amount of state can be implemented with a machine this simple. Everything that I can do on the computer that I’m typing this on is doable using a finite state machine. It would have a huge number of states, and an insanely complex state transition function, but it would be doable.

Let’s move on to grammars. As I said in the last post, each of the Chomsky grammar levels can be characterized by some way of constraining the grammar. There are two versions of regular grammars, called right regular and left regular grammars. The idea of both is similar; we’ll use right-regular as an example.

• there is exactly one non-terminal on the left-hand side of the rule;
• There can at most one non-terminal symbol on the right-hand side of the rule;
• There can be at most one terminal symbol on the right-hand side of the rule
• If there’s both a non-terminal and a terminal symbol on the right-hand side of the rule, then the terminal will come before the non-terminal.

So, for example, the following are all valid right-regular grammar rules.(I’m writing terminals as boldface, and non-terminals as italics.)

But the following are not right regular:

• . (The non-terminal is in the middle of two terminals, not at the end.)
• . (The non-terminal is not at the end.)
• 

There’s a clear connection between the structure of a regular grammar, and a finite state machine. If you think of each non-terminal symbol as a state, each terminal symbol as an the label on a transition between states, and final states as states reached by a rule without a non-terminal on the right-hand side – you’ve pretty much got the a finite state machine. They’re really similar, and you can see how the regular grammar restrictions constrain the grammar to exactly the same languages that you can recognize with a finite state machine.

FSMs are great, but if you want to describe a regular language, you probably don’t want to write one down. And grammars aren’t the easiest way to write down a regular language: for something so simple, they’re very verbose and not particularly easy to read. That’s why we have a third way of describing regular grammars: regular expressions. Regular expressions are compact, easy to read, and there’s a pretty clear correspondence between a regular expression and the corresponding regular grammar.

A regular expression is:

A single character, e.g., “a”

This is a literal match: the language matched by a single character regular expression is exactly that character.

Concatenation

If and are regular expressions, then is a regular expression. The language matched by is the concatenation of a string matched by followed by a string matched by .

Alternation

Alternation describes a choice. If and are regular expressions, then is a regular expression, which matches anything matched by either or .

Repetition (aka Kleene closure)

If is a regular expression, then is a regular expression. matches any sequence of zero or more strings matched by concatenated together.

You can also use grouping, written using parens, so that you can have alternation between concatenated groups.

A few examples of regular expressions:

any string of any length made from the characters “a”, “b”, “c”, and “d”: “abcd”, “aaaa”, “ab”, “dabcbad”, etc.

a string of any length made of “a”s and “b”s, followed by a string of any length of “c”s and “d”s. “ababbbacdcdcccc”, “ab”, “b”, “c”, “cdcdddcc”, “ddcc”.

a string of any number of repetitions of “ab”, followed by any number of “c”s and “d”s. “ababababcccd”, “abcc”, “ab”, etc.

strings consisting of at least one A; followed any number of “b”s (including zero); followed by any number of repetitions of “cd”; followed by either a single “e” or a single “f”.