Автомат для (a ^ n b ^ n) ^ m c ^ m

Question

Я застрял при создании функций перехода для этого автомата.

Полагаю, мне нужно сложить 1 для каждого a и разложить его для каждого b

Количество с равно количеству пар ab, поэтому я думаю, что я должен составлять 0 для каждого b, с которым я сталкиваюсь. Дело в том, как я могу развернуть 1 и добавить 0 одновременно?

Answer 1

Не помещайте 0 в стек каждый раз, когда вы сталкиваетесь с b. Вместо этого нажимайте 0 на стек каждый раз, когда вы сталкиваетесь с b, и стек пуст или вершина стека составляет 0.

Итак, используя вашу номенклатуру для 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

Стек пуст, поэтому мы принимаем эту строку.