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