什么是 3 型语法？解释其特性

3 型语法是描述正则/形式语言的正则语法。

这些语法包含由以下内容组成的产生式规则：

• 左侧只有一个非终结符，

• 右侧有一个终结符，并且可以或不可以后跟非终结符。

示例

A → ε , A → a, A → b, A → aA etc.

类型

正则语法有两种类型：

• 右线性/右正则语法

• 左线性/左正则语法

让我们详细了解这两种类型的语法。

右线性语法

这是一种正则语法，其产生式规则的形式为

A → α (or) A → α B

其中，A、B → 非终结符，α → 终结符

这些语法本质上是右分支的，因为如果存在，则对最右边的非终结符进行替换。

左线性语法

这是一种正则语法，其产生式规则的形式为：

A → α (or) A → B α

其中，A 和 B 是非终结符，α 是终结符。

由于对最左边的非终结符进行替换，因此这些语法本质上是左分支的。

正则语法的特性

正则语法生成正则语言，这些语言在以下方面是封闭的：

• 并集

• 连接

• 交集

• 补集

• 差集

• 逆转

• 逆转

• 闭包

• 同态

• 逆同态。

Bhanu Priya

更新于： 2021年6月15日

1K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习