Implementing the Regular Operations

So far, we’ve seen only a trivial regular expression: one containing a single character æ, which evaluates to the language {æ} \(\in 2^{\Sigma^*}\). How do we represent other kinds of regular expressions?

Concatenation

The operation of concatenation, which we represented using \(\circ\), is implicit in putting two characters next to each other. For instance, to represent the regular expression \((\text{æ} \circ (\text{b} \circ (\text{s} \circ (\text{t} \circ (\text{ɹ} \circ (\text{æ} \circ (\text{k} \circ (\text{ʃ} \circ (\text{ə} \circ \text{n})))))))))\), we can simply write æbstɹækʃən.

with open("cmudict-ipa", encoding="utf-8") as f:
    entry_rows: list[list[str]] = [
        line.strip().split(",", maxsplit=1) for line in f
    ]
    entries: dict[str, list[str]] = {
        word: ipa.split() for word, ipa in entry_rows
    }

import re

regex_æbstɹækʃən = "æbstɹækʃən"

string_æbstɹækʃən = "".join(entries["abstraction"])

re.fullmatch(regex_æbstɹækʃən, string_æbstɹækʃən)

Union

In contrast, to represent the regular expression \(((\text{æ} \cup \text{ə}) \circ (\text{b} \circ (\text{s} \circ (\text{t} \circ (\text{ɹ} \circ ((\text{æ} \cup \text{ə}) \circ (\text{k} \circ (\text{ʃ} \circ (\text{ə} \circ \text{n})))))))))\), which evaluates to {æbstɹækʃən, əbstɹækʃən, æbstɹəkʃən, əbstɹəkʃən}, we either use []…

regex_æəbstɹæəkʃən = "[æə]bstɹ[æə]kʃən"

string_əbstɹəkʃən = "".join(entries["obstruction"])
string_æbstɹəkʃən = "æbstɹəkʃən"
string_əbstɹækʃən = "əbstɹækʃən"

(re.fullmatch(regex_æəbstɹæəkʃən, string_æbstɹækʃən),
 re.fullmatch(regex_æəbstɹæəkʃən, string_æbstɹəkʃən),
 re.fullmatch(regex_æəbstɹæəkʃən, string_əbstɹækʃən), 
 re.fullmatch(regex_æəbstɹæəkʃən, string_əbstɹəkʃən))

…or an explicit |.

regex_æəbstɹæəkʃən = "(æ|ə)bstɹ(æ|ə)kʃən"

(re.fullmatch(regex_æəbstɹæəkʃən, string_æbstɹækʃən),
 re.fullmatch(regex_æəbstɹæəkʃən, string_æbstɹəkʃən),
 re.fullmatch(regex_æəbstɹæəkʃən, string_əbstɹækʃən), 
 re.fullmatch(regex_æəbstɹæəkʃən, string_əbstɹəkʃən))

Note that the () are important in the latter case!

regex_æəbstɹæəkʃən = "æ|əbstɹæ|əkʃən"

(re.fullmatch(regex_æəbstɹæəkʃən, string_æbstɹækʃən),
 re.fullmatch(regex_æəbstɹæəkʃən, string_æbstɹəkʃən),
 re.fullmatch(regex_æəbstɹæəkʃən, string_əbstɹækʃən), 
 re.fullmatch(regex_æəbstɹæəkʃən, string_əbstɹəkʃən))

Kleene star

Finally, the Kleene star works the way you would expect.

regex_ææææbstɹækʃən = "æ*bstɹækʃən"

for i in range(10):
    print(re.fullmatch(regex_ææææbstɹækʃən, "æ"*i + string_æbstɹækʃən[1:]))

To apply the Kleene star to a complex regular expression, we need ().

regex_reæbstɹækʃən = "(ɹi|di)*æbstɹækʃən"

for i in range(3):
    print(re.fullmatch(regex_reæbstɹækʃən, "ɹi"*i + string_æbstɹækʃən))
    print(re.fullmatch(regex_reæbstɹækʃən, "di"*i + string_æbstɹækʃən))
    print(re.fullmatch(regex_reæbstɹækʃən, "ɹidi"*i + string_æbstɹækʃən))
    print(re.fullmatch(regex_reæbstɹækʃən, "diɹi"*i + string_æbstɹækʃən))