Regular expressions



In [1]:

    
from tock import *

Regular expressions in Tock use the following operators:

| or ∪ for union
concatenation for concatenation
* for Kleene star

This is very similar to Unix regular expressions, but because a symbol can have more than one character, consecutive symbols must be separated by a space. Also, for the empty string, you must write ε (or &). The empty set is written as ∅.

To create a regular expression from a string (Sipser, Example 1.56):



In [2]:

    
r = RegularExpression.from_str('(a b|a)*')
r









    Out[2]:




(a b ∪ a)*

However, there isn't much you can do with a RegularExpression object other than to convert it to an NFA.

From regular expressions to NFAs



In [3]:

    
m = from_regexp(r)          # from RegularExpression object
m = from_regexp('(a b|a)*') # a str is automatically parsed into a RegularExpression

The regular expression is converted into a finite automaton, which you can view, as usual, as either a graph or a table.



In [4]:

    
to_graph(m)



In [5]:

    
to_table(m)

The states are numbered according to the position in the regular expression they came from (so that listing them in alphabetical order is natural). The letter suffixes are explained below.

We can also pass the display_steps=True option to show the automata created for all the subexpressions.



In [6]:

    
m = from_regexp('(a b|a)*', display_steps=True)









    




subexpression: a






    











    




subexpression: b






    











    




subexpression: a b






    











    




subexpression: a






    











    




subexpression: a b ∪ a






    











    




subexpression: (a b ∪ a)*

From NFAs to regular expressions

The to_regexp function converts in the opposite direction:



In [7]:

    
e = to_regexp(m)
e









    Out[7]:




ε ∪ a* a ∪ (ε ∪ a* a) (a b (ε ∪ a* a))* a b (ε ∪ a* a)

The resulting regular expression depends a lot on the order in which states are eliminated; Tock eliminates states in reverse alphabetical order.

Again, the display_steps option causes all the intermediate steps of the conversion to be displayed.



In [8]:

    
e = to_regexp(m, display_steps=True)









    











    




eliminate q8






    











    




eliminate q7






    











    




eliminate q6






    











    




eliminate q5






    











    




eliminate q4






    











    




eliminate q3






    











    




eliminate q2






    











    




eliminate q1