證明語言是無上下文的抽象引理

Question

我有一個測試來使用抽象引理來證明一種語言是否無上下文。我試圖解決一些練習問題，事情並沒有那麼好...

練習問題是： 對於a）到j），證明下列語言是否是上下文無關的。如果它是無上下文的，則提供一個生成它的上下文無關語法。

前兩個是：

a) {a^(2i+1) b^(3k+2) c^(4k+3) d^(5i+4) | i >= 0, k >= 0} 

b) {a^i b^i c^k d^i | i >= 1, k >= 1} 

如果有人能解決前兩個，給予他們是如何做一個詳細的解釋，我相信我能找出其餘的（C通過j）在我自己的。

Answer 1

一個是上下文無關：

A -> aBdddd 
B -> aaBddddd 
B -> C 
C -> bbbCcccc 
C -> D 
D -> bbccc 

B不是上下文。我們假設它是。因此，我們有一個整數p，泵浦引理所持有的整數p。讓我們看一下b中的下列單詞： a^p b^p c d^p

根據抽象引理，這個單詞可以表示爲序列uvwxy，這樣| vwx | < p和U，V，^ I W X^I Y也是B.

讓我們來看看VX：

案例1：VX包含 「C」。如果是這樣的話，則uwy應該也是在B中，但是B要求我們至少有一個「c」。所以這種情況是不可能的。

案例2：vx不包含「c」。它必須包含「a」，「b」或「c」中的至多兩個（否則| vwx |會比p更多）。因此，uv^2wx^2y將不包含等於a，b和c的數目，並且也不在B中。因此，B不是上下文無關語言。因此，B不是上下文無關語言。因此，B不是上下文無關語言。因此，B不是上下文無關語言。