Unit 11 — FSAs and Regular Expressions

Slide 1 of 49

The problem: The Knock Code

The clubhouse door has no key. It has two buttons: k (a knock) and t (a tap). You press a code, one button at a time, and a little machine inside the door decides whether to open.

The club's inventor left this chart of the machine taped inside the door:

state k t

→ S (start) K —

K K T

T (final) K —
The machine starts in state S. Each button press moves it to the state in that row and column. A — means there is no move at all: the machine jams, and the door stays locked. When the code is finished, the door opens only if the machine is in the final state T.

Two questions:
1. Which of these codes open the door: kt, kkt, ktt, tkt, ktkkt?
1. The inventor wants to write down, in one short line, a rule that describes every code that opens the door. What could that line be?
A machine like this is called a finite state automaton (FSA), and the one-line rule is a regular expression. Both are on the ACSL Intermediate and Senior papers. Lesson 1 teaches you to read and run an FSA, Lesson 2 to describe what it accepts with a regular expression, and Lesson 3 the short-hand symbols real regular expressions use. Along the way you will write Python programs that run an FSA and check a pattern, and at the end of Lesson 3 you will answer both of the inventor's questions.
- Read a finite state automaton as a table or a diagram, and run it by hand on a string.
- Read and write regular expressions built from concatenation, union and star.
- Test two regular expressions for equality, or show they differ with one string.
- Read ACSL's extended syntax: ?, +, . and classes such as [a-z] and [^abc].
- Write an FSA simulator and a simple pattern matcher in Python.
Lesson 1 — Finite state automata

Division: Intermediate and above.

A finite state automaton (FSA) is a very simple machine that reads a string one symbol at a time. It has four parts:
1. a small number of states; the machine is in exactly one of them at any moment
2. transitions: rules of the form "in state K, reading t, move to state T"
3. one initial state, where it starts
4. one or more final states
The FSA accepts a string if, after reading every symbol, it is in a final state. Otherwise it rejects the string. The symbols the FSA can read are its alphabet; the door's alphabet is k and t.

state	k	t
→ S (start)	K	—
K	K	T
T (final)	K	—

Two ways to draw an FSA

ACSL draws an FSA as a picture: a circle for each state, an arrow for each transition labelled with its symbol, an arrow from nowhere into the initial state, and a double circle for each final state. Here is the door, drawn in text, with (( T )) as the double circle:

                         +-k-+
                         |   |
                         |   v
  start --> ( S ) --k--> ( K ) --t--> (( T ))
                           ^             |
                           |             |
                           +------k------+

The loop above K says: in state K, reading k, stay in K.

This book usually gives an FSA as a transition table instead. There is one row per state and one column per symbol.
- → marks the initial state.
- (final) marks each final state.
- — means there is no transition: if the machine needs it, the string is rejected at once.
Running an FSA by hand

Keep track of the state as you read the string, one symbol at a time.

Example 1. Does the door accept kkt?

read — k k t

state S K K T

The machine ends in T, a final state, so kkt is accepted.

Example 2. Does the door accept ktt?
read — k t t

state S K T ?

In state T there is no move for t. The machine jams, so ktt is rejected, even though it passed through T on the way.

Watch out:
- Only the state at the end matters. Passing through a final state is not enough.
- A missing transition rejects the string straight away, whatever comes after.

read	—	k	k	t
state	S	K	K	T

read	—	k	t	t
state	S	K	T	?

The empty string, with no symbols at all, is written λ (the Greek letter lambda). The machine reads nothing and stays in the initial state, so an FSA accepts λ exactly when its initial state is also final. The door rejects λ, because S is not final.

Example 3. This FSA reads strings of 0s and 1s.

state	0	1
→ E (final)	E	O
O	O	E

             +-0-+             +-0-+
             |   |             |   |
             |   v             |   v
  start --> (( E )) ----1----> ( O )
               ^                 |
               |                 |
               +--------1--------+

A 0 never changes the state, and every 1 swaps between E and O. So the machine is in E exactly when it has read an even number of 1s: it accepts 0110 and rejects 1011. It accepts λ too, because its initial state E is final (zero 1s is an even number).

Working out what an FSA is counting or checking, like this, is the key to the harder questions.
An FSA in Python

A transition table fits naturally in a Python dict. Each key is a tuple (state, symbol), and its value is the next state. A missing transition is simply a key that is not in the dict.

