將下面的語法轉換爲喬姆斯基範式。給所有的中間步驟。將文法轉換爲喬姆斯基常態？
S -> AB | aB
A -> aab|lambda
B -> bbA
行，所以我做的第一件事就是添加一個新的開始變量S0
所以我現在
S0 -> S
S -> AB | aB
A -> aab|lambda
B -> bbA
然後我刪除了所有的拉姆達規則：
S0 -> S
S -> AB | aB | B
A -> aab
B -> bbA | bb
然後我檢查了S->S和A->B類型不存在的規則。這就是我提出的答案，我需要做更多的事情還是我做錯了什麼？
維基說：
在計算機科學中，上下文無關文法被認爲是喬姆斯基範式，如果它的所有生產規則的形式爲：
- 一個 - > BC ，或
- 甲 - >α，或
- 小號 - >ε
其中甲，乙，Ç是終結符，α是一個終端符號，小號是開始符號，並且ε是空字符串。而且，B和C都不是開始符號。
繼續您的工作：
S0 -> S S -> AB | aB | B A -> aab B -> bbA | bb
而不是使用|來表示不同的選擇，拆分規則到多個規則。
S0 -> S S -> AB S -> aB S -> B A -> aab B -> bbA B -> bb
創建新規則Y -> a和Z -> b因爲我們很快就會需要他們。
S0 -> S S -> AB S -> aB S -> B A -> aab B -> bbA B -> bb Y -> a Z -> b
S -> aB是形式S -> BC不是因爲a是一個終端。因此，改變a到Y：
S0 -> S S -> AB S -> YB S -> B A -> aab B -> bbA B -> bb Y -> a Z -> b
做同樣的B -> bb規則：
S0 -> S S -> AB S -> YB S -> B A -> aab B -> bbA B -> ZZ Y -> a Z -> b
對於A -> aab，創建C -> YY;爲B -> bbA，創造D -> ZZ：
S0 -> S S -> AB S -> YB S -> B A -> CZ C -> YY B -> DA D -> ZZ B -> ZZ Y -> a Z -> b
對於S -> B，複製一個規則，其中發生在右側S和內聯規則：
S0 -> B S0 -> S S -> AB S -> YB A -> CZ C -> YY B -> DA D -> ZZ B -> ZZ Y -> a Z -> b
處理規則S0 -> B和S0 -> S通過將右側加入到左側其他規則的手邊。此外，刪除孤立的規則（其中LHS符號永遠不會在RHS使用）：
S0 -> DA S0 -> ZZ S0 -> AB S0 -> YB A -> CZ C -> YY B -> DA D -> ZZ B -> ZZ Y -> a Z -> b
，我們就大功告成了。唷！
備選答案：語法只能產生串的數量有限，即6
S -> aabbbaab | aabbb | bbaab | bb | abbaab | abb.
您現在可以凝聚這回喬姆斯基範式手。
通過替換，我們可以找到所有生成的字符串的集合。您最初的規則：
S -> AB | aB.
A -> aab | lambda.
B -> bbA.
先拆了S規則：
S -> AB.
S -> aB.
現在替代哪些A和B擴展爲：
S -> AB
-> (aab | lambda) bbA
-> (aab | lambda) bb (aab | lambda).
S -> aB
-> abbA
-> abb (aab | lambda).
再次展開這些獲得：
S -> aabbbaab.
S -> aabbb.
S -> bbaab.
S -> bb.
S -> abbaab.
S -> abb.
若要將此有限集更改爲Chomsky標準形式，只需通過強力操作即可，無需任何智能因式分解。首先，我們介紹兩種終端的規則：
X -> a.
Y -> b.
現在對於每個字符串，我們消耗了終端變量的第一個字母，並用新的變量剩餘的字母。例如，像這樣：
S -> aabbb. (initial rule, not in Chomsky Normal Form)
S -> XC, where X->a and C->abbb.
C -> XD, where X->a and D->bbb.
D -> YE, where Y->b and E->bb.
E -> YY, where Y->b and Y->b.
我們只是通過這個過程的所有6個字符串，產生了很多新的中間變量。
不錯，即開即用的答案。你能否詳細說明你是如何提出這個問題的，以及如何將它轉化爲喬姆斯基常態？ –
@MatthiasWeiler感謝您的建議。編輯完成。 – Nayuki
沒有深入的理論和證明（你可以在維基百科中看到這個），在將上下文免費語法轉換爲喬姆斯基範式時，你必須做一些事情，你通常必須執行四個標準形式轉換。首先，您需要直接或間接識別可以產生空字符串（lambda/epsilon）的所有變量（無Lambda形式）。其次，你需要刪除單位制作 - （無單位表格）。第三，你需要找到所有生活/有用的變量（有用性）。四，你需要找到所有可到達的符號（Reachable）。在每一步你可能會或可能沒有新的語法。因此，對於你的問題，這是我想出了...
上下文無關文法
G(Variables = { A B S }
Start = S
Alphabet = { a b lamda}
Production Rules = {
S -> | AB | aB |
A -> | aab | lamda |
B -> | bbA | })
刪除的λ/小量
ERRASABLE(G) = { A }
G(Variables = { A S B }
Start = S
Alphabet = { a b }
Production Rules = {
S -> | AB | aB | B |
B -> | bbA | bb | })
刪除單元produtions
UNIT(A) { A }
UNIT(B) { B }
UNIT(S) { B S }
G (Variables = { A B S }
Start = S
Alphabet = { a b }
Production Rules = {
S -> | AB | aB | bb | bbA |
A -> | aab |
B -> | bbA | bb | })
確定活的符號小號
LIVE(G) = { b A B S a }
G(Variables = { A B S }
Start = S
Alphabet = { a b }
Production Rules = {
S -> | AB | aB | bb | bbA |
A -> | aab |
B -> | bbA | bb | })
刪除可達
REACHABLE (G) = { b A B S a }
G(Variables = { A B S }
Start = S
Alphabet = { a b }
Production Rules = {
S -> | AB | aB | bb | bbA |
A -> | aab |
B -> | bbA | bb | })
與固體非終結符替換所有混合串
G(Variables = { A S B R I }
Start = S
Alphabet = { a b }
Production Rules = {
S -> | AB | RB | II | IIA |
A -> | RRI |
B -> | IIA | II |
R -> | a |
I -> | b | })
喬姆斯基範式
G(Variables = { V A B S R L I Z }
Start = S
Alphabet = { a b }
Production Rules = {
S -> | AB | RB | II | IV |
A -> | RL |
B -> | IZ | II |
R -> | a |
I -> | b |
L -> | RI |
Z -> | IA |
V -> | IA | })
檢查時，你讀的第一件事[維基百科（http://en.wikipedia.org/wi文/ Chomsky_normal_form）？ – Nayuki
澄清請求：什麼是lambda？它是一個終端符號嗎？ – Nayuki
是的，爲什麼？我不知道最後一條規則是什麼意思。 Lambda是維基百科中的Epsilon，它在空格 – tehman