長度可被3整除的字符串的上下文免費語法

Question

我需要創建一個上下文無關語法，它將生成{a，b}長度爲而不是的字符串，可以被3整除。我不知道從哪裏開始有了這個。如果有人可以提供一個類似的例子或起點，將不勝感激。

Answer 1

好吧，讓我們開始做一些頭腦風暴。

• 是否每個正規語法都是上下文無關的？是。
• 我們是否知道任何正則語法使得字符串可以被3整除？那不是太難，我們做。
• 接下來的事情是從規則語法到有限自動機的轉換算法。
• 將自動機轉換爲接受補體的機器人是相當容易的（只需完成轉換函數並切換接受和不接受狀態）。
• 下一步是將有限自動機轉換回常規語法（也稱爲算法）。
• 現在我們有正則語法，從我們知道的第一行開始，每個reg。語法也是CFG。

確實有更直接的解決方案（比如說生成可以被3整除的句子形式，但是然後給它們添加1或2個字符），但是這會讓你對所有這些東西是連接的。

希望至少能回答你的問題。隨意詢問更多細節。

編輯： 我還添加了正規文法產生這樣的語言（初始非終結爲0）：

0 -> a1 | b1 | a | b 
1 -> a2 | b2 | a | b 
2 -> a0 | b0 

Basicaly什麼語法也正試圖通過3獲得字長整除，但每當它應該添加第三個字符，它不允許你終止生成。