構建上下文無關文法

我怎樣才能構建一個上下文無關文法下列語言：構建上下文無關文法

L = {a^l b^m c^n d^p | l+n==m+p; l,m,n,p >=1}

我開始通過嘗試：

S -> abcd | aAbBcd | abcCdD | aAbcdD | AabBcCd

然後A =別的東西......但我無法得到這個工作。

。

我想知道我們怎麼能記住有多少c的shud增加爲沒有。 b的增加了嗎？
例如：

string : abbccd

來源

2012-10-17 Sameer Jain

爲什麼不是上下文？ –

（正如我回答的語法所示），我對這個問題的解決方法是1.試着寫語法（我失敗了）2.嘗試證明它不是上下文無關的（我失敗了）3.試着寫語法再次（我成功了）....我寫了評論，但堅持2. :) –

語法是：

S1 - > a S1 d | S2
S2 - >S3S4
S3 - >一個S3 C |小量
S4 - >S5S6
S5 - >乙S5Ç| epsilon
S6 - > c S6 d | epsilon

規則1增加了相等數量的a和d。

規則3增加了相等數量的a和b。

規則5增加了相等數量的b和c。

第六條增加了C'S的數目相等並且D

的規則也保證了字母的順序是按照給定的語言保持。

來源

2014-05-05 17:33:27

怎麼樣這個問題：

S1 -> a S2 d     # at least one a and d 
S2 -> a S2 d 
S2 -> S3 S4     # no more d, split into ab and bc parts 
S2 -> S4 S5     # no more a, split into bc and cd parts 

S3 -> a S3 b 
S3 ->       # already ensured at least one a and b 
S4 -> b S4 c     
S4 -> b c      # at least one b and c 
S5 -> c S5 d 
S5 ->       # already ensured at least one c and d

這裏的關鍵是如何組...（即「零件」，而不是非終端）

來源

2012-10-17 12:29:22

構建上下文無關文法

回答

相關問題