54
правки
Изменения
Нет описания правки
== Формальная грамматика ==
'''[[Формальные грамматики|Формальная грамматика]]''' - способ описания формального языка, то есть некоторого подмножества слов данного конечного алфавита. Выделяют ''порождающие'' грамматики, состоящие из следующих компонентов:
# Множество '''терминальных символов''' ('''терминалов''') - символов алфавита, слова над которым определяет грамматика, то есть символов, непосредственно присутствующих в словах языка.
== Контекстно-свободная грамматика ==
'''[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|Контекстно-свободная грамматика]]''' ('''КС-грамматика''', '''бесконтекстная грамматика''') — частный случай формальной грамматики, у которой левые части всех правил являются одиночными нетерминалами, то есть все её продукции имеют вид L → R, где L - нетерминал, а R - последовательность терминалов и нетерминалов.
=== Пример ===
== Нормальная форма Хомского ==
'''[[Нормальная форма Хомского]]''' - нормальная форма КС-грамматик, в которой все продукции имеют вид:
* A → a, где ''A'' - нетерминал, а ''a'' - терминал
* A → BC, где ''A'', ''B'', ''C'' - нетерминалы, причем ''B'' и ''C'' не являются начальными нетерминалами