door = {("S", "k"): "K", ("K", "k"): "K", ("K", "t"): "T", ("T", "k"): "K"}
print(door[("K", "t")])
print(("T", "t") in door)
print(("T", "k") in door)

Output

T
False
True

in tells you whether a key is in the dict. Asking for door[("T", "t")] would crash the program, so always check with in first.

To run the machine, go through the string one symbol at a time. When a transition is missing, move to a made-up state "STUCK" that has no transitions at all: the machine then stays stuck to the end, and "STUCK" is never final.

door = {("S", "k"): "K", ("K", "k"): "K", ("K", "t"): "T", ("T", "k"): "K"}
for code in ["kkt", "ktt", "ktkkt"]:
    state = "S"
    for button in code:
        if (state, button) in door:
            state = door[(state, button)]
        else:
            state = "STUCK"
    print(code, state)

Output

kkt T
ktt STUCK
ktkkt T

Put it together: this program reads one code and prints OPEN if the door accepts it and LOCKED if not. It is saved as assets/l1.py.

Try it

door = {("S", "k"): "K", ("K", "k"): "K", ("K", "t"): "T", ("T", "k"): "K"}
code = input()
state = "S"
for button in code:
    if (state, button) in door:
        state = door[(state, button)]
    else:
        state = "STUCK"
if state == "T":
    print("OPEN")
else:
    print("LOCKED")

Run it from this unit's folder:
```
python assets/l1.py < assets/l1/1.in
```
It prints OPEN for the code kt. Try assets/l1/2.in (the code ktt, which jams), assets/l1/3.in and assets/l1/4.in too.
Lesson 2 — Regular expressions

Division: Intermediate and above.

An FSA is a machine that checks strings. A regular expression is a short line of text that describes a set of strings. The two ideas fit together: every FSA's set of accepted strings can be written as a regular expression, and every regular expression has an FSA.

The building blocks

Regular expression	The strings it describes
`a` (any single symbol)	just the string `a`
`λ`	just the empty string
`xy` (concatenation: one after the other)	a string from `x` followed by a string from `y`
`x	y`, also written` xUy` (union)
`x` (Kleene star*)	zero or more strings from `x`, one after another

So ab describes only ab; a|b describes a and b; and a* describes λ, a, aa, aaa, and so on forever.

ACSL writes union both ways, | and U, so 0U1 means the same as 0|1. (In this book, a capital U outside square brackets always means union, and λ always means the empty string.) Round brackets group, as in maths: (ab)* describes λ, ab, abab, ababab, ….

Precedence

When there are no brackets, the operations are done in this order:
1. star * first
2. then concatenation
3. then union | last
So:
- ab* means a(b*): an a followed by any number of bs: a, ab, abbb, but not abab.
- (ab)* repeats the whole ab: λ, ab, abab, but not abb.
- a|bc means a|(bc): the strings a and bc, not ac.
This is just like arithmetic, where powers come before multiplication and multiplication before addition: star is like a power, concatenation like multiplication, and union like addition.
Example 4. Which of these strings does 00*1*1U11*0*0 describe? 0000001111111, 1011, 10, 0

Use precedence to split it at the union first: 00*1*1 or 11*0*0.
- 00*1*1 is one or more 0s followed by one or more 1s.
- 11*0*0 is one or more 1s followed by one or more 0s.
So 0000001111111 (0s then 1s) and 10 (a 1 then a 0) are described. 1011 switches three times, and 0 has no 1 at all, so neither is.
From an FSA to a regular expression

To describe what an FSA accepts, follow the paths from the initial state to a final state:
- a chain of transitions becomes concatenation
- a loop that you can go round any number of times becomes a star
- a choice between two ways becomes a union
Example 5. The door. From S you must press k, reaching K. In K you can press k any number of times (the loop): that is k*. Then t takes you to T. So one trip from S to T is kk*t.
From T, a k goes back to K, and the same pattern repeats: k* again, and a t back to T. So after the first trip you can take any number of further trips kk*t. The door accepts exactly the strings described by
```
kk*t(kk*t)*
```
Check it against the codes from the problem: kt and kkt are one trip, and ktkkt is two trips (kt, then kkt). ktt has two ts in a row, and tkt starts with t, so neither fits.
Try it. Write a regular expression for the FSA of Example 3 (an even number of 1s). Work it out on paper before you read on.

