Automata & Formal Languages Formula Sheet

Math for CS · Axiom Academy

FORMULA SHEET Automata & Formal Languages Quick reference for definitions, closure properties, and key theorems Union, intersection, difference Homomorphism, inverse homomorphism Union, concatenation, Kleene star Intersection with a regular language Recognizable (RE): some TM accepts every w L ; may loop on w L . Decidable: some TM halts on every input and answers correctly. Co-recognizable: complement is recognizable. A_ : does DFA M accept string w ? EQ_ : do two DFAs recognize the same language? A_ : does CFG G generate w ? (CYK, O(n^3) ) Membership for context-sensitive languages (PSPACE) EQ_ : do two TMs recognize the same language? EQ_ : do two CFGs generate the same language? Rice's theorem: any non-trivial property of L(M) is undecidable Hilbert's tenth problem (Diophantine solvability)

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