Quantifiers

Note that ., the character ranges, and the escape characters match only a single character, and so to match more than one, we need more than one of whichever we are interested in matching.

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_dot_stɹ_dot_kʃən = '.bstɹ.kʃən'
regex_dot_dot_tɹ_dot_kʃən = '..stɹ.kʃən'

print(regex_dot_stɹ_dot_kʃən, "matches:")
print()

for w, ipa in entries.items():    
    if re.fullmatch(regex_dot_stɹ_dot_kʃən, "".join(ipa)):
        print(regex_dot_stɹ_dot_kʃən, "matches", "".join(ipa), f"({w})")

print()

print(regex_dot_dot_tɹ_dot_kʃən, "matches:")
print()

for w, ipa in entries.items():
    if re.fullmatch(regex_dot_dot_tɹ_dot_kʃən, "".join(ipa)):
        print("".join(ipa), f"({w})")

We can avoid writing out multiple by using a quantifier. There are a few different quantifiers. For instance, if you have an exact number in mind:

regex_dot2_tɹ_dot_kʃən = '.{2}stɹ.kʃən'

for w, ipa in entries.items():
    if re.fullmatch(regex_dot2_tɹ_dot_kʃən, "".join(ipa)):
        print("".join(ipa), f"({w})")

Or if you had a range of numbers in mind:

regex_dot2_tɹæk_dot13 = '.{2}stɹək.{1,3}'

for w, ipa in entries.items():
    if re.fullmatch(regex_dot2_tɹæk_dot13, "".join(ipa)):
        print("".join(ipa), f"({w})")

You can also leave off one bound:

regex_dot2_tɹæk_dot03 = '.{2}stɹək.{,3}'
regex_dot2_tɹæk_dot1inf = '.{2}stɹək.{1,}'

print(regex_dot2_tɹæk_dot03, "matches:")
print()

n_matches = 0

for w, ipa in entries.items():
    if re.fullmatch(regex_dot2_tɹæk_dot03, "".join(ipa)):
        if n_matches < 10:
            n_matches += 1
            print("".join(ipa), f"({w})")
        else:
            print("...")
            break

print()
print(regex_dot2_tɹæk_dot1inf, "matches:")
print()

n_matches = 0

for w, ipa in entries.items():
    if re.fullmatch(regex_dot2_tɹæk_dot1inf, "".join(ipa)):
        if n_matches < 10:
            n_matches += 1
            print("".join(ipa), f"({w})")
        else:
            print("...")
            break

Note that {,} is equivalent to *. There is also a special quantifier symbol for {1,}: +

And if you wanted at least one character to come after Aaron, but didn’t care how many came after that, you could use +.

regex_dot2_tɹæk_dotplus = '.{2}stɹək.+'

n_matches = 0

for w, ipa in entries.items():
    if re.fullmatch(regex_dot2_tɹæk_dotplus, "".join(ipa)):
        if n_matches < 10:
            n_matches += 1
            print("".join(ipa), f"({w})")
        else:
            print("...")
            break

Do any of these quantifiers increase the expressive power of regular expressions? No. We can translate each one into the three regular operations.

Fix an arbitrary regular expression \(\rho\). Define \(\rho^0=\epsilon\) and \(\rho^{i+1}=\rho^i\circ\rho\). The main translations are

\[ \begin{aligned} \rho\{m\} &\equiv \rho^m,\\ \rho\{m,n\} &\equiv \rho^m\cup\rho^{m+1}\cup\cdots\cup\rho^n,\\ \rho\{m,\} &\equiv \rho^m\circ\rho^*,\\ \rho\{,n\} &\equiv \epsilon\cup\rho\cup\cdots\cup\rho^n,\\ \rho+ &\equiv \rho\circ\rho^*. \end{aligned} \]

Take the bounded-range case. A string matches \(\rho\{m,n\}\) exactly when it is a concatenation of \(i\) strings from \(\operatorname{eval}(\rho)\) for some \(m\leq i\leq n\). The expression on the right evaluates to the union of those same languages \(\operatorname{eval}(\rho)^i\). Thus, every quantified match appears in one union branch, and every string in a union branch has a permitted repetition count.

The unbounded case has the same form. If a string uses at least \(m\) repetitions, separate its first \(m\) factors from the remaining \(j\geq0\) factors. The first portion belongs to \(\operatorname{eval}(\rho)^m\) and the remainder belongs to \(\operatorname{eval}(\rho)^*\). Conversely, concatenating a member of \(\operatorname{eval}(\rho)^m\) with any member of \(\operatorname{eval}(\rho)^*\) produces \(m+j\) repetitions for some \(j\geq0\). Thus, \(\rho\{m,\}\) and \(\rho^m\circ\rho^*\) describe the same language.

For instance, a{2,3} abbreviates \((a\circ a)\cup(a\circ a\circ a)\), which evaluates to \(\{\text{aa},\text{aaa}\}\). The quantifier is more compact, but the translated expression uses no additional operation. Since each quantifier has such a translation, adding them changes notation rather than expressive power.

Set complement

For these escaped character classes, the uppercase version generally matches the complement—e.g. \w becomes \W.

regex_notw_bstɹækt = r'\Wbstɹəkt'

(re.fullmatch(regex_notw_bstɹækt, "".join(entries["obstruct"])),
 re.fullmatch(regex_notw_bstɹækt, '\n'+"".join(entries["obstruct"])[1:]))

Sometimes you want the complement of a set that doesn’t have an associated escaped alphabetic character. For that you can use the same square bracket set notation but put a ^ after the first bracket.

regex_notæ_bstɹ_notæ_kt = '[^æ][^b]stɹ[^æ]kt'

for w, ipa in entries.items():    
    if re.fullmatch(regex_notæ_bstɹ_notæ_kt, "".join(ipa)):
        print("".join(ipa), f"({w})")

The placement of this ^ is really important, since it only has the negation interpretation directly after [.