Skip to content
Tutorials Center
My learning

Topics

Lesson 56 of 68 ยท Computation and Languages

Context-Free Grammars, Pushdown Automata and Turing Machines

Climb the Chomsky hierarchy: write context-free grammars, simulate pushdown automata with a stack, and run a Turing machine, with Python simulators.

Automata and Regular Languages ended with a limitation: a finite automaton cannot count without bound, so it cannot recognize 0โฟ1โฟ or balanced parentheses. To go further we add memory. A stack gives you a pushdown automaton, which recognizes the context-free languages (the ones programming-language syntax is made from). A tape you can read and write gives a Turing machine, which captures everything that can be computed at all.

These machine types form the Chomsky hierarchy: each level recognizes strictly more languages than the one below.

Level Grammar Machine Example language
Regular regular finite automaton strings ending in 01
Context-free context-free pushdown automaton 0โฟ1โฟ, balanced parentheses
Recursively enumerable unrestricted Turing machine anything computable

(There is also a context-sensitive level between the last two; we skip it here.)

Context-free grammars

A context-free grammar (CFG) has variables (written in capitals), terminals (the real symbols), a start variable and productions of the form A โ†’ string. "Context-free" means each rule rewrites a single variable no matter what surrounds it. To derive a string, start from the start variable and keep replacing variables by the right-hand side of a production until only terminals remain.

The grammar S โ†’ 0 S 1 | ฮต (where ฮต is the empty string) generates 0โฟ1โฟ: S โ‡’ 0S1 โ‡’ 00S11 โ‡’ 0011. Balanced parentheses are S โ†’ ( S ) S | ฮต. Arithmetic expressions use E โ†’ E + T | T, T โ†’ T * F | F, F โ†’ ( E ) | number, where the layering of rules gives * higher precedence than +.

Python Generating strings from a grammar

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each string appears because some sequence of leftmost replacements derives it. A parse tree records one derivation as a tree, and a grammar is ambiguous if some string has two different parse trees, as E โ†’ E + E | E * E | n does for 1 + 2 * 3.

Pushdown automata

A pushdown automaton (PDA) is a finite automaton with a stack. On each step it reads an input symbol (or none), looks at the top of the stack, and may push or pop. It accepts if it ends in an accepting state (or, in a common variant, with an empty stack). The stack is exactly the missing memory: it can count the zeros and then match them against the ones.

For 0โฟ1โฟ: push a marker for every 0; on each 1, pop a marker; accept if the input ends exactly when the stack becomes empty. For balanced parentheses: push on (, pop on ), reject if you pop from an empty stack, accept if the stack ends empty.

Python Pushdown automata with a stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A PDA with its single stack still cannot recognize 0โฟ1โฟ2โฟ (the stack is emptied by the time the twos arrive) or ww (a word followed by an identical copy). Those need more power.

The Chomsky hierarchy

Regular Finite automaton, no memory.
Context-free Pushdown automaton, one stack.
Computable Turing machine, a tape to read and write.

Each level recognizes strictly more languages.

1 / 2

Turing machines

A Turing machine has a finite set of states and an infinite tape divided into cells. A head sits on one cell. On each step, depending on the current state and the symbol under the head, the machine writes a symbol, moves the head left or right, and switches state. It halts when it reaches an accepting or rejecting state, or it may run forever.

Despite its simplicity, this model can simulate any algorithm you can write in any programming language. The Church-Turing thesis says that whatever is effectively computable is computable by a Turing machine. The machine can read and write unboundedly, so it can recognize 0โฟ1โฟ2โฟ and ww and it can compute functions such as incrementing a binary number.

The machine below adds 1 to a binary number. It walks right to the end of the digits, then walks left turning trailing 1s into 0s until it finds a 0 (or blank) to flip to 1.

Python A Turing machine that increments a binary number

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every row matches Python's own arithmetic. The rule table is the machine's whole "program": states are its memory of what it is doing (scanning, or carrying), and the tape holds the data.

What Turing machines tell us

Because Turing machines are precise, mathematicians could prove that some problems have no algorithm. The best known is the halting problem: no program can decide, for every program and input, whether it eventually stops. The proof is a short diagonal argument, similar to the one for uncountable sets. This sets a hard limit on what software can do, and it is the starting point of computability theory and complexity theory (P versus NP).

A language is decidable if some Turing machine always halts with the right yes/no answer. It is recognizable if some machine halts and accepts exactly the members, but may loop on non-members. Every decidable language is recognizable; the halting problem is recognizable but not decidable.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a pushdown automaton have that a finite automaton lacks?

    The stack gives it unbounded memory used in last-in, first-out order.
  2. 2. Which language needs at least a pushdown automaton (it is not regular)?

    Matching an unbounded count of zeros with ones needs a stack.
  3. 3. A context-free grammar rule has which form?

    Context-free rules replace one variable at a time, without looking at its surroundings.
  4. 4. What does the halting problem show?

    It is a proven limit of computation: some well-defined yes/no questions have no algorithm.

Summary

  • The Chomsky hierarchy orders language classes: regular, context-free, then Turing-recognizable, each more powerful than the last.
  • Context-free grammars generate nested structure; pushdown automata (a finite automaton plus a stack) recognize exactly those languages.
  • A Turing machine has an unbounded read-write tape and models every algorithm, according to the Church-Turing thesis.
  • Some problems, such as the halting problem, are undecidable: no Turing machine solves them.

Continue with Recursion and Algorithm Analysis.