資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學編譯器設計中的喬姆斯基層次結構是什麼？
喬姆斯基層次結構是一組不同的形式語法。使用這種形式語法，可以生成一些形式語言。它們可以透過多種型別的裝置來定義，這些裝置可以識別這些語言，例如有限狀態自動機、下推自動機、線性有界自動機和圖靈機。
喬姆斯基提出了四種不同的短語結構語法類別，如下所示：
0型文法（無限制文法） - 0型文法對替換規則沒有任何限制。左邊的字串中必須出現非終結符。生成的語言稱為遞迴可列舉語言。
因此，0型文法是：
一個終結符字母表∑。
一個包含起始符號的非終結符字母表∀。$\sum\cup V,′α′$包含至少一個非終結符，並且對′β′沒有限制。0型文法由圖靈機識別。讓我們考慮一個例子，文法G可以表示為：
G=(V,T,P,S)
V=set of non−terminals={A,B,C}
T=set of terminals={a}
S=start symbol={A}產生式P如下所示：
A→AB
AB→BC
B→α
1型文法（上下文有關文法） - 如果文法滿足以下條件，則該文法被稱為1型文法或上下文有關文法：
每個產生式都形如α→β，並且α的長度小於或等於β的長度，即沒有空產生式，其中右側是空字串∈。
每個產生式都形如α1Aα2→ α1 βα2，其中$β≠∈$。可以構造圖靈機來識別由上下文有關文法 (CSG) 生成的上下文有關語言。假設文法 G (V, T, P, S) 是上下文有關語言的一個例子，其中
V={A,B,C}
T={a,b}
S={A}
產生式由下式給出：
A→AB
AB→BC
C→ab
2型文法（上下文無關文法） - 如果產生式形如 A→α，其中 A 是非終結符，而 α 是一個語義形式，即 α ∈ (V ∪T)∗，即 α 可以是 ∈，則該文法被稱為上下文無關文法/2型文法。產生式的左側必須只包含一個非終結符。
2型文法可以用下推自動機識別。假設文法 G(V,T,P,S)=({S},{a,b},P,S)，其中 P 包含 S→aSa|bSb|a|b 是上下文無關文法的例子。
3型文法（正則文法） - 如果產生式形如 A→a 或 A→aB，即每個產生式的左側只應包含一個非終結符，或者右側的第一個符號必須是終結符，並且可以後跟一個非終結符，則該文法被稱為3型文法。
由該文法生成的語言由有限狀態機識別。這些正則語言也可以用更簡單的表示式來表示，稱為正則表示式。
2K+ 次瀏覽
