Overview

In this lesson, we'll learn a little about the connection between regular expessions and state machines. You'll explore this topic in much more depth in LING 538.

Outcomes

After completing this lesson, you'll be able to …

• translate a simple state machine into a regular expression
• translate a simple regular expression into a state machine
• explain transitions
• explain final states

Background

Regular languages and regular expressions

As mentioned in our introduction to regexes, regular expressions were first developed as a way of describing regular languages in formal language theory. Regular languages are the simplest type of language¹ in the Chomsky heirarchy. You'll learn all about regular languages and formal language theory in LING 539. In this lesson, we're simply going to look at an alterative way of representing a regular expression using a finite state machine (FSM).

FSMs and regular expressions

There are several subtypes of finite state machines (FSMs)² (deterministic, non-deterministic, etc.). For the purposes of this introduction, we won't explore these different types, but instead look at them generally.

Finite state machines are defined by five things:

• $Q$: a finite set of states (ex. ${q1, q2}$)
• $\Sigma$³: a finite set of input symbols
• $\delta$⁴: a transition function that tells how to move from one state to another by means of reading a symbol from our alphabet $\Sigma$
• $\delta : Q \times \Sigma \rightarrow Q$
• $q_{0}$: our start state
• $F$: a set of accept aka terminal aka final states (these are a subset of $Q$)

❗ Every finite state machine can be represented using an equivalent regular expression.

• Equivalent here means that both the regular expression and the finite state machine accept exactly the same set of strings.

Like a regular expression, we can think of a state machine as a validator/acceptor/recognizer of strings. Imagine we wanted to match the string abc. We can represent a language containing only the string abc with a regular expression:

abc

Alternatively, we can use a state machine:

The regular expression abc is equivalent to the state machine depicted above. Both the regular expression and the state machine accept exactly the same set of strings:

$L = \{\text{abc}\}$

The circles in our FSM represent its states and the lines between them represent valid transitions. We start in the state marked with an S:

In our little language, the only character that can start a string is a:

$L = \{\mathbf{a}\text{bc}\}$

This is represented by the following transition:

Reading or observing an a takes us from our start state, $S$, to a new state called $q_1$. Next, we read a b. This takes us to a new state, $q_2$:

From $q_2$, there is only one possible transition: $q_2 \rightarrow q_3$ by means of reading a c:

Notice anything different about $q_3$ in the example above?

The concentric circle indicates that this is a terminal⁵ state.

If we end up in this state and we've read off all of the characters for the string we're testing, that string is accepted by this state machine and is therefore part of the language represented by the machine.

Let's extend our language so that it includes the following strings:

abc
aabc

Alternatively, we can write it in the following way:

$L = \{\text{abc}, \text{aabc}\}$

Here is a deterministic finite state machine that defines our language, $L$:

We still have a single terminal state, $q_4$, but now there are two possible paths to $q_4$:

• $S \rightarrow q_1 \rightarrow q_2 \rightarrow q_3 \rightarrow q_4$
• $S \rightarrow q_1 \rightarrow q_3 \rightarrow q_4$

Ok. Let's look at one last example. What if our language allows an unlimited number of repetitions of a?

$L = \{\text{abc}, \text{aabc}, \text{aaabc}, \text{aaaaabc}, \ldots \}$

Can we represent such a string of infinite length with a finite number of states? Absa-loop-ley!

Using a loop mechanism, every subsequent a that we read will lead us right back to $q_1$:

The only way to leave $q_1$ for another state is to read off a b:

The strings accepted by our language all end with a c. We need one last state:

This state machine accepts the following language:

$L = \{\text{abc}, \text{aabc}, \text{aaabc}, \text{aaaaabc}, \ldots \}$

Try running a few example strings through to test that this is indeed the case.

Conversion

Regular expression $\rightarrow$ FSM

One intuitive way of creating a state machine from a regular expression is to enumerate the strings matched by the regular expression. For example, take the following expression:

a[bc]d

Let's list the strings it will match:

abd
acd

To create an equivalent finite state machine, we need to ensure that our FSM accepts exactly the same strings (no additions allowed!):

$L = \{\text{abd}, \text{acd}\}$

In this case, all strings accepted by our regular expression start with a. That means our start state in our state machine will have exactly one outgoing transition with the label a:

From there we can move to the next state by reading either a b or a c:

From this next position, $q_{2}$, we can only read a d. Let's add another state:

The strings that comprise our language all end with d. To accept such strings, $q_3$ must be a terminal state:

If we wanted to write a regular expression corresponding to this state machine, we can create one incrementally by reading off the transitions:

Based on that transition, our regular expression so far is a.

From $q_1$, two transitions are possible:

Our regular expression is now a(b|c).

Our only remaining transition is $q_{2} \rightarrow q_{3}$ which is traversed by reading a d:

Our final expression is thus a(b|c)d.

Finite state machine $\rightarrow$ regular expression

Every finite state machine has an equivalent regular expression, but how do we generate that regular expression?

Let's examine one algorithm for doing so…

We'll generate a regular expression for each state and then concatenate the expressions.

Let's look at an example:

We'll start by composing a series of series of state equations taht list the incoming transitions for each state:

• $q_{0}$ = $\epsilon$
• $q_{1}$ = $q_{0}\text{a}$
• $q_{2}$ = $q_{1}(\text{b}|\text{c})$
• $q_{3}$ = $q_{2}\text{d}$

Notes:

• $q_{0}$ refers to our start state $S$.

• $\epsilon$ (epsilon) corresponds to an empty string.

For states with multiple incoming transitions, we'll treat them as a disjunction.

To construct our regular expression, we need to subtitute in the values for the referenced states until we end up with a single regex corresponding to each terminal state:

$q_{1} = q_{0}a = \epsilon \text{a} = \text{a}$

We end up with the following for $q_{1}$:

$\mathbf{q_{1}} = \mathbf{a}$

Now let's expand the equation for $q_{2}$ by substituting the expanded form of $q_{1}$:

$q_{2} = q_{1}(\text{b}|\text{c}) = \text{a}(\text{b}|\text{c})$

We end up with the following for $q_{2}$:

$\mathbf{q_{2}} = \mathbf{a(b|c)}$

Finally, we'll expand $q_{3}$ by substituting our expanded $q_{2}$:

$q_{3} = q_{2}\text{d} = \text{a}(\text{b}|\text{c})\text{d}$

We end up with the following for $q_{3}$:

$\mathbf{q_{3}} = \mathbf{\text{a}(\text{b}|\text{c})\text{d}}$

Since $\mathbf{q_{3}}$ is our terminal state, our regular expression is a(b|c)d.

If we had more than one terminal state, our final expression would be a disjunction of the regular expression for each terminal state.

This "one simple trick" is an application of Arden's theorem.

Next steps

You've had a taste of representing regular expressions as finite state machines. Aside from exploring the connection to formal language theory, using a state machine to develop a regular expression can sometimes make debugging easier.

Practice

• List at least 2 strings accepted by the following state machine:

• How many states does the following finite state machine have? How many are terminal states?

• Write an equivalent regex that accepts the same strings as the following state machine:

Resources

• https://www.debuggex.com/
• A regex debugger that visualizes expressions as state machines

Footnotes

1. In formal language theory, a language defines a set of strings. Each string is a sequence of symbols. ↩
2. Also known as finite state automata (FSA). ↩
3. "Sigma". ↩
4. "delta". ↩
5. Also known as an accepting state. ↩