Неукорачивающие грамматики

Определение 15.1.1.

Порождающая грамматика

называется неукорачивающей (noncontracting), если для каждого правила

выполняется неравенство .

Теорема 15.1.2.

Существует алгоритм, позволяющий по произвольной неукорачивающей грамматике G и по слову w узнать, верно ли, что .

Теорема 15.1.3.

Каждая контекстная грамматика является неукорачивающей. Каждая неукорачивающая грамматика эквивалентна некоторой контекстной грамматике.

Пример 15.1.4.

Грамматика

эквивалентна контекстной грамматике из примера 1.5.4.

Упражнение 15.1.5.

Найти неукорачивающую грамматику, порождающую язык .

Упражнение 15.1.6.

Найти неукорачивающую грамматику, порождающую язык .

Упражнение 15.1.7.

Найти неукорачивающую грамматику, порождающую язык .

Упражнение 15.1.7.

Найти неукорачивающую грамматику, порождающую язык .