无限制文法

无限制文法是形式文法 ${\displaystyle G=(N,\Sigma ,P,S)}$ ，这里的 ${\displaystyle N}$  是非终结符的集合，${\displaystyle \Sigma }$  是终结符的集合，这里的 ${\displaystyle N}$  和 ${\displaystyle \Sigma }$  是无交集的(实际上这个限制不是必需的，因为无限制文法在非终结符和终结符之间不做真实区分，存在这个指定纯粹是为了使得你在尝试生成文法的句子形式的时候知道何时停止)，${\displaystyle P}$  是形如 ${\displaystyle \alpha \to \beta }$  的产生规则的集合，这里的 ${\displaystyle \alpha }$  和 ${\displaystyle \beta }$  是在 ${\displaystyle N\cup \Sigma }$  中的符号的字符串而 ${\displaystyle \alpha }$  是非空字符串，${\displaystyle S\in N}$  是特别指定的开始符号。如名称所暗含的，在无限制文法可以有什么类型的产生规则上没有真实限制。

可以证明无限制文法特征化了递归可枚举语言。这同于声称对于所有无限制文法 ${\displaystyle G}$  都存在某个图灵机有能力识别 ${\displaystyle L(G)}$  反之亦然。给定一个无限制文法，这种图灵机足够简单构造为两磁带非确定图灵机。第一个磁带包含要被测试的输入字 ${\displaystyle w}$ ，而机器使用第二个磁带生成来自 ${\displaystyle G}$  的句子形式。图灵机接着做如下事情:

1. 开始于第二个磁带的左端并重复的选定要右移或选择在磁带上的当前位置。
2. 非确定的从 ${\displaystyle G}$  中选定一个产生式 ${\displaystyle \beta \to \gamma }$ 。
3. 如果 ${\displaystyle \beta }$  出现在第二个磁带的某个位置，在这个点上把 ${\displaystyle \beta }$  替代为 ${\displaystyle \gamma }$ ，依据 ${\displaystyle \beta }$  和 ${\displaystyle \gamma }$  的相对长度可能要把在磁带上的符号向左或右移动(就是说如果 ${\displaystyle \beta }$  长于 ${\displaystyle \gamma }$ ，左移磁带符号)。
4. 比较在磁带 2 上的结果句子形式和在磁带 1 上的字。如果匹配，则图灵机接受这个字。如果不匹配则回到步骤 1。

容易看出这个图灵机将在最后步骤被执行任意次之后在第二个磁带上生成 ${\displaystyle G}$  的所有的句子形式，所以语言 ${\displaystyle L(G)}$  必定是递归可枚举的。

相反构造也是可能的。给定某个图灵机，有可能建立一个无限制文法。

从无限制文法和图灵机的等价性上，给定一个字符串 ${\displaystyle s}$  是否属于某个无限制文法的语言的决定性问题一般是不可判定的。

给出一个语言的描述完全可能建立一个通用无限制文法有能力接受任何其他无限制文法的语言，如同有可能建立一个通用图灵机，所以在理论上有可能建造一个基于无限制文法的编程语言。

• 图灵机
• λ演算
• 字符串重写