无限制文法
在形式语言理论中,无限制文法是对文法的产生式左右两侧都没有限制的形式文法。这是乔姆斯基层级中最一般性的文法类,它们可以识别任意的递归可枚举语言。
无限制文法是形式文法 ,这里的
是非终结符的集合,
是终结符的集合,这里的
和
是无交集的(实际上这个限制不是必需的,因为无限制文法在非终结符和终结符之间不做真实区分,存在这个指定纯粹是为了使得你在尝试生成文法的句子形式的时候知道何时停止),
是形如
的产生规则的集合,这里的
和
是在
中的符号的字符串而
是非空字符串,
是特别指定的开始符号。如名称所暗含的,在无限制文法可以有什幺类型的产生规则上没有真实限制。