ГРАММАТИКА ФОРМАЛЬНАЯ [Мапа поняття]

Четверка , в которой S - аксиома Г.Ф.; A - множество нетерминальных символов; B - множество терминальных символов; P - правила вывода. Объектами, с которыми работает Г.Ф., являются цепочки, состоящие из терминальных и нетерминальных символов. Правила вывода имеют вид, где и цепочки символов. При этом содержит хотя бы один нетерминальный символ. Функционирование Г.Ф. всегда начинается с цепочки, состоящей из единственного символа S. Применение правила к цепочке заключается в замене всех вхождений (или только самого левого вхождения) в на . Процесс заканчивается, когда ни одно из правил вывода к данной цепочке неприменимо. Такие заключительные цепочки входят в язык, порождаемый данной Г.Ф..