Week 3: 2017/01/30-02/03

In [1]:
from tock import *

Monday reading

Read Section 1.3, but you can save Lemma 1.60 and its proof for next time.

Tuesday class

Regular expressions

Regular expressions were invented by Stephen Kleene (pronounced clay-knee) back in the 1950s as a characterization of the languages recognized by the earliest neural networks. But they became widely used through various Unix tools, like grep, which is where you have likely encountered them.

Regex Golf

There are some differences between Unix regular expressions and true regular expressions. True regular expressions have three operations: concatenation, union ($\cup$ in the book, | in Unix), and Kleene star (*). The order of operations is star, then union, then concatenation. Use parentheses to change the order of operations, just as in arithmetic expressions.

Unix regular expressions use a dot (.) to match any symbol; the book uses $\Sigma$ for this purpose.

Another difference is that Unix regular expressions usually match anywhere in a string, whereas true regular expressions usually must match the entire string. When using grep, use the -Ex flags to approximate true regular expressions (-E to get the union operator, -x to match the whole line).

In [2]:
%%file movies.txt
the phantom menace
attack of the clones
revenge of the sith
a new hope
the empire strikes back
return of the jedi
the force awakens
rogue one
the last jedi
the motion picture
the wrath of khan
the search for spock
the voyage home
the final frontier
the undiscovered country
generations
first contact
insurrection
nemesis
into darkness
beyond
Overwriting movies.txt
In [3]:
!grep -Ex '.*(m | (t|n)|b).*' movies.txt
the phantom menace
attack of the clones
revenge of the sith
a new hope
the empire strikes back
return of the jedi
beyond

Almost right.

Question. Can you fix the regular expression so that it also accepts the force awakens, rogue one, and the last jedi, but not beyond?

Converting regular expressions to NFAs

Regular expressions are the third "model of computation" of this course, and they, too, are equivalent to both DFAs and NFAs. The proof involves algorithms to convert between regular expressions and NFAs. Today we're converting regular expressions to NFAs, which is, I think, not as difficult as the subset construction from last time.

The algorithm in the book is a slight variation on the algorithm from a paper by Ken Thompson, one of the co-developers of Unix, for the QED editor, from which are descended sed, grep, and vi. (But many modern regular expression engines actually do not use this algorithm, but one that is asymptotically much slower!)

Here's a step by step visualization of the example from the book. You can try different regular expressions to see how they get converted. (Note that in Tock, unlike in Unix tools, symbols in regular expressions are separated by spaces.)

In [4]:
m = from_regexp('(a b|a)*', display_steps=True)
subexpression: a
%3 _START 0 q1 _START->0 1 q2 0->1 a
subexpression: b
%3 _START 0 q3 _START->0 1 q4 0->1 b
subexpression: a b
%3 _START 1 q1 _START->1 0 q3 2 q4 0->2 b 3 q2 1->3 a 3->0 ε
subexpression: a
%3 _START 1 q5 _START->1 0 q6 1->0 a
subexpression: a b|a
%3 _START 1 q7 _START->1 0 q3 2 q4 0->2 b 4 q5 1->4 ε 5 q1 1->5 ε 3 q6 4->3 a 6 q2 5->6 a 6->0 ε
subexpression: (a b|a)*
%3 _START 0 q8 _START->0 2 q7 0->2 ε 1 q3 4 q4 1->4 b 5 q5 2->5 ε 6 q1 2->6 ε 3 q6 3->2 ε 4->2 ε 5->3 a 7 q2 6->7 a 7->1 ε
In [5]:
m = from_regexp('(a|b)* a b a', display_steps=True)
subexpression: a
%3 _START 1 q01 _START->1 0 q02 1->0 a
subexpression: b
%3 _START 0 q03 _START->0 1 q04 0->1 b
subexpression: a|b
%3 _START 1 q05 _START->1 0 q01 2 q02 0->2 a 1->0 ε 4 q03 1->4 ε 3 q04 4->3 b
subexpression: (a|b)*
%3 _START 4 q06 _START->4 0 q01 1 q02 0->1 a 3 q05 1->3 ε 2 q04 2->3 ε 3->0 ε 5 q03 3->5 ε 4->3 ε 5->2 b
subexpression: a
%3 _START 0 q07 _START->0 1 q08 0->1 a
subexpression: b
%3 _START 0 q09 _START->0 1 q10 0->1 b
subexpression: a
%3 _START 0 q11 _START->0 1 q12 0->1 a
subexpression: (a|b)* a b a
%3 _START 10 q06 _START->10 0 q10 2 q11 0->2 ε 1 q09 1->0 b 11 q12 2->11 a 3 q01 4 q02 3->4 a 6 q07 4->6 ε 7 q05 4->7 ε 5 q08 5->1 ε 6->5 a 7->3 ε 8 q03 7->8 ε 9 q04 8->9 b 9->6 ε 9->7 ε 10->6 ε 10->7 ε

