计算理论中的四类语言及其关系

整理自书本¹。
四类语言分别是正则语言（regular）、上下文无关语言（context-free）、可判定语言（decidable）和图灵可识别语言（Turing-recognizable）。其关系如下图所示：

解释一下这几种语言的含义。
书上定义3.5²：
如果一个语言能够被某图灵机所识别，那么称这个语言是图灵可识别的（Turing-recognizable）。
图灵可识别语言也可以称为递归可枚举语言（recursively enumerable language）。
注意，图灵机对于某个输入字符串，只会产生三种输出，即接受（accept）、拒绝（reject）和循环（loop）。
然而，循环和拒绝比较难区分，我们不知道它是真的陷入循环了，还是仅仅因为执行时间长，尚未退出。所以，我们希望有仅包含接受和拒绝这两种输出的图灵机，这种图灵机成为判定机（decider）。
书上定义3.6²：
如果一个语言能够被某图灵机所判定，那么称这个语言是图灵可判定的（Turing-decidable）或者是可判定的（decidable）。
图灵可判定语言也可以称为递归语言（recursive language）。
书上定义2.2³：
上下文无关文法是一个四元组(V, $\sum$∑, R, S)，该四元组满足以下四个条件。

1. V是有限集，称为变量集（variables），即非终结符集，
2. $\sum$∑是有限集，脱离于V，称为终结符（terminals）集。
3. R是包含产生式规则的有限集，每条规则都是一个非终结符连接一串终结符和非终结符，
4. S是开始符号，是V的子集。

符合上下文无关文法的语言是上下文无关语言。
书上定理2.20⁴：
某语言是上下文无关的当且仅当有某个下推自动机可以识别它。
书上定义1.52⁵：
如果一个语言能够被某个有限自动机所识别，那么称这个语言为正则语言。