Context-free languages, PDAs, Turing machines

A pushdown automaton (PDA), a finite automaton with a stack, checks that aabbbb has twice as many b’s as a’s in 7 moves: one push of two symbols for each a, one pop for each b, and a last move that reads nothing. A context-free grammar (CFG) generates strings by rewriting one variable at a time, whatever surrounds it, with rules such as S → aSb | ε, and the languages that grammars generate are the context-free languages (CFLs). Nondeterministic PDAs accept exactly the context-free languages, while deterministic PDAs accept fewer of them.

A Turing machine has an unbounded tape that it can read, write and move along in both directions. Turing machines compute everything that any computer can, and they define two classes: a language is decidabledecidable language: A language for which some Turing machine halts on every input and accepts exactly the strings of the language. Decidable and recursive mean the same., or recursive, when a machine halts on every input with the right answer, and recursively enumerablerecursively enumerable language: A language that some Turing machine accepts exactly, possibly running forever on strings outside it. Every decidable language is one; the halting problem is one that is not decidable. when a machine accepts exactly its strings but may run forever on the others. Each idea below comes with a program you can run.

Each machine adds one resource, and each class is strictly larger

Each class contains the classes drawn inside it, and each machine adds one resource. A finite automaton has only its states. A PDA adds a stack, which can match one count against another or a string against its reversal. A linear-bounded automaton may rewrite the tape cells of its input but no others, and Turing machines have an unbounded tape. Every inclusion is strict, and the examples show why: $a^n b^n$ needs the stack, the even palindromes need a guess of the middle, $a^n b^n c^n$ needs more than one stack can do, and HALT is recognised but never decided.

A stack lets a PDA check what a grammar generates

The grammar S → aSbb | ε generates $a^n b^{2n}$: each use of the first rule adds one a on the left and two b’s on the right. The PDA does the same work with its stack. It pushes two X’s for every a and pops one for every b, and the bottom marker Z tells it that every b has been matched. Step through its run on aabbbb:

The program prints the same configurations, then the run on aabbb, which uses up its input with an X still on the stack:

"""A deterministic PDA for a^n b^(2n), traced move by move and checked against the definition."""
from itertools import product

# (state, symbol read, top of stack) -> (next state, what replaces the top).
# A symbol of "" reads nothing; Z marks the bottom of the stack.
MOVES = {
    ("q0", "a", "Z"): ("q1", "XXZ"),  # the first a pushes two X's
    ("q1", "a", "X"): ("q1", "XXX"),  # every further a pushes two more
    ("q1", "b", "X"): ("q2", ""),     # each b pops one X
    ("q2", "b", "X"): ("q2", ""),
    ("q2", "", "Z"): ("q3", "Z"),     # every X matched: move to the accepting state
}
ACCEPTING = {"q0", "q3"}  # q0 accepts the empty string


def run(word, show=False):
    state, rest, stack = "q0", word, "Z"  # the top of the stack is its first character
    while True:
        if show:
            print(f"  {state}  input {rest or '-':7}  stack {stack}")
        top = stack[:1]
        if rest and (state, rest[0], top) in MOVES:
            state, push = MOVES[state, rest[0], top]
            rest, stack = rest[1:], push + stack[1:]
        elif (state, "", top) in MOVES:
            state, push = MOVES[state, "", top]
            stack = push + stack[1:]
        else:
            return not rest and state in ACCEPTING


for word in ("aabbbb", "aabbb"):
    print(f"{word}:")
    print("  accepted" if run(word, show=True) else "  rejected: no move left")

