PDA和CF语法，L = {w | w = {a，b} *，使得2 *（w中“ a” -s的个数）！= 3 *（w中“ b” -s的个数）+2}

Question

我在过去的考试中发现了以下问题：使用以下语言构建具有无效堆栈接受能力和CF语法的PDA：

L={w| w={a,b}* such that 2* (number of "a"-s in w) != 3* (number of "b"-s in w) +2 }

假设w = {a，b} *具有该属性。我试图构造PDA，以实现左右手之间的平等，但我认为我做对了，但我不知道如何解决不平等问题。至于CF语法，我发现它有点棘手。有人可以帮我吗？

Answer 1

[不等式（a≠b）通常被认为是两个严格比较（a> b∨b> a）的析取。如果您知道如何做a = b，那么a> b通常非常简单；您需要做的只是介绍更多信息。

举个简单的例子，{a ⁱ b ^j | i = j}很简单：

S→aSb | ε

{a ⁱ b ^j | i≠j}不太明显，但是{a ⁱ b ^j | i> j}只是

S→aSb | aS | a

和{a ⁱ b ^j | j> i}非常相似。

我想考试问题不是那么简单，但是很容易得出相同的分析结果。