上下文無抽吸引理

Question

下列語言環境是否免費？

L = {a^i b^k c^r d^s | i+s = k+r, i,k,r,s >= 0} 

我試圖拿出一個上下文無關文法來生成，但我不能，所以我假設它不是上下文無關。至於通過矛盾我的證明：

假設L是免費的背景下，

令P是由泵引理給出的常數，

選擇串S = A^PB^PC^PD^P其中S = uvwxy

As | vwx | < = p，則至多VWX可以包含兩個不同的符號：

情況a）VWX只包含單一類型的符號的，因此UV^2wx^2Y將導致I + S = K + R

！

情況b）VWX包含兩種類型的符號：

我）VWX由b的和C的，因此UV^2wx^2Y將導致I + S = K + R

現在我的問題是！如果vwx由a和b組成，或者c和d組成，那麼抽出它們就不會破壞語言，因爲i和k或s和r可以一致地增加，導致i + s == k + r。

我做錯了什麼或者這是一種上下文無關語言？

Answer 1

我不能想出一個CFG來在我的頭頂生成特定語言，但是我們知道，如果某種下推自動機能夠識別它，那麼語言就是上下文無關的。

設計這樣的PDA不會太困難。一些想法讓你開始： 我們知道i + s = k + r。等價地，i-k-r + s = 0（我按順序寫它，因爲這是它們出現的順序）。如果（k + r）> i，問題的癥結在於決定如何處理堆棧。

如果您不熟悉PDA或不能使用它們來回答問題，至少您現在知道它是無背景的。

祝你好運！

Answer 2

這裏是接受這個語言的語法：

A -> aAd 
A -> B 
A -> C 
B -> aBc 
B -> D 
C -> bCd 
C -> D 
D -> bDc 
D -> ε