Module 13: Languages and limits of computation

A formal language is a set of strings over an alphabet. A deterministic finite automaton has states, a start state, a transition for each symbol and accepting states. For binary strings with an even count of ones, use even and odd states: zero keeps the state; one toggles it; accept even. Empty input is accepted. Finite memory suffices for parity, but arbitrary balanced parentheses require an unbounded nesting count or stack, which a finite automaton cannot generally provide.

Lexing groups characters into tokens such as integers and operators. Parsing checks how tokens fit a grammar and constructs a syntax tree. Our grammar is expression=term ('+' term)*; term=factor ('*' factor)*; factor=integer or '(' expression ')'. Multiplication binds tighter because terms absorb products before expressions combine sums. The tree for 2+3*4 is +(2,*(3,4)), not *(+(2,3),4). A parser must consume the entire input; accepting a valid prefix while ignoring extra tokens is a bug.

An interpreter executes the meaning of a representation; a compiler translates it to another representation. An AST evaluator recursively computes child values and applies their operator. Syntax validity is distinct from semantic validity: a language with division could parse 1/0 yet fail during evaluation. Real language systems may compile to bytecode and then interpret or JIT-compile it, so the categories can coexist. Error reports should identify whether tokenisation, structure or execution failed.

A decision procedure must return yes or no and terminate for every valid input. Suppose H(P,x) always decides whether program P halts on input x. Construct D(P): if H(P,P) says halts, loop forever; otherwise halt. Ask what D(D) does. If H says it halts, D loops; if H says it loops, D halts. Either answer contradicts H's claimed correctness. Therefore no such general halting decider exists in a computational model able to express this construction.

This does not forbid proving termination for particular programs, or deciding restricted finite systems. A time limit is not a general decider: exceeding it cannot distinguish a long terminating run from an infinite one.

P contains decision problems solvable in polynomial time in encoded input length. NP contains decision problems whose yes answers have polynomial-sized certificates verifiable in polynomial time. NP does not mean 'not polynomial', and P is contained in NP. For a route-length decision problem, a proposed route can serve as a certificate under suitable bounds. NP-complete problems are in NP and every NP problem reduces to them in polynomial time. A reduction maps instances while preserving yes/no answers. P versus NP remains open; NP-hardness differs fundamentally from undecidability.

Download each script and run it in a terminal with Python 3.11 or later: python m13_automaton.py. On Windows, py -3 is an alternative; on some systems use python3. The labs use only the standard library. Predict the result before running, then complete the variations. Run without -O so assertions remain enabled. Outputs below were captured by the builder. Code and output are identical in both language editions.

A two-state machine accepts even parity and rejects symbols outside its alphabet.

Download m13_automaton.py

"""DFA recognising binary strings containing an even number of ones."""
def accepts(text):
    state = 0
    for symbol in text:
        if symbol not in "01": raise ValueError("binary alphabet required")
        if symbol == "1": state = 1 - state
    return state == 0

for text in ["", "0", "1", "11", "101", "111"]:
    result = accepts(text)
    print(repr(text), "accepted:", result)
    assert result == (text.count("1") % 2 == 0)
try:
    accepts("102")
except ValueError:
    print("invalid symbol rejected")

'' accepted: True
'0' accepted: True
'1' accepted: False
'11' accepted: True
'101' accepted: True
'111' accepted: False
invalid symbol rejected

1. Change acceptance to odd parity.
2. Draw the transition table.
3. Add a second state component for whether any zero has appeared.

Trace tokenisation, AST construction and evaluation separately. Input length and nesting are bounded.

Download m13_interpreter.py

"""A bounded recursive-descent interpreter: integers, +, *, parentheses."""
import re
def tokens(source):
    if len(source) > 200: raise ValueError("expression too long")
    result, position = [], 0
    while position < len(source):
        if source[position].isspace(): position += 1; continue
        match = re.match(r"[0-9]+|[+*()]", source[position:])
        if not match: raise ValueError("invalid character")
        result.append(match.group()); position += len(match.group())
    return result

class Parser:
    def __init__(self, source):
        self.items, self.position = tokens(source), 0
    def peek(self):
        return self.items[self.position] if self.position < len(self.items) else None
    def take(self):
        value = self.peek()
        if value is None: raise ValueError("unexpected end")
        self.position += 1; return value
    def expression(self, depth=0):
        node = self.term(depth)
        while self.peek() == "+":
            self.take(); node = ("+", node, self.term(depth))
        return node
    def term(self, depth):
        node = self.factor(depth)
        while self.peek() == "*":
            self.take(); node = ("*", node, self.factor(depth))
        return node
    def factor(self, depth):
        if depth > 20: raise ValueError("nesting too deep")
        token = self.take()
        if token == "(":
            node = self.expression(depth+1)
            if self.take() != ")": raise ValueError("missing closing parenthesis")
            return node
        if not token.isdecimal(): raise ValueError("integer expected")
        return int(token)
    def parse(self):
        node = self.expression()
        if self.peek() is not None: raise ValueError("trailing input")
        return node

def evaluate(node):
    if isinstance(node, int): return node
    op, left, right = node
    a, b = evaluate(left), evaluate(right)
    return a+b if op == "+" else a*b

for source in ["2+3*4", "(2+3)*4", "7"]:
    tree = Parser(source).parse()
    print(source, "tree:", tree, "value:", evaluate(tree))
assert evaluate(Parser("2+3*4").parse()) == 14
for source in ["", "2+", "(2+3", "2 3", "__import__('os')"]:
    try: Parser(source).parse()
    except ValueError: print(repr(source), "rejected")
    else: raise AssertionError("invalid expression accepted")

2+3*4 tree: ('+', 2, ('*', 3, 4)) value: 14
(2+3)*4 tree: ('*', ('+', 2, 3), 4) value: 20
7 tree: 7 value: 7
'' rejected
'2+' rejected
'(2+3' rejected
'2 3' rejected
"__import__('os')" rejected

1. Evaluate 2*(3+4*5).
2. Try unmatched parentheses and trailing tokens.
3. Design subtraction's grammar and evaluation while preserving left associativity.

Try before opening the solution. ★ applies an idea; ★★ combines ideas; ★★★ asks for design or proof.

Choose an answer for feedback; reset to retry. A text answer key is available without JavaScript.

• MIT computation course — Read the automata, undecidability and complexity lecture summaries; keep the three notions separate.

Draw the AST before evaluating and explain the halting contradiction from memory. Module 14 combines the series into a tested catalogue application.