Изменения

'''Задача о выводе в контекстно-свободной грамматике''' - задача о том, выводимо ли данное слово в данной контекстно-свободной грамматике. '''Алгоритм Кока-Янгера-Касами''' - алгоритм, решающий данную задачу. = Определения = == Формальная грамматика ==

* 1) # Множество '''терминальных символов''' ('''терминалов''') - символов алфавита, слова над которым определяет грамматика, то есть символов, непосредственно присутствующих в словах языка.* 2) # Множество '''нетерминальных символов''' ('''нетерминалов''') - объектов, выражающих некоторые структурные части языка, не имеющие конкретного представления как слова над алфавитом (таких, как формула или часть программы).* 3) # Множество '''правил вывода''' ('''продукций''') - правил вида L → R, где:** ## L - непустая последовательность терминальных и нетерминальных символов, содержищий по крайней мере один нетерминал.** ## R - любая (возможно, пустая) последовательность терминальных и нетерминальных символов.* 4) # S - стартовый нетерминал.

Терминалы: {a, b}. Нетерминалы: {S, A, B}. Продукции:

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

Терминалы: {(, )}. Нетерминалы: {S}. Продукции:

== Нормальная форма Хомского ==

ПокажемМожно показать, что любую КС-грамматику можно привести к нормальной форме Хомского. Рассмотрим продукцию этой грамматики: <tex>A \Rightarrow A_1 A_2 A_3 ... A_n</tex>, где <tex>A_i</tex> - терминалы или нетерминалы. Добавим к грамматике нетерминалы <tex>B_1 ... B_n</tex>, <tex>C_k</tex> для таких k, что <tex>A_k</tex> - нетерминал, и продукции вида* <tex>A \Rightarrow B_1</tex>* <tex>B_i \Rightarrow A_i B_{i+1}</tex> если <tex>A_i</tex> - нетерминал* <tex>B_i \Rightarrow C_i B_{i+1}</tex> и <tex>C_i \Rightarrow A_i</tex>, если <tex>A_i</tex> - терминал Очевидно, что добавленные элементы в совокупности дают рассмотренную продукцию. Проделав данную процедуру ко всем продукциям, мы и получим нормальную форму Хомского для данной грамматики.