語言的上下文無關語法的數量多於bs

問題是爲語言開發一個上下文無關文法，該語言包含的所有字符串的數量都多於B。語言的上下文無關語法的數量多於bs

我想不出合乎邏輯的解決方案。有沒有辦法解決這些問題，有什麼可以幫助我更好地處理這些問題？有人可以提出一個合理的方法來分析這樣的語法問題嗎？

2016-04-01 nino

你能描述的語言，你想生成更準確？例如，「aabbaba」是一個有效的字符串？ – blazs

@blazs是aabbaba是一個有效的字符串，對a或b的順序沒有限制。我能夠寫出語法的情況下，當Bs跟隨的情況下，但給定的問題的普遍性是艱難的 – nino

以下語法生成的{a,b}上的所有字符串的a比b的更多。我用eps表示空字符串。

S -> Aa | RS | SRA 
A -> Aa | eps 
R -> RR | aRb | bRa | eps

很明顯它總是「比b小號的產生更多的a。這是它產生了{a,b}所有可能的字符串不太明顯有更多a的比b的

生產R -> RR | aRb | bRa | eps生成所有平衡的字符串（這是很容易看到），以及生產A -> Aa生成語言a*（即字符串零或更多a's）。

這裏是語法背後的邏輯。請注意，如果w=c1,c2,c3,...,cn是一個超過{a,b}的字符串，其中a的數量多於b，那麼我們總是可以將它分解爲一系列平衡字符串（即相同數量的a和b，其中包括空字符串）和字符串形式爲a+。

例如，ababaaaba = abab（可由R生成），aaa（可由A生成），ba（可由R生成）。

現在請注意，生產S -> Aa | RS | SRA會生成這種形式的精確字符串。

這足以驗證S涵蓋下列情況下（因爲所有其他情況下，可以通過闖入這樣子情況，你應該確認支付）：

2016-04-01 15:52:26 blazs

有嚴格的不平等，數量的As和Bs的數量不能相等 – nino

是的，謝謝，我剛剛注意到並糾正了答案。 – blazs

您能否解釋解決方案背後的邏輯和思考過程？這會有很大的幫助。在此先感謝 – nino

另一種可能是簡單的解決辦法：

S->A|AAB|BAA|e A->AA | a B->AB | BA | b

2016-05-04 15:35:29

回答