grammar - 我的解决方案对于这种上下文无关语法是否正确？

Question

我正在尝试解决这个问题（我想我可能已经解决了）：http ://d.pr/i/L5Qm

L = {a ³ⁿ b ²ⁿ | n >= 0}

基本上问题是说不l等于m或m不等于n

我生成的规则：

S -> aaaSbb | A
A -> a | ^

几个测试：

Test one: S --> aaaSbb -> aaaAbb -> aaabb
Test two: S --> A -> a
Test three: S --> A -> ^

我敢肯定还有很多我可以测试的，但我不太确定如何测试大多数问题，因为我对这些问题还很陌生。我很感激任何帮助。

Answer 1

你的测试二：

Test two: S --> A -> a

清楚地表明你的语法是错误的！

用您的语言：

L = {a ³ⁿ b ²ⁿ | n >= 0}

a每两个总是有三个b，并且a不是语言 L。

适合您的语言的正确作品是：

S ---> aaaSbb | ^

^空符号在哪里。通知^也是语言，因为n可以0。

编辑：

你的语法：

S -> aaaSbb | A
A -> a | ^

产生两种语言的联合，即：

{a ³ⁿ b ²ⁿ | n >= 0} U {a ³ⁿ⁺¹ b ²ⁿ | n >= 0}

额外的部分 a ³ⁿ⁺¹ b ²ⁿ是由于A--> a生产。