Правила И Символы Автомата
y*) -- (s0 , a*a , h0F*T) --
(s0 , $ , $).
Отметим, что последовательность правил, используемая построенным автоматом, соответствует левому выводу входной цепочки:
E Þ E+T Þ T+T Þ F+T Þ a+T Þ a+T*F Þ a+F*F Þ a+a*F Þ a+a*a.
Если по такому выводу строить дерево, то построение будет происходить сверху вниз, т.е. от корня дерева к листьям.
Рис. Дерево, соответствующее левому выводу цепочки a+a*a.
.
Такой способ построения дерева по заданной цепочке называется нисходящим.
Магазинные автоматы называют часто распознавателями, поскольку они определяют, является ли цепочка, подаваемая на вход автомата, допустимой или нет, и следовательно, отвечают на вопрос, принадлежит ли эта цепочка языку, пораждаемому грамматикой, использованной для построения автомата.
Учитывая характер построения вывода в магазине, автоматы рассмотренного типа называют нисходящими распознавателями.
Еще раз подчеркнем, что доказательство допустимости цепочки нисходящим магазинным автоматом (НМА) предусматривает поиск определенной последовательности конфигураций.
Такой поиск может существенно увеличить время работы автомата. Детерминированные автоматы не требуют поиска и работают быстрее, поэтому именно такие автоматы применяются на практике. Детерминированные автоматы-распознаватели могут быть построены не для всех, а только для некоторых видов КС-грамматик.
Определение. Если язык L допускается детерминированным М-автоматом , то он называется детерминированным языком. |
Учитывая значение детерминированных автоматов для практических применений, посвятим им последующие разделы.