NPDA для L = {w ∈ {a, b} *: количество a в два раза больше количества b}

Question

Я пытался найти NPDA для этого языка, но не могу придумать ничего, что могло бы принять все слова на этом языке. Я действительно пытался сделать его условием приема пустой стек и использовать алфавит стека {$ ab}, но, может быть, мне стоит попробовать что-нибудь еще?

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

Посмотрев дважды, A->a можно удалить и иметь только:

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

Тест :

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