Класс языков, порождаемых грамматиками типа
Теорема 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?
Содержание раздела