Math
Finite automata and regular expressions
Compile small regular expressions into finite automata and trace word recognition through actual subset-construction transitions.
Try this
Edit a regular expression over a and b using |, *, parentheses and concatenation. A Thompson NFA is converted to reachable DFA subsets. Read the word one letter at a time; double circles accept. Limit: 16 DFA states.
Equations used in the module
Equations
Thompson construction: symbol, concatenation, union, Kleene star
DFA start = ε-closure(NFA start)
δ(S,c) = ε-closure({q : p ∈ S and p —c→ q})
A subset accepts iff it contains the NFA accepting state