Question. If a regular expression has $n$ symbols, how big will the resulting NFA be?

For a very cool "real-time" visualization of (a slightly different version of) this construction, see Debuggex.

Wednesday reading

Read or reread Lemma 1.60 and its proof, which (in my opinion) is the most complicated one so far.

Thursday class

Homework 2 is due this evening.

NFAs to regular expressions

Today we're completing the proof from last time by converting NFAs to regular expressions. The algorithm for this is known as the state elimination algorithm, because it eliminates the states of the NFA one by one.

To make this construction simpler, the new concept of a generalized NFA (GNFA) is introduced. In this course, GNFAs are a "throwaway" formalism; they exist just to make this proof possible. But elsewhere they might be useful in their own right.

A GNFA is a NFA whose transitions can be labeled with regular expressions instead of symbols. The algorithm first changes the NFA into a GNFA, and then eliminates the states one by one. When there is just one transition left, its label is the final answer.

The order of elimination is arbitrary, although some orders may lead to more compact regular expressions than others. Tock eliminates states in reverse alphabetical order, for no particularly good reason.

In [6]:
m66 = read_csv('sipser-1-66.csv')
m66
%3 _START 0 1 _START->0 0->0 a 1 2 0->1 b 1->1 a b
In [7]:
to_regexp(m66, display_steps=True)
%3 _START 0 start _START->0 3 1 0->3 ε 1 accept 2 2 2->1 ε 2->2 a|b 3->2 b 3->3 a
eliminate 2
%3 _START 0 start _START->0 2 1 0->2 ε 1 accept 2->1 b (a|b)* 2->2 a
eliminate 1
%3 _START 0 start _START->0 1 accept 0->1 a* b (a|b)*
Out[7]:
a* b (a|b)*
In [8]:
m68 = read_csv('sipser-1-68.csv')
m68
%3 _START 0 1 _START->0 1 2 0->1 a 2 3 0->2 b 1->0 a 1->1 b 2->0 b 2->1 a
In [9]:
to_regexp(m68, display_steps=True)
%3 _START 0 start _START->0 4 1 0->4 ε 1 accept 2 2 2->1 ε 2->2 b 2->4 a 3 3 3->1 ε 3->2 a 3->4 b 4->2 a 4->3 b
eliminate 3
%3 _START 0 start _START->0 3 1 0->3 ε 1 accept 2 2 2->1 ε 2->2 b 2->3 a 3->1 b 3->2 a|b a 3->3 b b
eliminate 2
%3 _START 0 start _START->0 2 1 0->2 ε 1 accept 2->1 b|(a|b a) b* 2->2 b b|(a|b a) b* a
eliminate 1
%3 _START 0 start _START->0 1 accept 0->1 (b b|(a|b a) b* a)* (b|(a|b a) b*)
Out[9]:
(b b|(a|b a) b* a)* (b|(a|b a) b*)

(The answer is different from the book's because the elimination order was different.)