喬姆斯基正常形式 - 計算理論

這是例如

S--> AB | ɛ 

A--> aASb | a 

B--> bS

我試圖解決這個

S --> [A] [B] 

[A] --> [aA] [Sb] | [a] 

[aA] --> [a] A 

[Sb] --> s [b] 

[a] --> a 

[b] --> b

我不知道答案。有人可以告訴我這是對還是錯？

來源

2010-12-13 cool

不太正確的論壇爲您的問題。嘗試在此張貼：http://cstheory.stackexchange.com/ – 2010-12-13 17:26:29

您的答案不會生成空白字。 – 2010-12-13 17:27:23

@尼科：絕對不是。 cstheory是*研究級*問題的網站。此外，基本的CS問題一直是主題。 – sepp2k 2010-12-13 17:33:48

一個錯誤是您刪除了S --> ɛ轉換。您需要（即使AnyNonTerminalOtherThanS --> ɛ不是S --> ɛ是特別允許在CNF中）。

然後規則[A] --> [a]，應該是[A] --> a，因爲如果你在RHS只有一個項目，它需要是一個終端。

[aA] --> [a] A 
[Sb] --> s [b]

這兩個看似錯別字爲A和s不存在。你的意思可能是：

[aA] --> [a] [A] 
[Sb] --> [S] [b]

除此之外，你有什麼是正確的。

來源

2010-12-13 17:32:32 sepp2k

@ sepp2k-謝謝，這是有道理的。 – cool 2010-12-13 17:41:00

@ sepp2k-我很抱歉，但我沒有包括[A] - > [a]規則，就像您之前提到的那樣。雖然我的觀點是，如果在RHS上只有一個項目，那麼它應該是終端。 – cool 2010-12-13 17:45:49

@ sepp2K-嗨！我有一個請求。我在這裏問了一個問題http://stackoverflow.com/questions/13143186/example-of-non-linear-unambiguous-and-non-deterministic-cfl。 - 可以清除我的疑問。 – 2012-11-02 11:03:23

喬姆斯基正常形式 - 計算理論

回答

相關問題