形式语言理论变换文法描述涉及变换文法作为形式语言的表述手段。例如，语言Lɑ可通过变换文法表示为{S→ɑ,S→ɑS}，该文法包含两条变换规则。每一步变换都通过替换文法的左侧规则的右侧实现。S作为起始点，代表Lɑ中的任何可能句子。例如，句子ɑɑɑɑɑ通过S→ɑS→ɑɑS→ɑɑɑS→ɑɑɑɑS→ɑɑɑɑɑ的推导生成，共进行五步，前四步使用第二条规则，第五步使用第一条规则。按照此方法，可以生成Lɑ中的所有句子，即整个Lɑ语言。

变换文法严格定义为四元组G=（∑，V，S，P），其中∑是字母表或终结符号表，V是变量表或非终结符号表，S是起始符号，P是变换规则或产生式的集合，所有集合都有限且∑与V无交集，S属于V。α和β分别代表∑∪V)+和（∑∪V)*中的元素，表示用β替换α的产生式属于P。此定义的文法称为零型文法，或短语结构文法。由零型文法生成的语言称为零型语言。每个零型语言都是递归可枚举集，反之亦然。

在零型文法中，通过限制|α|≤|β|，得到一型文法。由一型文法生成的语言称为一型语言。一型文法的定义是所有产生式取γAδ→γωδ的形式，其中γ，ω，δ∈（V∪∑）*，|ω|>0，A∈V，直观上表示在左有γ，右有δ的环境下，A可以被ω替换。因此，一型文法和一型语言分别称为上下文有关文法和上下文有关语言。

如果要求一型文法中α∈V，则得到二型文法，亦称为上下文无关文法，它生成的语言称为二型语言或上下文无关语言。

扩展资料

形式语言理论（formal language theory）是用数学方法研究自然语言（如英语）和人工语言（如程序设计语言）的产生方式、一般性质和规则的理论。形式语言是模拟这些语言的一类数学语言，它采用数学符号，按照严格的语法规则构成。从广义上说，形式语言是符号取自某个字母表的字符串的集合。

本文地址： http://www.goggeous.com/20241228/1/957366

文章来源：天狐定制

版权声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。