[Verse 1] Empty set and epsilon start the show Literals match the characters we know Concatenation puts them side by side Union gives us choices to decide Kleene star means zero or more repeats Building patterns that our language meets [Chorus] Regular expressions, patterns we design Empty, epsilon, literals combine Concatenate and union, star for repetition Thompson builds the NFA with precision State elimination takes us back again Regular expressions, NFAs, DFAs - they're all the same [Verse 2] Plus means one or more, not zero this time Question mark is optional by design Character classes bracket ranges neat A through Z makes matching complete Extended operators make life easier still But basic syntax gives us all the skill [Chorus] Regular expressions, patterns we design Empty, epsilon, literals combine Concatenate and union, star for repetition Thompson builds the NFA with precision State elimination takes us back again Regular expressions, NFAs, DFAs - they're all the same [Bridge] Thompson's construction breaks it down One rule per operator, piece by piece compound Start with simple parts then build them up Compositional method fills our cup When we need to go the other way State elimination saves the day Remove each state but keep the paths Convert the NFA back with math [Verse 3] Three forms but one class of languages Regular expressions, NFAs with advantages DFAs deterministic and clean Converting between them, what does it mean? They all describe the very same sets Equivalence that we won't forget [Chorus] Regular expressions, patterns we design Empty, epsilon, literals combine Concatenate and union, star for repetition Thompson builds the NFA with precision State elimination takes us back again Regular expressions, NFAs, DFAs - they're all the same [Outro] From regex to machine and back once more Automata theory opens up the door Patterns, states, and transitions too Regular languages coming through
← 3 NFA → DFA Conversion (Subset Construction) | 5 Closure Properties of Regular Languages →