Week 02 · Sipser 1.3 · Part I

One class, three notations

Type an expression. Thompson's construction turns it into an NFA, the subset construction turns that into a DFA, and all three accept exactly the same strings. That chain is Theorem 1.54, and you can watch each link of it below.

The expression

| or + is union, juxtaposition is concatenation, * is star, eps is ε and empty is ∅. Precedence: star, then concatenation, then union.

fully parenthesised —

Thompson NFA

Does it match?

—

Every string over the alphabet up to length 4, matched ones marked. Compare this with what you meant the expression to say.

Parse tree

Definition 1.52 is inductive, so an expression really is a tree. If this tree is not the one you intended, your brackets are wrong.


        

      

      

        
Sizes

        

      

      

        
Not the same as "regex"

        

          
Java, Python and PCRE patterns allow backreferences:
            (\w+)\1 matches exactly the doubled strings ww, which
            is not a regular language. Those engines cannot compile to a DFA, so they backtrack — and
            (a+)+b then takes exponential time on aⁿc. That is
            ReDoS, and it is why Go's and Rust's engines drop backreferences on purpose.