在 TOC 中解釋喬姆斯基層次結構


喬姆斯基層次結構表示不同機器接受的語言類別。

喬姆斯基層次結構

根據喬姆斯基的語法層次結構如下所述,根據語法型別:

型別 0 - 無限制語法

無限制語法 - 無限制語法是 4 元組 (T,N,P,S),它包括:

T = 終結符集

N = 非終結符集

P = 產生式集,形式為:

v->w

其中 v 和 w 是由非終結符和終結符組成的字串。

S = 稱為起始符號

示例 - 圖靈機 (TM)

型別 1 - 上下文相關語法

所有產生式都具有以下形式:

v -> w 其中 |v| < |w|

uAv -> uwv 其中 w != epsilon,

即,A -> w,但僅在 u _ v 的上下文中。

上下文相關語法等價於線性有界上下文相關語言

示例 - 線性有界自動機 (LBA)

型別 3 - 上下文無關語法 -

所有產生式都具有以下形式:

A -> x - 其中 A 是非終結符,x 是非終結符和終結符的字串,上下文無關語法等價於下推自動機 (PDA)上下文無關語言

示例 - 下推自動機 (PDA)

型別 3 - 正則語法

所有產生式都具有以下形式:

A -> xB

A -> x 其中 A、B 是非終結符,x 是終結符字串。

正則語法等價於正則集有限自動機

示例 - 有限自動機 (FA)

語法型別語法接受語言接受自動機
型別 0無限制語法遞迴可列舉語言圖靈機
型別 1上下文相關語法上下文相關語言線性有界自動機
型別 2上下文無關語法上下文無關語言下推自動機
型別 3正則語法正則語言有限狀態自動機

喬姆斯基層次結構如下圖所示:

更新於:2021 年 6 月 16 日

11K+ 次觀看

啟動您的 職業生涯

透過完成課程獲得認證

開始
廣告