Как построить Pushdown Automata для данного языка

Когда мы говорим об автомате выталкивания вниз (PDA), есть два типа PDA: dpda и npda. Теперь давайте просто посмотрим на вопрос, который он говорит: a^n b^m a^2m, где n,m >=1.

Теперь член a^n не окажет никакого влияния на b^ma^2m, потому что n и m не зависят друг от друга. Таким образом, этот вопрос просто разбивается на PDA b ^ m a ^ 2m, потому что только для этого термина потребуется стек, чтобы мы могли сбалансировать каждое «b» с 2 «a». Теперь так как точки переходов ясны, значит это DPDA.

КПК для данной задачи будет иметь вид:

Где «z» — начальный символ стека, а «^» — нуль, а x, y/z означает, что когда входной символ равен x, а вершина стека — y, замените вершину стека на z. Надеюсь, этот ответ поможет.

Здесь у нас есть число а, окружающих б, имеют одинаковое количество вхождений, за которыми следует независимо от количества а.

Предполагая, что m=3,n=2

Образец строки будет aabbaaa

Для автоматов Push Down конечное состояние достигается, когда стек пуст после обработки всей строки, и, следовательно, нам нужна какая-то симметрия в языке для обработки, чтобы гарантировать, что соответствующие операции извлечения происходят для каждой операции нажатия.

Таким образом, для построения КПК в этом примере было бы лучше, если бы „b; следует рассматривать как своего рода разделитель, а не элемент, который нужно поместить в стек, т. е. всякий раз, когда мы сталкиваемся с «b», мы не будем выполнять никаких конкретных действий, таким образом, рассматривая «b» как простой разделитель между начальным и конечным двумя значениями.

Требовать:

Как только мы встречаем первую последовательность, мы помещаем в стек элементы «a». Тогда, когда мы встретим «b», мы не будем выполнять никаких действий. И после того, как последовательность «b» закончится и мы встретим завершающий элемент an , мы вытолкнем элементы.

В конце операции обработки строки мы обнаруживаем, что «b» использовалось просто как разделитель между первой и последней последовательностью, и при таком использовании «b» стек в конечном итоге оказывается пустым.

Операции со стеком:

δ(S,a,z0)=(S,az0) (az0 помещен в стек)

δ(S,a,a)=(S,aa) (aa помещается в стек)

δ(A,b,a)=(A) (без операции)

δ(A,a,az0)=(A, є) (a извлекается из стека)

δ(A, є,z0)=(Q, z0) (условие пустого стека)