技術來創建CFG的

我要創建一個CFG產生技術來創建CFG的

{a^n (ab)^n c^m d^l e^k | n>0, k, l, m>=0, k<m, m=l+k}

，第一部分是很容易的，我想出了

S -> aS2abS3 S2 -> aS2ab | epsilon

然而，第二部分是很混亂。到目前爲止，我有

S3 -> S4 | epsilon

我已經是我怎麼可能跟蹤所有這些變量的問題？ K必須小於m，m必須等於l + k，並且l必須至少延長1。有人能給我一些接近這些CFG的一般技巧嗎？

來源

2014-11-04 Conner R Panarella

現在回想起來，這個問題的答案就有點過頭了，因爲這是幾乎可以肯定的功課，你會了解更多盤算的事情了自己。以下是提示：PDA可以回寫;這是一個堆棧的本質。所以你總是要嘗試使字符串鏡像一種或另一種形式。 a^m b^m是鏡像的微不足道的形式（鏡子將a變成b）。這只是一個更復雜一點，但如果你專注於尋找對稱性，你會發現它。 – rici 2014-11-04 07:07:41

由內而外思考（因爲這是CFG的工作方式），不要被無關的細節弄糊塗。

下面是提示：CFG是下推自動機（PDAs），這意味着他們有一個堆棧。 PDA擅長對稱，但不能做反對稱。所以他們可以做迴文，但不能重複。這是一個堆棧的本質。

所以你總是需要尋找鏡像。例如，a^mb^m是鏡像的微不足道形式，其中鏡像將a s變成b s。

這一個只是更復雜一點，但如果你專注於尋找對稱性，你會發現它。

話雖如此，這裏的解決方案：

由於m > l，

c^md^le^k

可以改寫爲：

c^m-lc^ld^le^k

而且，由於k = m - l，這是一樣的：

c^kc^ld^le^k

從那裏是微不足道：

S_inner → cd | c S_inner d 
S_outer → S_inner | c S_outer e

來源

2014-11-04 06:58:35 rici

可能是一個愚蠢的問題，但我們怎麼稱呼蘇特？ – 2014-11-04 07:12:24

@ConnerRPanarella：如果這不明顯，可以用鉛筆和紙試一下。蘇特生產什麼？ – rici 2014-11-04 07:13:45

啊我現在明白了。這實際上不是我正在檢查的作業，這是一個實踐問題。 – 2014-11-04 07:16:55

技術來創建CFG的

回答

相關問題