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

         

Проблема выводимости слова


Теорема 15.3.1.

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

Теорема 15.3.2.

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

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

Принадлежит ли слово aaaaabbbabb языку, порождаемому грамматикой

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

Принадлежит ли слово abababa языку, порождаемому грамматикой



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