Контекстно-свободные языки и грамматики

АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ

Кафедра ТК

Тема: Контекстно-свободные языки и грамматики

β∈V+, V=VT∪VN (неукорачивающие КС-грамматики),
Контекстно-свободные (КС) языки определяются грамматиками типа

А→β, где А∈VN , β∈V*, V=VT∪VN (укорачивающие КС-грамматики).

Приведенные грамматики – это КС-грамматики, которые не содержат недостижимых и бесплодных символов, циклов и λ-правил («пустых» правил).

Для преобразования произвольной КС-грамматики к приведенному виду, необходимо удалить:

все бесплодные символы;

все недостижимые символы;

λ-правила;

цепные правила.

Шаги преобразования должны
выполняться именно в указанном порядке,
и никак иначе.

P, S) символ A∈VN называется бесплодным, если для него выполняется:

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

Символ x∈(VT∪VN) называется недостижимым, если он не встречается ни в одной сентенциальной форме грамматики G(VT, VN, P, S).

Правилами с пустой цепочкой или λ-правилами называются все правила грамматики вида А→λ, где A∈VN.

Циклом (циклическим выводом) в грамматике G(VT, VN, P, S) называется вывод вида А⇒*А, A∈VN.

такой вывод абсолютно бесполезен,
вследствие этого в распознавателях КС-языков
целесообразно избегать возможности появления циклов

Циклы возможны только в том случае, если в КС-грамматике присутствуют цепные правила вида А→В, A, B∈VN.