查找該語言的文法

Question

{a ^m b ⁿ c ⁱ | m> n + i}

我一直試圖弄清楚這兩個小時。這是我迄今爲止所擁有的。

//To start with as many a's as you want: 
S => a | aA | aS 
//To ensure an a gets added each time a b or c does so there is always at least 1 more a than b's plus c's. 
A => aBb | aaBbCc | aCc 
B => aBb | lambda 
C => ??? 

我知道這是不正確的，這就是爲什麼我要求幫助/提示。

謝謝。

Answer 1

你的語法不正確。

閱讀Tips for creating 「Context Free Grammar」和鏈接的答案是，你的語言的語法是

S --> aSc | B // for every `c` there must be a `a` 
B --> aBb | A // for every `b` there must be a `a` 
A --> aA | a // generate extra `a` 

Answer 2

從內到外建立起來：

• 乙→ ABB | ＆小量;             - 匹配的^我 b ^我
• Ç→ ACC |乙          - 匹配的^{I + J} b ^我Ç^Ĵ
• 小號→ AC |作爲          - 在前面

這不是最小的添加至少一個多 - 你可以用5個規則和2個非終端的做到這一點。