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

Question

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

Answer 1

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

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上使用>