Notes on Formal Language Theory and Parsing

Contents 1 REGULAR LANGUAGES 1 1.1 Regular Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Non-Deterministic Finite-State Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.1 Converting a regular expression to a NFA - Thompson's Algorithm . . . . . . . . . . . . . . . . 3 1.2.2 Kleene's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.3 Converting a NFA to a Regular Expression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Deterministic Finite-State Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.1 Constructing a DFA from an NFA ("Subset Construction") . . . . . . . . . . . . . . . . . . . . 5 1.4 DFA minimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Further Properties of Regular Languages . . . . . . . .