语义

小步语义

小步语义类似对代数式迭代求值。

大步语义

大步语义的意思是，对于大的表达式，先求它的小表达式，然后把结果结合起来得到最终的答案。这通常意味着递归

操作语义（operational semantic）

想象一个理想、抽象的计算机，操作语义为程序在某些机器上的执行定义一些规则。

指称语义（denotional semantic）

用一种低级、更形式化的语言来解释当前的语言。

状态机的分类

确定性有限自动机

finite state machine -> finite automaton

deterministic finite automaton 是确定性有限自动机的意思

我们的领域模型的状态机最好是这种状态机。

非确定性有限自动机

NFA
能被一台特定机器接受的字符串集合称为一种语言：我们说这台机器识别了这种语言。

任何 NFA 等价于 DFA

确定性下推自动机

PushDown Automaton pda。

这种状态机可以处理无限多的中间状态。

确定型图灵机

Deterministic Turing Machine DTM

可以解决所有可判定/可计算问题

停机问题不可解，即任意问题都可能是不可终止的。