非限制性语法

在自动机理论中，非限制性语法类（也称为半休、0型或短语结构语法）是乔姆斯基层次中最一般的语法类。对非限制性语法的生成没有任何限制，只是它们的每个左手边都是非空的。这类语法可以生成任意的递归可列举语言。

一个非限制性语法是一个形式语法G=(N,T,P,S){textstyleG=(N,T,P,S)}。是一个特别指定的起始符号。顾名思义，非限制性语法可以有的生产规则类型没有真正的限制。与图灵机的等价性非限制性语法是递归可列举语言的特征。这就等于说，对于每一个非限制性语法将磁带2上产生的句子形式与磁带1上的词进行比较。如果它们匹配，那么图灵机就会接受这个词。如果不匹配，图灵机将回到步骤1。很容易看出，这个图灵机将生成所有且只有G的句法形式。G{displaystyleG}在最后一步执行了任意次数之后，在它的第二个磁带上，因此语言必须是可递归枚举的。反过来的构造也是可能的。给定某个图灵机，有可能创建一个等效的非限制性语法，该语法甚至只使用左手边有一个或多个非终端符号的产物。因此，一个任意的非限制性语法总是可以被等效地转换为服从后一种形式，方法是将其转换为图灵机，然后再返回。一些作者使用后一种形式作为非限制性语法的定义。计算特性关于一个给定的字符串是否是s{displaystyles}是否能被一个给定的非限制性语法生成能否由一个给定的非限制性语法生成的决定问题等同于它能否被等同于该语法的图灵机所接受的问题。

后一个问题被称为Halting问题，是不可判定的。递归可列举语言在Kleenestar、concatenation、union和intersection下是封闭的，但在setdifference下不是；见递归可列举语言#Closure属性。非限制性语法与图灵机的等价性意味着存在一个通用的非限制性语法，一个能够接受任何其他非限制性语法的语言的语法，给定一个语言的描述。由于这个原因，理论上有可能建立一种基于非限制性语法的编程语言（例如Thue）。