Defining Regular Expressions

Regular expressions themselves are strings. We formally define these strings recursively, starting with an alphabet $\Sigma$, a symbol for the empty string $\epsilon$, and a symbol for the empty set $\emptyset$. Let’s assume the alphabet is the set of English phonemes:

\[\Sigma \equiv \{\text{ɑ, æ, ʌ, ɔ, aʊ, aɪ, b, tʃ, d, ð,} \ldots\}\]

$\rho$ is a regular expression if and only if:

$\rho \in \Sigma \cup \{\epsilon, \emptyset\}$
$\rho$ is $(\rho_1 \cup \rho_2)$ for some regular expressions $\rho_1$ and $\rho_2$
$\rho$ is $(\rho_1 \circ \rho_2)$ for some regular expressions $\rho_1$ and $\rho_2$
$\rho$ is $\rho_1^*$ for some regular expression $\rho_1$

Thus, given the $\Sigma$ above, the following are all regular expressions.

æ
b
(æ $\cup$ b)
(æ $\circ$ b$^*$)
(æ $\circ$ b)$^*$
((æ $\circ$ b) $\cup$ b)
(æ $\circ$ (b $\cup$ b))

The following are not regular expressions.

æ $\cup$ b
æ $\circ$ b$^*$
æ $\circ$ b $\cup$ b

Another way of saying this is that the regular expressions on $\Sigma$ are a language on $\Sigma \cup\{\epsilon, \emptyset, \cup, \circ, (, ), *\}$. Note that, based on the recursive definition above, the set of regular expressions is infinite. Thus, the regular expressions on $\Sigma$ are the first infinite language we’ve described (besides $\Sigma^*$ itself).

We can generate all the regular expressions given an alphabet. Note that because the set of regular expressions is infinite, we need to use a generator.

from collections.abc import Iterator

def regular_expressions(sigma: set[str]) -> Iterator[str]:
    old_regex_set = frozenset(sigma | {'∅', '𝜖'})
    
    for rho in old_regex_set:
        yield rho
    
    while True:
        new_regex_set = set(old_regex_set)
            
        for rho in old_regex_set:
            elem = rho+'*'
            new_regex_set |= {elem}
            yield elem
            
        for rho1 in old_regex_set:
            for rho2 in old_regex_set:
                elem = '('+rho1+' ∪ '+rho2+')'
                new_regex_set |= {elem}
                yield elem
                
        for rho1 in old_regex_set:
            for rho2 in old_regex_set:
                elem = '('+rho1+' ∘ '+rho2+')'
                new_regex_set |= {elem}
                yield elem
                
        old_regex_set = frozenset(new_regex_set)

But how do we know this generator eventually reaches every regular expression? The key is a construction-depth invariant. Give each atomic expression depth $0$, and give an expression formed with $*$, $\cup$, or $\circ$ depth one greater than the maximum depth of its immediate subexpressions. After round $d$, old_regex_set contains every regular expression of depth at most $d$.

Start with the initialization: the symbols in $\Sigma\cup\{\epsilon,\emptyset\}$ are exactly the depth-$0$ expressions. Now suppose the set contains every expression of depth at most $d$. Each loop applies star to every member and union and concatenation to every ordered pair of members. It thus constructs every expression of depth $d+1$, while retaining the expressions constructed earlier. The invariant is thus preserved for the next round.

Conversely, every initialized object satisfies the first clause of the definition, and every object added by the loop applies one of the three licensed constructors to expressions already in the set. Thus, the generator never constructs a non-regular expression. Since every regular expression has some finite construction depth, the invariant also guarantees that every regular expression appears after finitely many rounds. The code may yield an expression more than once, but it neither omits a well-formed expression nor introduces an ill-formed one.

english_phonemes = {"ɑ", "æ", "ə", "ʌ", "ɔ", "aʊ", "aɪ", "b", "tʃ", "d", "ð", "ɛ", 
                    "ɝ", "eɪ", "f", "g", "h", "ɪ", "i", "dʒ", "k", "l", "m", 
                    "n", "ŋ", "oʊ", "ɔɪ", "p", "ɹ", "s", "ʃ", "t", "θ", "ʊ", 
                    "u", "v", "w", "j", "z", "ʒ"}

for i, r in enumerate(regular_expressions(english_phonemes)):
    print(r)
    
    if i > 100:
        break

