Regular expressions and regular languages

The metacharacters, matching in Python, the link between regexes and FSMs, and what makes a language regular.

A6.4Theory of computationA level25 min

A finite state machine describes a set of strings by drawing a machine. A regular expression (regex) describes a set of strings by writing a short pattern. They turn out to be two views of the same thing, and the sets of strings they can describe have a name: regular languages.

Languages

In theory of computation an alphabet is a finite set of symbols, such as {0, 1} or {a, b}, and a language is a set of strings made from that alphabet. The language might be finite, like {ab, ba}, or countably infinite, like "every binary string with an even number of 1s". A regex is a way to write down a language, and a string matches the regex when it is a member of that language.

The metacharacters

Any ordinary character in a regex matches itself, so abc describes the set {abc}. The metacharacters build bigger sets:

"" is the empty string. *, + and ? apply only to the single character or bracketed group just before them, so ab* is a followed by any number of bs, while (ab)* repeats the pair. Alternation has the lowest priority of all: ab|cd means ab or cd, not a, then b or c, then d.

Some worked examples over the alphabet {a, b}:

• a(a|b)* : strings that start with a.
• (a|b)*b : strings that end with b.
• (a|b)(a|b) : every string of exactly two symbols, {aa, ab, ba, bb}.
• b*ab* : strings containing exactly one a.

As a set, ab* is {abⁿ | n ≥ 0}, using the notation from the last lesson.

Regular expressions in Python

Python's re module understands these metacharacters. re.fullmatch(pattern, text) succeeds only if the whole of the text matches, which is what "is this string in the language?" means. Writing the pattern as a raw string, r"...", stops Python treating backslashes specially.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

import re

pattern = r"a(a|b)*"
for text in ["a", "abba", "ba", "aab", ""]:
    result = "yes" if re.fullmatch(pattern, text) else "no"
    print(repr(text), result)

Run this in the simulator

Real regex engines add shorthand. [0-9] means any one digit and [FBLR] any one of those four letters, both of which could be written with | instead. Exam regexes stick to the metacharacters above, so learn to write everything with them first.

A robot command language might have tokens such as F20 (forward 20 cm) or R90 (turn right 90 degrees): a direction letter then one or more digits. With only the exam metacharacters that is (F|B|L|R)(0|1|2|3|4|5|6|7|8|9)+. Checking the shape of each token like this is the first job of a compiler's lexical analyser.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

import re

token = r"(F|B|L|R)(0|1|2|3|4|5|6|7|8|9)+"
for text in ["F20", "R90", "F", "20F", "L5"]:
    print(text, bool(re.fullmatch(token, text)))

Run this in the simulator

Regular expressions and FSMs

Every regular expression has a finite state machine that accepts exactly the same language, and every FSM has a regular expression for its language. They describe the same sets of strings.

For a(b|c)*: S0 is the start, reading a moves to S1, which is accepting, and S1 loops to itself on b or c. Any other symbol goes to a trap state.

Going the other way, the parity machine from lesson A6.1 accepts strings with an even number of 1s. A regex for it is 0*(10*10*)*: any 0s, then any number of blocks, each containing exactly two 1s with any 0s after each. Every string it matches has an even number of 1s, and every string with an even number of 1s can be split that way.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

import re
from itertools import product

# check the regex and the machine agree on every binary string up to length 8
agree = True
for n in range(9):
    for bits in product("01", repeat=n):
        text = "".join(bits)
        by_regex = re.fullmatch(r"0*(10*10*)*", text) is not None
        by_machine = text.count("1") % 2 == 0
        if by_regex != by_machine:
            agree = False
print("agree on all 511 strings:", agree)

Run this in the simulator

Regular languages

A language is regular if it can be described by a regular expression. Because regexes and FSMs are equivalent, that is the same as saying a language is regular if some finite state machine accepts it.

The word "finite" is the limit. An FSM remembers only which of its states it is in, so it cannot count without bound. The language {0ⁿ1ⁿ | n ≥ 1} needs the machine to remember how many 0s it has read, which could be any number, so no FSM accepts it and no regex describes it: it is not regular. The same goes for "every bracket is matched by a closing bracket", which is why regexes cannot check the nesting in a program. The next lesson brings in a notation that can.

Task: three languages

Write a regular expression for each language, then test it.

• L1: strings over {a, b} that start with a and end with b.
• L2: binary strings in which every 1 is immediately followed by a 0. The string 000 counts, because it has no 1s at all.
• L3: binary numbers with no leading zeros: 0 itself, or a 1 followed by any binary digits.

Rules:

• Assign each pattern to its variable as a raw string on one line, such as L1 = r"...". Use only the symbols of the language and the metacharacters * + ? | ( ). No [ ], no \d.
• Test with re.fullmatch. For every string in tests[name], working through L1, L2, L3 in that order, print the name, the string and yes or no, separated by single spaces: for example L1 ab yes. Fifteen lines in all.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

import re

tests = {
    "L1": ["ab", "aab", "ba", "a", "abab"],
    "L2": ["1010", "0100", "110", "01", "000"],
    "L3": ["0", "1010", "0101", "100", "00"],
}

Challenges

1. Write a regex for binary strings that contain 11 somewhere. Then draw its FSM.
2. Does (a|b)* include the empty string? Does (a|b)+?
3. Explain why no regex can describe {aⁿbⁿ | n ≥ 1}, but a+b+ is fine.