Формальные языки


Пример построения автомата - часть 2


(s0 , $ , $).

Отметим, что последовательность правил, используемая построенным автоматом,  соответствует левому выводу входной цепочки:

E Ю E+T  Ю   T+T  Ю

F+T Ю a+T  Ю a+T*F  Ю a+F*F  Ю a+a*F  Ю  a+a*a.

Если по такому выводу строить дерево, то построение будет происходить
сверху вниз, т.е. от корня дерева к листьям.
 

       

Такой способ построения дерева по заданной цепочке называется нисходящим.


Магазинные автоматы называют часто распознавателями, поскольку они определяют, является ли цепочка, подаваемая на вход автомата, допустимой или нет, и следовательно, отвечают на вопрос, принадлежит ли эта цепочка языку, пораждаемому грамматикой, использованной для построения автомата.
Учитывая характер построения вывода в магазине, автоматы рассмотренного типа называют нисходящими распознавателями.


Еще раз подчеркнем , что доказательство допустимости цепочки нисходящим магазинным автоматом ( НМА) предусматривает поиск определенной последовательности конфигураций.
Такой поиск может существенно увеличить время работы автомата. Детерминированные автоматы не требуют поиска и работают быстрее,  поэтому именно такие автоматы применяются на практике. Детерминированные автоматы-распознаватели могут быть построены не для всех, а только для некоторых  видов КС-грамматик.

 

    Определение. Если язык L допускается детерминированным М-автоматом ,   то он называется детерминированным языком.

 
Учитывая значение детерминированных автоматов для практических применений,  посвятим им последующие разделы.


 

Пред.Страница 

След.Страница   Раздел   Содержание


 




- Начало -  - Назад -  - Вперед -