words = ["".join(w) for n in range(10) for w in product("ab", repeat=n)]
same = all(run(w) == (w == "a" * (len(w) // 3) + "b" * (2 * len(w) // 3)) for w in words)
print(f"agrees with a^n b^(2n) on all {len(words)} strings up to length 9: {same}")

aabbbb:
  q0  input aabbbb   stack Z
  q1  input abbbb    stack XXZ
  q1  input bbbb     stack XXXXZ
  q2  input bbb      stack XXXZ
  q2  input bb       stack XXZ
  q2  input b        stack XZ
  q2  input -        stack Z
  q3  input -        stack Z
  accepted
aabbb:
  q0  input aabbb    stack Z
  q1  input abbb     stack XXZ
  q1  input bbb      stack XXXXZ
  q2  input bb       stack XXXZ
  q2  input b        stack XXZ
  q2  input -        stack XZ
  rejected: no move left
agrees with a^n b^(2n) on all 1023 strings up to length 9: True

This PDA is deterministic: in every configuration at most one move applies. Deterministic PDAs accept exactly the deterministic CFLs, which include $a^n b^{2n}$ but not the even palindromes, where a machine would have to guess where the middle is.

Normal forms fix the length of every derivation

A grammar in Chomsky normal formChomsky normal form: A grammar form that allows only rules A → BC and A → a, plus S → ε when the language contains ε. A derivation of a string of length n then takes exactly 2n − 1 steps. derives aabb in exactly 7 steps, in whatever order it applies its rules:

• Chomsky normal form (CNF) allows only rules A → BC and A → a, so a derivation of a string of length n takes exactly 2n − 1 steps.
• Greibach normal form (GNF) starts every right-hand side with a terminal, A → aα, so a string of length n takes exactly n steps.
• The CYK algorithm decides whether a grammar in CNF generates a string of length n in $O(n^3)$ time, by filling a triangle of cells, one for each substring.
• The pumping lemma for CFLs splits every long enough string as uvxyz, with |vxy| ≤ p and |vy| ≥ 1, and pumps v and y together. $a^n b^n c^n$ fails it.
• Closure: CFLs are closed under union, concatenation, star and intersection with a regular language, but not under intersection or complement.
• Ambiguity: a grammar is ambiguous when some string has two parse trees, and no algorithm decides ambiguity for every grammar. A language is inherently ambiguous when every grammar for it is ambiguous.

Decidability shrinks as the machines grow stronger

A problem is decidable when one Turing machine answers it correctly for every input and always halts. The table gives the standard results for each class; the input is a description of the language, such as a DFA, a grammar or a Turing machine.

Two results explain most of the undecidable cells. Turing proved that no machine decides whether a given machine halts on a given input, the halting problem. Other problems are shown undecidable by reduction: if a decider for a problem P could be used to decide halting, P is undecidable. Rice’s theorem makes this general: every non-trivial property of the language that a Turing machine accepts is undecidable. Diagonalisation explains why such problems must exist: Turing machines can be listed one after another, while languages cannot.

Practise: membership, closure and decidability

ANBN = [("S", "A", "B"), ("S", "A", "C"), ("C", "S", "B")]
derives(ANBN, {"a": {"A"}, "b": {"B"}}, "S", "aabb")   # True
derives(ANBN, {"a": {"A"}, "b": {"B"}}, "S", "abab")   # False

def derives(binary, unit, start, word):
    """True when the grammar in Chomsky normal form derives `word` from `start`.

    `binary` lists the rules A -> BC as triples ("A", "B", "C"); `unit` maps each terminal
    to the set of variables that produce it (A -> a). The grammar has no rule for the empty
    string, so the empty word is never derived.
    """
    # Replace this line with your code.
    return False

from itertools import product

from membership import derives

# a^n b^n, n >= 1: S -> AB | AC, C -> SB, A -> a, B -> b.
ANBN = [("S", "A", "B"), ("S", "A", "C"), ("C", "S", "B")]
ANBN_UNIT = {"a": {"A"}, "b": {"B"}}

# Balanced brackets: S -> SS | LR | LT, T -> SR, L -> (, R -> ).
BRACKETS = [("S", "S", "S"), ("S", "L", "R"), ("S", "L", "T"), ("T", "S", "R")]
BRACKETS_UNIT = {"(": {"L"}, ")": {"R"}}


def test_anbn_members():
    """ab, aabb and aaabbb are derived"""
    assert [derives(ANBN, ANBN_UNIT, "S", w) for w in ("ab", "aabb", "aaabbb")] == [True, True, True]


def test_anbn_non_members():
    """aab, abab and ba are not derived"""
    assert [derives(ANBN, ANBN_UNIT, "S", w) for w in ("aab", "abab", "ba")] == [False, False, False]


def test_empty_word():
    """a grammar in Chomsky normal form without an empty rule never derives the empty word"""
    assert derives(ANBN, ANBN_UNIT, "S", "") is False


def test_unknown_symbol():
    """a symbol that no rule produces makes the word underivable"""
    assert derives(ANBN, ANBN_UNIT, "S", "acb") is False


def test_brackets():
    """balanced brackets are derived, unbalanced ones are not"""
    words = ["()", "(())()", "(()", ")(", "()()()"]
    assert [derives(BRACKETS, BRACKETS_UNIT, "S", w) for w in words] == [True, True, False, False, True]


def test_anbn_against_definition():
    """the same answer as the definition on every string up to length 8"""
    for n in range(9):
        for w in map("".join, product("ab", repeat=n)):
            k = len(w) // 2
            assert derives(ANBN, ANBN_UNIT, "S", w) == (k > 0 and w == "a" * k + "b" * k), w

Grammars in depth: CYK, ambiguity and normal forms, worked Pro: opens with a Pro, Premium or Ultimate pass

Closure, pumping and deterministic PDAs, with the traps reproduced Pro: opens with a Pro, Premium or Ultimate pass

Turing machines and undecidability, with reductions worked Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• CFGs and nondeterministic PDAs describe the same languages; deterministic PDAs describe fewer, without the even palindromes.
• A derivation in Chomsky normal form takes 2n − 1 steps, one in Greibach normal form n steps, and CYK decides membership in $O(n^3)$ time.
• CFLs are closed under union, concatenation and star and under intersection with a regular language, but not under intersection or complement.
• Membership, emptiness and finiteness are decidable for CFLs; equivalence and universality are not, and Rice’s theorem makes every non-trivial question about a Turing machine’s language undecidable.