Unit 9 Summary

Math for CS · Axiom Academy

SUMMARY Unit 9 — Automata & Formal Languages Everything you should know before the unit assessment A formal language is a set of strings drawn from a finite alphabet . Theory of computation studies which languages can be recognized by which kinds of machines — and which can't be recognized at all. Three big questions drive the unit: What can a fixed-memory machine recognize? (regular languages) What can a stack-based machine recognize? (context-free languages) What can any machine recognize, ever? (recursively enumerable languages, and the limits of computation) 2. Regular Languages: DFAs and NFAs Deterministic Finite Automaton (DFA) A 5-tuple M = (Q, , , q_0, F) where : Q Q is total. After reading any input, the machine is in exactly one state. M accepts w if its run ends in a state of F . Nondeterministic Finite Automaton (NFA) Same tuple, but : Q ( \ \ ) (Q) . The machine can be in many states at once and may follow -transitions for free. The class of languages recognized by DFAs (equivalently NFAs) is the class of regular languages . 3. Regular Expressions and Kleene's Theorem A regular expression over is built from the constants , , and each a , combined with three operators: Kleene star: R^* (zero or more repetitions) Closure properties of regular languages If L_1, L_2 are regular, so are: L_1 L_2 , L_1 L_2 , L_1 L_2 , L_1^* , , L_1 - L_2 , reversal, and homomorphic images. Pumping lemma for regular languages

This is the written version of the interactive lesson above. See the full Math for CS course.