模块 13: 语言与计算的边界

形式语言是字母表上字符串的集合。确定有限自动机包含状态、初始状态、每符号转移与接受状态。偶数个一的二进制串可用偶奇两状态，零不变、一切换，接受偶。空串接受。奇偶仅需有限记忆，但任意平衡括号需要无界嵌套计数或栈，有限自动机一般无法提供。

词法把字符分为整数、运算符等记号，解析按文法构建语法树。文法为表达式含加法项，项含乘法因子，因子为整数或括号表达式。项先吸收乘法，所以乘法优先。2+3*4 的树为 +(2,*(3,4))，不是 *(+(2,3),4)。解析必须消耗全部输入，不能忽略尾部记号。

解释器执行表示的含义，编译器转换到另一表示。AST 求值递归计算子值再应用运算。语法有效不同于语义有效，带除法语言可解析 1/0 却求值失败。真实系统可编译字节码再解释或即时编译，因此类别可共存。错误需区分词法、结构与执行阶段。

判定过程需对每个有效输入终止并回答是或否。假设 H(P,x) 总能判定 P 在 x 上是否停机。构造 D(P)：若 H(P,P) 说停，则永远循环，否则停机。考察 D(D)：H 说停则循环，说循环则停，两种都矛盾，因此能表达该构造的计算模型中不存在通用停机判定器。

仍可证明特定程序终止，或判定受限有限系统。超时不是通用判定，不能区分很久后终止与无限运行。

P 是对编码长度多项式时间可解的判定问题，NP 的是答案具有多项式大小证书并可多项式验证。NP 不是非多项式，P 包含于 NP。路线判定在合适界下可用路线作证书。NP 完全问题属于 NP，且每个 NP 问题可多项式归约到它。归约保持是非答案。P 与 NP 仍未解决，NP 难不同于不可判定。

下载脚本，在终端中使用 Python 3.11 或更新版本运行：python m13_automaton.py. Windows 也可使用 py -3；部分系统使用 python3。实验仅用标准库。先预测结果，再运行并完成变体。不要使用 -O，以保留断言。下方输出由构建器实际运行捕获，两种语言使用相同代码与输出。

两状态机器接受偶奇偶性并拒绝字母表外符号。

下载 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. 改为接受奇数。
2. 画转移表。
3. 增加是否出现零的状态。

分别跟踪词法、AST 构造与求值，并限制输入与嵌套。

下载 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. 计算 2*(3+4*5)。
2. 尝试不匹配括号与尾部记号。
3. 设计减法并保留左结合。

先尝试，再展开解答。★ 应用概念；★★ 结合概念；★★★ 进行设计或证明。

选择答案查看反馈，重置后可重做。无需 JavaScript 也可阅读答案表。

• MIT 计算理论课程 — 阅读自动机、不可判定与复杂度概要，区分三者。

求值前画 AST，凭记忆解释停机矛盾。模块 14 将整合为测试过的目录应用。