--- title: Defining Regular Expressions jupyter: python3 --- Regular expressions themselves are strings. We formally define these strings recursively, starting with an alphabet $\Sigma$, a symbol for the empty string $\epsilon$, and a symbol for the empty set $\emptyset$. Let's assume the alphabet is the set of English phonemes: $$\Sigma \equiv \{\text{ɑ, æ, ʌ, ɔ, aʊ, aɪ, b, tʃ, d, ð,} \ldots\}$$ $\rho$ is a regular expression if and only if: 1. $\rho \in \Sigma \cup \{\epsilon, \emptyset\}$ 2. $\rho$ is $(\rho_1 \cup \rho_2)$ for some regular expressions $\rho_1$ and $\rho_2$ 3. $\rho$ is $(\rho_1 \circ \rho_2)$ for some regular expressions $\rho_1$ and $\rho_2$ 4. $\rho$ is $\rho_1^*$ for some regular expression $\rho_1$ Thus, given the $\Sigma$ above, the following are all regular expressions. 1. æ 2. b 3. (æ $\cup$ b) 4. (æ $\circ$ b$^*$) 5. (æ $\circ$ b)$^*$ 6. ((æ $\circ$ b) $\cup$ b) 7. (æ $\circ$ (b $\cup$ b)) The following are *not* regular expressions. 1. æ $\cup$ b 2. æ $\circ$ b$^*$ 3. æ $\circ$ b $\cup$ b Another way of saying this is that the regular expressions on $\Sigma$ are a language on $\Sigma \cup\{\epsilon, \emptyset, \cup, \circ, (, ), *\}$. Note that, based on the recursive definition above, the set of regular expressions is infinite. Thus, the regular expressions on $\Sigma$ are the first infinite language we've described (besides $\Sigma^*$ itself). We can generate all the regular expressions given an alphabet. Note that because the set of regular expressions is infinite, we need to use a generator. ```{python} #| executionInfo: {elapsed: 141, status: ok, timestamp: 1675099872833, user: {displayName: Aaron Steven White, userId: 06256629009318567325}, user_tz: 300} from collections.abc import Iterator def regular_expressions(sigma: set[str]) -> Iterator[str]: old_regex_set = frozenset(sigma | {'∅', '𝜖'}) for rho in old_regex_set: yield rho while True: new_regex_set = set(old_regex_set) for rho in old_regex_set: elem = rho+'*' new_regex_set |= {elem} yield elem for rho1 in old_regex_set: for rho2 in old_regex_set: elem = '('+rho1+' ∪ '+rho2+')' new_regex_set |= {elem} yield elem for rho1 in old_regex_set: for rho2 in old_regex_set: elem = '('+rho1+' ∘ '+rho2+')' new_regex_set |= {elem} yield elem old_regex_set = frozenset(new_regex_set) ``` But how do we know this generator eventually reaches every regular expression? The key is a **construction-depth invariant**. Give each atomic expression depth $0$, and give an expression formed with $*$, $\cup$, or $\circ$ depth one greater than the maximum depth of its immediate subexpressions. After round $d$, `old_regex_set` contains every regular expression of depth at most $d$. Start with the initialization: the symbols in $\Sigma\cup\{\epsilon,\emptyset\}$ are exactly the depth-$0$ expressions. Now suppose the set contains every expression of depth at most $d$. Each loop applies star to every member and union and concatenation to every ordered pair of members. It thus constructs every expression of depth $d+1$, while retaining the expressions constructed earlier. The invariant is thus preserved for the next round. Conversely, every initialized object satisfies the first clause of the definition, and every object added by the loop applies one of the three licensed constructors to expressions already in the set. Thus, the generator never constructs a non-regular expression. Since every regular expression has some finite construction depth, the invariant also guarantees that every regular expression appears after finitely many rounds. The code may yield an expression more than once, but it neither omits a well-formed expression nor introduces an ill-formed one. ```{python} #| colab: {base_uri: 'https://localhost:8080/'} #| executionInfo: {elapsed: 3934, status: ok, timestamp: 1675099876765, user: {displayName: Aaron Steven White, userId: 06256629009318567325}, user_tz: 300} #| outputId: babeefbd-7970-4005-985c-0eb4aa189eb3 english_phonemes = {"ɑ", "æ", "ə", "ʌ", "ɔ", "aʊ", "aɪ", "b", "tʃ", "d", "ð", "ɛ", "ɝ", "eɪ", "f", "g", "h", "ɪ", "i", "dʒ", "k", "l", "m", "n", "ŋ", "oʊ", "ɔɪ", "p", "ɹ", "s", "ʃ", "t", "θ", "ʊ", "u", "v", "w", "j", "z", "ʒ"} for i, r in enumerate(regular_expressions(english_phonemes)): print(r) if i > 100: break ```