形式语言中形式语法四种类型的通俗理解

it2024-06-27  46

形式语法在乔姆斯基的语法理论中被分为以下四种类型:

1.0型文法(无约束文法)

如题,没什么约束

2.1型文法(上下文有关文法)

对任一产生式α→β,都有|β|>=|α|, 仅仅 S→ε除外产生式的形式描述:α1Aα2→α1βα2 (其中,α1、α2、β∈(VN∪VT)*,β≠ε,A∈VN)即:被替换的A只有出现在α1α2的上下文中,才允许用β替换。

3.2型文法(上下文无关文法)

产生式的形式描述:A→β(A∈VN),即β取代A时,与A所处的上下文无关。

3.3型文法(正则文法)

每个产生式均为 “A→aB”或“A→a” —— 右线性,  “A→Ba”或“A→a” —— 左线性;其中,A、B∈VN,a∈VT*

最新回复(0)