Evaluating Regular Expressions

Regular expressions evaluate to sets of strings on \(\Sigma\)–i.e. languages on \(\Sigma\). Another way of thinking about this is that a regular expression on \(\Sigma\) describes a language on \(\Sigma\).

We can define this evaluation procedure formally as a function \(\text{eval}: R(\Sigma) \rightarrow 2^{\Sigma^*}\), where \(R(\Sigma)\) is the set of regular expressions on \(\Sigma\).

\(\text{eval}(\rho) = \begin{cases}\{\} & \text{if } \rho = \emptyset \\\{\_\} & \text{if } \rho = \epsilon \\ \{\rho\} & \text{if } \rho \in \Sigma\\ \text{eval}(\rho_1) \times \text{eval}(\rho_2) & \text{if } \rho = (\rho_1 \circ \rho_2) \\ \text{eval}(\rho_1) \cup \text{eval}(\rho_2) & \text{if } \rho = (\rho_1 \cup \rho_2)\\ \bigcup_{i = 0}^\infty \text{eval}(\rho_1)^i & \text{if } \rho = \rho_1^*\\ \end{cases}\)

So first, we’re going to want to have access to the regular expressions’ structure for the purposes of evaluating them. We could do this by using pyparsing or some hand-built parser to reconstruct the structure of each expression, but we may as well just build retain the structure while generating the expression.

def regular_expressions_structured(sigma):
    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)

for i, r in enumerate(regular_expressions_structured({'ə', 'm'})):
    print(r)
    
    if i > 100:
        break

ə
∅
m
𝜖
('ə', '*')
('∅', '*')
('m', '*')
('𝜖', '*')
('ə', '∪', 'ə')
('ə', '∪', '∅')
('ə', '∪', 'm')
('ə', '∪', '𝜖')
('∅', '∪', 'ə')
('∅', '∪', '∅')
('∅', '∪', 'm')
('∅', '∪', '𝜖')
('m', '∪', 'ə')
('m', '∪', '∅')
('m', '∪', 'm')
('m', '∪', '𝜖')
('𝜖', '∪', 'ə')
('𝜖', '∪', '∅')
('𝜖', '∪', 'm')
('𝜖', '∪', '𝜖')
('ə', '∘', 'ə')
('ə', '∘', '∅')
('ə', '∘', 'm')
('ə', '∘', '𝜖')
('∅', '∘', 'ə')
('∅', '∘', '∅')
('∅', '∘', 'm')
('∅', '∘', '𝜖')
('m', '∘', 'ə')
('m', '∘', '∅')
('m', '∘', 'm')
('m', '∘', '𝜖')
('𝜖', '∘', 'ə')
('𝜖', '∘', '∅')
('𝜖', '∘', 'm')
('𝜖', '∘', '𝜖')
(('m', '*'), '*')
(('m', '∘', 'm'), '*')
('∅', '*')
(('m', '∪', 'm'), '*')
(('ə', '∘', '𝜖'), '*')
(('𝜖', '*'), '*')
(('m', '∘', 'ə'), '*')
(('∅', '∘', 'ə'), '*')
(('𝜖', '∘', '∅'), '*')
(('∅', '∪', 'm'), '*')
(('m', '∪', 'ə'), '*')
(('𝜖', '∪', '∅'), '*')
(('∅', '∪', 'ə'), '*')
(('ə', '∪', '∅'), '*')
(('∅', '∘', '𝜖'), '*')
(('𝜖', '∘', 'm'), '*')
(('𝜖', '∪', 'm'), '*')
(('∅', '∪', '∅'), '*')
(('m', '∘', '𝜖'), '*')
(('ə', '∘', '∅'), '*')
('𝜖', '*')
(('m', '∪', '𝜖'), '*')
(('𝜖', '∘', 'ə'), '*')
(('ə', '∪', 'm'), '*')
(('𝜖', '∪', 'ə'), '*')
(('∅', '∪', '𝜖'), '*')
(('ə', '∘', 'm'), '*')
(('ə', '∪', 'ə'), '*')
(('ə', '*'), '*')
('m', '*')
(('∅', '∘', '∅'), '*')
(('ə', '∘', 'ə'), '*')
(('𝜖', '∘', '𝜖'), '*')
(('∅', '*'), '*')
(('𝜖', '∪', '𝜖'), '*')
(('m', '∘', '∅'), '*')
(('m', '∪', '∅'), '*')
('ə', '*')
(('∅', '∘', 'm'), '*')
(('ə', '∪', '𝜖'), '*')
(('m', '*'), '∪', ('m', '*'))
(('m', '*'), '∪', ('m', '∘', 'm'))
(('m', '*'), '∪', '∅')
(('m', '*'), '∪', ('m', '∪', 'm'))
(('m', '*'), '∪', ('ə', '∘', '𝜖'))
(('m', '*'), '∪', ('𝜖', '*'))
(('m', '*'), '∪', ('m', '∘', 'ə'))
(('m', '*'), '∪', ('∅', '∘', 'ə'))
(('m', '*'), '∪', ('𝜖', '∘', '∅'))
(('m', '*'), '∪', ('∅', '∪', 'm'))
(('m', '*'), '∪', ('m', '∪', 'ə'))
(('m', '*'), '∪', ('𝜖', '∪', '∅'))
(('m', '*'), '∪', ('∅', '∪', 'ə'))
(('m', '*'), '∪', ('ə', '∪', '∅'))
(('m', '*'), '∪', ('∅', '∘', '𝜖'))
(('m', '*'), '∪', ('𝜖', '∘', 'm'))
(('m', '*'), '∪', ('𝜖', '∪', 'm'))
(('m', '*'), '∪', ('∅', '∪', '∅'))
(('m', '*'), '∪', ('m', '∘', '𝜖'))
(('m', '*'), '∪', ('ə', '∘', '∅'))
(('m', '*'), '∪', '𝜖')
(('m', '*'), '∪', ('m', '∪', '𝜖'))

Next, we can write a function that recursively evaluates a regular expression.

def evaluate_regular_expression(regex):
    if regex == '∅':
        return
    
    elif regex == '𝜖':
        yield ''
    
    elif isinstance(regex, str):
        yield regex
    
    elif regex[1] == '*':
        i = 0
        while True:
            for s in evaluate_regular_expression(regex[0]):
                yield s*i
            
            i += 1
            
    elif regex[1] == '∪':
        for s1 in evaluate_regular_expression(regex[0]):
            yield s1
            
        for s2 in evaluate_regular_expression(regex[2]):
            yield s2
            
    elif regex[1] == '∘':
        for s1 in evaluate_regular_expression(regex[0]):
            for s2 in evaluate_regular_expression(regex[2]):
                yield s1 + s2

for s in evaluate_regular_expression('ə'):
    print(s)

ə

for s in evaluate_regular_expression(('ə', '∪', 'm')):
    print(s)

ə
m

for s in evaluate_regular_expression(('ə', '∘', 'm')):
    print(s)

əm

for s in evaluate_regular_expression(('ə', '∘', ('m', '∪', 'g'))):
    print(s)

əm
əg

for i, s in enumerate(evaluate_regular_expression(('ə', '*'))):
    print(s)
    
    if i > 10:
        break

ə
əə
əəə
əəəə
əəəəə
əəəəəə
əəəəəəə
əəəəəəəə
əəəəəəəəə
əəəəəəəəəə
əəəəəəəəəəə

for i, s in enumerate(evaluate_regular_expression((('ə', '∪', 'm'), '*'))):
    print(s)
    
    if i > 10:
        break

ə
m
əə
mm
əəə
mmm
əəəə
mmmm
əəəəə
mmmmm