L= {w ∈ {a,b}* 的 NPDA：a 的数量是 b 的两倍}

Question

我一直在尝试为这种语言寻找一个 NPDA，但我想不出任何可以接受该语言中所有单词的东西。我确实尝试将其接受条件设置为空堆栈并使用堆栈字母表 {$ a b} 但也许我应该尝试其他方法？

Answer 1

也许您正在寻找给定 Regular Expression 的等效 Grammar。
如果是这样的话，也许这个有以下作品：

S->AAb | SAAb | ASAb | AASb | AAbS
A->a

一些测试：

aab : S->AAb->aAb->aab
aaaabb : S-> AASb -> AA(AAb)b -> aaaabb

也可以检查其他示例，看看是否适合所有情况。

如果没事总要上
Result = (2*count_of_b) for a, count_b

找了两遍，A->a可以去掉只有：

S->aab|Saab|aSab|aaSb|aabS

测试：

aaaabb : aaSb(S_4)->aaaabb(S_1), etc.

NPDA for L= {w ∈ {a,b}*: number of a's is twice the number of b's}