什麼是 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+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習