爲語言創建上下文無關語法

Question

我正在上有限自動機課。我正在爲期中考試做準備，因此無法爲特定語言創建語法。雖然我發現簡單的很直觀，但當它們變得更復雜時，我似乎不知道從哪裏開始。例如：

L = {瓦特E {A，B，C} *：NB（W）= NA（W）+ NC（W）}

答案是：

小號→S1 | S2
S1→bS3 | S3b | S3bS3
S3→S0 | S1
S2→XS4 | S4X | S4XS4
S4→S | S2
S0→bS0XS0 | XS0bS0 | e
X→a | c

如果任何人都可以給我一些關於思考過程的指導，那將不勝感激。

Answer 1

您列出的語言不清楚。我假設w E {a,b,c}*意味着w ε {a,b,c}*和nb(w) != na(w) + nc(w)意味着語言中的所有字符串的數量都不等於a的數量和c的數量之和。

如果是這種情況，則必須考慮將使用該語言的所有字符串的特徵以及將排除使用該語言的字符串的所有特徵。

該語言接受字符串，其中b的數量=/= a的數量+ c的數量。我們可以重新制定這種語言是一個接受字符串：

數a的+號c的>b的 或 數a的數+ c的<一些b的

這解釋了第一個S - > S1 | S2

S1確保存在至少1 b（S3），然後迫使任b的作爲a的和c的（S0）或更多b的比a的等量和（S1）。 S1規則的最終結果是字符串b的比a和c的更多。

S2確保有更多的a和/或c的比b的。它通過強制執行a或c（X），然後允許等於a的（S0）或更多的a的/ c的比b的（S2再次）。

這是專門針對你的榜樣，但你可以種看到，進入創建這個語法的思維過程如何：

1. 制定的語言作爲具體案例（a的/ c的>或< b S「S）
2. 對於每種情況下，通過確保的情況下將舉行（力＃b開始」>比a的/ c的通過迫使至少一個b），然後擴展字符串包括平等的所有可能性a's/c's和b's，或更少a's/c's比b's。
3. 對稱處理另一種情況。

問題是您需要確保生成該語言中的每個字符串，並且不生成該語言中的所有字符串。（重讀這個，直到它意味着匯入）