formal-languages - 语法的产生规则

Question

在任何事情之前，是的，这是来自课程作业，我在处理另一个项目时偶尔会这样做。

一种语言由那些字符串（终端“a”和“b”）组成，其中 a 的数量 = b 的数量。试图找到将定义上述语言的语法的产生规则。

更正式地说，L(G) = {w | Na(w) = Nb(w)}

所以我想它应该是这样的，L = {ϵ, ab, aabb, abab, abba, bbaa, ... 等等}

任何提示，甚至与解决方案相关的问题都可以帮助我更好地掌握当前的问题。

Answer 1

我觉得这就是：

S -> empty  (1)
S -> aSb    (2)
S -> bSa    (3)
S -> SS     (4)

编辑：我改变了规则。现在这里是如何生产bbaaabab

S ->(4) SS ->(4) SSS ->(3) bSaSS ->(3) bbSaaSS -> (1)bbaaSS 
  ->(2) bbaaaSbS ->(2) bbaaaSbaSb ->(1)bbaaabaSb ->(1) bbaaabab

Answer 2

另一个提示：编写所有的生产规则，确保每一步都保证 Na(w) = Nb(w)。