01Overview

In 1943 McCulloch and Pitts described neurons with logic; in 1951 Kleene proved regular expressions equivalent to finite automata. In 1956 Chomsky proposed the hierarchy: regular, context-free, context-sensitive and recursively enumerable languages, corresponding to machines of increasing power.

That hierarchy became the skeleton of the compiler: lexical analysis uses finite automata, parsing uses pushdown automata, and context-free grammars correspond directly to syntax trees. It also turned parsing from craft into a science with provable properties — whether a grammar is ambiguous, whether a language is regular, both have decision procedures.

02History

  1. 1943

    The McCulloch–Pitts neuron

    Neural activity described with logic gates.

  2. 1951

    Kleene's theorem

    Regular expressions and finite automata are equivalent.

  3. 1956

    The Chomsky hierarchy

    Formal languages classified by generative power.

  4. 1965

    LR parsing

    Knuth defines a grammar class that can be parsed efficiently.

03Core concepts

Finite automaton

Finitely many states; recognises regular languages.

Context-free grammar

Recursive rules that generate nested structure; the basis of parsing.

Pushdown automaton

Finite states plus a stack; recognises context-free languages.

04Hands-on

Do it once — it beats reading it ten times

Hand-write a regex → NFA → DFA converter that supports only tiny languages like a*b

05Self-check

Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.

Can you explain "Finite automaton"?

Finitely many states; recognises regular languages.

Can you explain "Context-free grammar"?

Recursive rules that generate nested structure; the basis of parsing.

Can you explain "Pushdown automaton"?

Finite states plus a stack; recognises context-free languages.

What problem did it solve, and why was there nothing better at the time?

Go back to the history section: how was this done before, and what did it cost?

If you had to build it today, how would you break it down?

Use the hands-on task above: write a plan of at most three steps before you start.

06Key people

N

Noam Chomsky

1928 –

The formal-language hierarchy and generative grammar.

S

Stephen Kleene

1909 – 1994

Regular expressions and automata theory.

07Further reading

  • Introduction to Automata Theory, Languages, and ComputationHopcroft & Ullman · 1979
  • Three Models for the Description of LanguageNoam Chomsky · 1956