Автомат нажатия (a ^ x b a ^ y c a ^ x + y)

Question

Мой друг задал мне вопрос о автомате.abacaa.Я смотрю на некоторые похожие проблемы, но все проблемы содержат четные числа, такие как 0 ^ a 1 ^ a, но теперь у меня есть 3 значения.Я нашел пример об этом, но я не могу перевести мой вопрос в это.

aabbabcc:

read a push 1
read a push 1
read b pop 1
read b pop 1
stack is empty so push 0
read a push 1
read b pop 1 
top of stack is 0 so push 0
read c pop 0
read c pop 0

Как я могу преобразовать абака?

Answer 1

Я знаю, что это было здесь некоторое время, но на всякий случай, если кто-нибудь ищет похожие вопросы ... зачем перефразировать это?

Основная идея такова: у пуш-апа у автомата есть стек. Итак, читайте столько а, сколько хотите, каждый раз добавляя по стеку дополнительное «а». Затем прочитайте b и перейдите в следующее состояние.

Теперь прочитайте столько, сколько хотите, снова, снова помещая все в стек. Затем прочитайте c и перейдите в следующее состояние.

Теперь читайте a, пока вы смотрите на a в верхней части стека. Когда вы смотрите на символ нижней части стека, переходите в окончательное состояние принятия.

Если у вас больше а, переходов нет, и ваша строка не принята (вы не закончили чтение, и вам некуда идти, поэтому вы «зависаете» на машине). В противном случае, если у вас закончились символы a в предыдущем состоянии, вы никогда не дойдете до конечного состояния и ваша строка не будет принята. Только если вы просто прочитали столько раз, сколько вы делали в первые два раза, вы окажетесь в состоянии принятия и больше не будете читать, и строка будет принята.