Introduction to Automata & Formal Languages

Math for CS · Axiom Academy

Computation models, languages, and the Chomsky hierarchy An automaton (plural: automata) is an abstract mathematical model of a computing device. It reads input, follows rules to transition between states, and either accepts or rejects the input. Automata theory is the foundation of: Compiler design — lexers and parsers are built on finite automata and grammars Regular expressions — regex engines are finite automata under the hood Computability theory — what problems can be solved at all? Complexity theory — what resources (time, space) are needed? Verification — model checking hardware and software String: A finite sequence of symbols from . Example: w = 01101 . The empty string is denoted . Language ( L ): A set of strings over . Example: . denotes the set of all strings over , including . A language is any subset — it can be finite, infinite, or even empty. The central question of automata theory: given a language L , can we build a machine that decides membership? That is, given a string w , can the machine determine whether ? Different types of machines can recognize different classes of languages. More powerful machines recognize more complex languages — but at a cost of requiring more resources. Noam Chomsky (1956) classified languages into four levels based on the grammar rules that generate them and the machines that recognize them: Each level is a strict superset of the previous: starts and ends with the same symbol — matching counts require memory

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