= Определения =
== Формальная грамматика ==
'''[[Формальные грамматики|Формальная грамматика]]''' - способ описания формального языка, то есть некоторого подмножества слов данного конечного алфавита. Выделяют ''порождающие'' грамматики, состоящие из следующих компонентов:
# Множество '''терминальных символов''' ('''терминалов''') - символов алфавита, слова над которым определяет грамматика, то есть символов, непосредственно присутствующих в словах языка.
# Множество '''нетерминальных символов''' ('''нетерминалов''') - объектов, выражающих некоторые структурные части языка, не имеющие конкретного представления как слова над алфавитом (таких, как формула или часть программы).
# Множество '''правил вывода''' ('''продукций''') - правил вида L → R, где:
## L - непустая последовательность терминальных и нетерминальных символов, содержищий по крайней мере один нетерминал.
## R - любая (возможно, пустая) последовательность терминальных и нетерминальных символов.
# S - стартовый нетерминал.
'''Выводом''' называется последовательность строк из терминалов и нетерминалов, такая, что:
* Первая строка состоит из стартового нетерминала
* Каждая следующая строка получена из предыдущей путем замена некоторой подстроки по некоторому правилу
* Последняя строка состоит только из терминалов (и, следовательно, не может быть преобразована по правилу грамматики).
Существование в грамматике вывода для получения конкретного слова - критерий принадлежности слова языку, определяемому грамматикой.
=== Пример ===
Терминалы: {a, b}. Нетерминалы: {S, A, B}. Продукции:
* S → AB
* A → AB
* AB → ba
* A → a
* B → b
Слова, выводимые в данной грамматике: ab, ba, abb, bab, abbb, babb, ...
Слова, невыводимые в данной грамматике: a, b, baa, baba, ...
== Контекстно-свободная грамматика ==
