前后文无关文法和语言

字数

295 字

阅读时间

2 分钟

一、集合的运算

集合的加法运算就是元素和： $A + B = {w | w \in A 或 w \in B}$
$A B = {x y | x \in A 且 y \in B}$

二、文法G[S]

四、文法和语言的Chomsky分类

0型文法：产生式左边至少存在一个非终结符（大写字母），如： $1 A \to 1 A B$
1型文法：产生式左边的长度 $\leq$ 产生式右边的长度
- $a \to ε$ 也是1型文法
2型文法：产生式左边只能有一个非终结符（大写字母）
3型文法：根据产生式右边的非终结符位置可分为左线性文法和右线性文法
- 左线性文法：产生式右边的非终结符位置在最左侧，如： $A \to a | A a | B c$
- 右线性文法：产生式右边的非终结符位置在最右侧，如： $A \to a | a B | b B$

六、正规式到NFA

正规式的三条规则：

贡献者

freeway348

文件历史

最后编辑于 17 天前查看完整历史