One answer: from E, loop on 0s (0*); a pair of 1s, each followed by any 0s, takes you from E to O and back to E (10*10*); repeat the pair any number of times.
```
0*(10*10*)*
```
Another correct answer is (0|10*1)*: each step is either a 0, or a 1, some 0s and a second 1. Different regular expressions can describe the same set of strings. That is why contest questions on this usually give you options to choose from.

Identities: when are two expressions equal?

Two regular expressions are equivalent when they describe exactly the same strings. These identities are always true (a, b and c can stand for any regular expressions):

	Identity	Why
1	`(a) = a*`	repeating a repeat is still just a repeat
2	`aa* = a*a`	both are one or more `a`s
3	`aa* U λ = a*`	one or more, or none, is zero or more
4	`a(b U c) = ab U ac`	concatenation spreads over union, like multiplying out brackets
5	`a(ba)* = (ab)*a`	both are `a`, `aba`, `ababa`, …
6	`(a U b)* = (a* U b)`	any mixture of `a`s and `b`s
7	`(a U b)* = (ab)*`	the same
8	`(a U b)* = a(ba)*`	the same

To show that two expressions are not equivalent, one string is enough: find a string that one describes and the other does not. For example, (ab)* = ab* is false: abb fits ab* but not (ab)*. A good way to hunt is to try the short strings first: λ, then every string of length 1, then length 2, and so on.

Counting accepted strings in Python

Trying every short string is exactly what a computer is good at. The function count below builds every code of length n one button at a time, with recursion: a code that is not long enough yet branches into two longer codes, one ending in k and one ending in t.
```
def count(code, n):
    if len(code) == n:
        print(code)
        return 1
    return count(code + "k", n) + count(code + "t", n)


print(count("", 2))
```
Scroll the code for more ↓
Output
```
kk
kt
tk
tt
4
```
With 2 buttons there are 2 × 2 = 4 codes of length 2, and in general 2 multiplied by itself n times.

Put it together: this program reads n and prints how many codes of length n open the door. It is saved as assets/l2.py.

Try it

door = {("S", "k"): "K", ("K", "k"): "K", ("K", "t"): "T", ("T", "k"): "K"}


def opens(code):
    state = "S"
    for button in code:
        if (state, button) in door:
            state = door[(state, button)]
        else:
            state = "STUCK"
    return state == "T"


def count(code, n):
    if len(code) == n:
        if opens(code):
            return 1
        return 0
    return count(code + "k", n) + count(code + "t", n)


n = int(input())
print(count("", n))

Run it from this unit's folder:
```
python assets/l2.py < assets/l2/1.in
```
For n = 2 it prints 1 (only kt opens the door). Try assets/l2/2.in and assets/l2/3.in, then check the answer for n = 3 by hand with kk*t(kk*t)*.

Lesson 3 — The extended syntax

Division: Intermediate and above.

Real regular expressions, like the ones in text editors and search boxes, add some short-hand symbols. ACSL uses them too:

Symbol	Meaning	Example	Describes
`x?`	zero or one `x`	`ab?`	`a`, `ab`
`x+`	one or more `x`	`ab+`	`ab`, `abb`, `abbb`, …
`x*`	zero or more `x`	`ab*`	`a`, `ab`, `abb`, …
`.`	any one character	`c.t`	`cat`, `cot`, `c9t`, …
`[abc]`	any one of the characters listed	`[aeiou]`	one vowel
`[^abc]`	any one character not listed	`[^0-9]`	one character that is not a digit
`[a-z]`	any one character in the range	`[A-D]`	`A`, `B`, `C` or `D`
`(x)`	grouping	`(ab)+`	`ab`, `abab`, …

?, + and * work on the one thing just before them: a single character, a ., a class in square brackets, or a bracketed group. None of these add anything new; they are short ways to write the basic operations. For example, x+ is xx*, x? is x|λ, and [abc] is a|b|c.

Watch out:

- Inside square brackets, ^ means "not" only when it comes first: [^abc].
- A class matches exactly one character. [a-c] matches b but not bc; [a-c]+ matches bc.
- Capital and small letters are different characters: [a-d] does not match B.
Example 6. Which strings match [A-D]*[a-d]*[0-9]? ABCD8, abcd5, ABcd9, AbCd7, DCCBBBaaaa5, ABCDE3

