grammar - 查找该语言的语法

Question

我需要找到以下语言的上下文无关语法：

L= { w 从 { a,b,c,d }* : #a+2#b=2#c+#d }

这是我的尝试，但我怀疑它是否正确：

S -> aSd|dSa|BSC|CSB|abSdc|baScd|dcSab|cdSba|SS|λ
B -> c|dd
C -> b|aa 

Answer 1

您可以构建一个识别语言的 PDA，如下所示：

• 输入中的字符a和b对应a于堆栈上。
• 字符c和d对应c的堆栈。
• 如果堆栈为空或顶部是a, 并且a在输入上，则使用它并推a送到堆栈。
• 如果堆栈为空或顶部是a, 并且b在输入上，则使用它并推aa送到堆栈。
• 如果堆栈为空或顶部是c, 并且c在输入上，则使用它并推cc送到堆栈。
• 如果堆栈为空或顶部是c, 并且d在输入上，则使用它并推c送到堆栈。
• 如果栈顶在c并且a在输入上，则使用a并弹出c.
• 如果栈顶在c并且b在输入上，则使用b并弹出c，移动到一个特殊的状态，要么弹出另一个，要么在堆栈为空时c压入一个。a
• ...
• 接受状态是输入和堆栈都是空的。

这意味着您必须能够构建 CFG。我认为你在正确的轨道上，但是这个 CFG 写起来会很痛苦，因为没有排序限制。这意味着您将有许多相同基本规则的排列。