Математическая теория формальных языков

         

Класс языков, порождаемых грамматиками типа


Теорема 14.4.1.

Класс языков, порождаемых грамматиками типа 0, совпадает с классом перечислимых языков.

Доказательство можно найти, например, в [СерГал с. 24-26].

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

Выводимо ли слово aab в грамматике

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

Выводимо ли слово aaaaaaaab в грамматике

Замечание 14.4.4.

Неизвестно, порождает ли грамматика

все слова в алфавите {a,b}.

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

Пусть . Рассмотрим грамматику

Выводимо ли в ней слово ccdcdcddccddcdcccabba?

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

Является ли разрешимым язык, порождаемый грамматикой

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

Порождающая грамматика в нормальной форме - это порождающая грамматика, в которой каждое правило имеет вид ,

или , где , , , .

Теорема 14.4.8.

Каждая порождающая грамматика эквивалентна некоторой порождающей грамматике в~нормальной форме.

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

Существует ли такая порождающая грамматика G, что язык

не порождается ни одной грамматикой типа 0?


Содержание раздела