The pattern is: any number of capitals from A to D, then any number of small letters from a to d, then exactly one digit.
- ABCD8, abcd5, ABcd9 and DCCBBBaaaa5 match.
- AbCd7 does not: once a small letter has appeared, a capital cannot come back.
- ABCDE3 does not: E is outside A to D.
Example 7. Which strings match Hi?g+h+[^a-ceiou]? Highb, HigghhhC, Hihh, Highd, HgggggghX

The pattern is: H, an optional i, one or more gs, one or more hs, and then one character that is not a, b, c, e, i, o or u.
- HigghhhC, Highd and HgggggghX match. (C and X are capitals, so they are not in the class a-ceiou; d is not in it either.)
- Highb does not: its last character b is in a-c.
- Hihh does not: it has no g.
A pattern matcher in Python

Here is a program that checks whether a word matches a pattern made of letters, where a letter may be followed by *. It works on two positions at once: i, how far it has got in the pattern, and j, how far it has got in the word.
- When the pattern is used up, the match succeeds only if the word is used up too.
- A plain letter must match the next character of the word; then both move on by one.
- A letter with a * gives two choices: use it zero times (skip the letter and its * in the pattern), or match one copy of it and stay on the same letter to look for more.
Recursion is the natural way to try both choices: if the first choice fails, the function comes back and tries the second.

def match(p, i, s, j):
    if i == len(p):
        return j == len(s)
    fits = j < len(s) and s[j] == p[i]
    if i + 1 < len(p) and p[i + 1] == "*":
        if match(p, i + 2, s, j):
            return True
        return fits and match(p, i, s, j + 1)
    return fits and match(p, i + 1, s, j + 1)


print(match("ab*c", 0, "abbbc", 0))
print(match("ab*c", 0, "ac", 0))
print(match("a*ab", 0, "aaab", 0))
print(match("ab*c", 0, "abcb", 0))

Output

True
True
True
False

The third test needs the second choice. For a*ab on aaab, the a* must take only two of the three as, leaving one a for the plain a in the pattern. The recursion finds this by trying the choices one after another, without you telling it how many as to take.

fits uses and so that s[j] is only looked at when j < len(s): once the first part is False, Python does not work out the second part at all.
Put it together: this program reads a pattern on the first line and a word on the second, and prints ACCEPT or REJECT. It is saved as assets/l3.py.

Try it

def match(p, i, s, j):
    if i == len(p):
        return j == len(s)
    fits = j < len(s) and s[j] == p[i]
    if i + 1 < len(p) and p[i + 1] == "*":
        if match(p, i + 2, s, j):
            return True
        return fits and match(p, i, s, j + 1)
    return fits and match(p, i + 1, s, j + 1)


pattern = input()
word = input()
if match(pattern, 0, word, 0):
    print("ACCEPT")
else:
    print("REJECT")

Run it from this unit's folder:
```
python assets/l3.py < assets/l3/1.in
```
It prints ACCEPT for the pattern ab*c and the word abbbc. Try assets/l3/2.in, assets/l3/3.in and assets/l3/4.in too.
Back to the door

Now both of the inventor's questions are easy.
1. Run each code through the table (or through assets/l1.py): kt, kkt and ktkkt open the door; ktt jams at its second t, and tkt jams at once, since S has no move for t.
2. In Lesson 2 you found kk*t(kk*t)*. With the extended syntax, kk* is k+, so one trip is k+t, and one or more trips is
```
(k+t)+
```
In words: the door opens for one or more blocks, where each block is one or more knocks followed by a single tap.
- An FSA accepts a string only if it ends in a final state; a missing move rejects the string.
- Star goes first, then concatenation, then union.
- One counterexample string is enough to show that two expressions are different.
- x+ means one or more (so kk* is k+), x? means zero or one, and a class matches exactly one character.
- In Python, a dict keyed by (state, symbol) tuples holds the transition table, and recursion tries both choices of a star.
You can now describe the knock code in one line, (k+t)+, and answer ACSL's FSA and pattern questions.

Unit 11 — FSAs and Regular Expressions

The problem: The Knock Code

Lesson 1 — Finite state automata

Two ways to draw an FSA

Running an FSA by hand

An FSA in Python

Lesson 2 — Regular expressions

The building blocks

Precedence

From an FSA to a regular expression

Identities: when are two expressions equal?

Counting accepted strings in Python

Lesson 3 — The extended syntax

A pattern matcher in Python

Back to the door