Построение автомата толкания

Question

В моих лекциях приведен пример автомата с отталкиванием, который принимает следующий язык {(a^n) (b^n): n больше или равно нулю}.

Q - set of states ={s,p,f} 
L - alphabet = {a,b} 
R - stack = {a} 
F - accepting states ={s,f} 
D -transition relation ={ 
(s,a,e),(p,a) 
(p,a,e),(p,a) 
(p,b,a),(f,e)} 

Мой вопрос: зачем нужны состояния p и f? Не могли бы вы просто использовать состояние s?

Также мне было интересно, когда при создании КПК существует способ узнать, сколько состояний вам понадобится и каков будет алфавит стека? Или вам просто нужно решить это интуитивно?

Answer 1

В случае отсутствия состояния p, КПК будет принимать любую строку, имеющую такое же количество символов a и b.

Нет никакого неинтуитивного метода, чтобы заранее знать количество состояний или переходов, так как мы собираемся преобразовать неформальное описание в формальное, так что формального пути нет!