在 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 | 正則語法 | 正則語言 | 有限狀態自動機 |
喬姆斯基層次結構如下圖所示:
廣告