Давайте начнем с КПК для ^ nb ^ m, где m> = n.КПК может помещать a в стек для каждого a, который он видит, выдвигать ab для каждого b, который он видит, и если у него заканчивается b, пока в стеке еще есть a, он отклоняет.
Теперь,что еще нам нужно сделать, чтобы исключить случай, когда m - n нечетно?Ну, m - n нечетно означает, что у нас есть некоторые b на входе.Мы можем просто изменить наше принимающее состояние, чтобы при дальнейшем b оно переходило в новое состояние (кодирование нечетного b) и затем возвращалось в принимающее состояние в следующем b, кодируя требование, чтобы остаточный b был четным.
Полный КПК может выглядеть следующим образом:
q s S q' S'
q0 a Z q0 aZ
q0 a ax q0 aax
q0 b Zx q2 Z
q0 b ax q1 x
q1 b ax q1 x
q1 b Z q2 Z
q2 b Z q1 Z
Проверьте, чтобы убедиться, что он работает, могут быть некоторые ошибки.Это можно прочитать следующим образом:
Из состояния q на входе s с конфигурацией стека S КПК может перейти в состояние q 'и обновить конфигурацию стека до S'.