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


Резюме


Контекстно-свободные языки являются более сильным выразительным средством, чем автоматные языки, которые являются подмножеством КС-языков. КС-грамматики, предназначенные для  практических применений, не должны содержать бесполезных символов. Такие грамматики  называются приведенными. КС-грамматики допускают преобразования, результатом которых может быть исключение цепных, аннулирующих или леворекурсивных правил. Задачу распознавания для КС-языков решают магазинные преобразователи. В общем случае для любой КС-грамматики можно построить магазинный распознаватель, допускающий язык, который порождается заданной грамматикой. Однако, такой распознаватель может оказаться недетерминированным. Работа недетерминированного распознавателя связана с поиском последовательности конфигураций, показывающей допустимость входной цепочки. Поиск увеличивает время работы автомата, поэтому для практических применений предпочитают использовать  детерминированные  автоматы.

  •  

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

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


  •  




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