Поместите себя в состояние духа пуш-апа.Все, что вы знаете, как это делать, это читать ввод и стек, а затем нажимать / выталкивать и изменять состояние в зависимости от того, что вы видите.Если вы начинаете читать строку и хотите сказать, на каком языке она написана, что вы можете сделать?
Мне кажется, лучшее, что мы можем сделать, начиная с начала, - вспомнить, сколько a s мы читаем,Пока мы не увидим b s, нет никаких причин делать что-либо еще.То есть просто прочитайте a s и поместите их в стек.Следующих правил должно быть достаточно:
Q i s Q' s'
-- -- -- -- --
q0 a Z q0 aZ
q0 a a q0 aa
Теперь, что происходит, когда мы видим b?Если мы хотим по крайней мере вдвое больше b с, чем a с, мы не можем просто пересечь a с для каждого b, поскольку это даст по крайней мере столько же b с, сколько a s, но не как минимум вдвое больше.
Что если мы вычеркнем два a s для каждого b?Что ж, это дает нам как минимум вдвое меньше b с a с, что является неправильным направлением.Это предполагает пересечение одного a на каждые два b s, что оказывается правильным.Правила:
Q i s Q' s'
-- -- -- -- --
q0 b a q1 a
q1 b a q2 -
q2 b a q1 a
Обратите внимание, что мы создали новое состояние q2, которое имеет одно общее с q0 правило, но не для чтения a s.Действительно, как только мы начинаем читать b s, мы не хотим больше разрешать чтение a s.Выход из правил приведет к сбою автомата и отклонению строки.
Если у нас будет ровно вдвое больше b с, чем a с, мы окажемся в состоянии q2 без ввода и вывода.пустой стек.Если у нас есть дополнительные b s, нам нужно правило, чтобы разрешить их.Достаточно добавить самоконтроль для состояния q2:
Q i s Q' s'
-- -- -- -- --
q2 b Z q2 Z
Взятые вместе, эти состояния и переходы должны быть довольно близки к рабочему КПК для вашего языка.Другими вариантами было бы сначала написать CFG, а затем применить алгоритм для преобразования CFG в КПК, например, анализатор сверху вниз или снизу вверх.