Unit 11 — FSAs and Regular Expressions

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.

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?

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

Example 2. Does the door accept ktt?

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.
• 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.

             +-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)

T
False
True

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)

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.

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

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):

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))

kk
kt
tk
tt
4

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:

?, + 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))

True
True
True
False

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.

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.