ГРАММАТИКА ФОРМАЛЬНАЯ

В лингвистике: логическая система, или исчисление, задающая некоторое множество («правильных») цепочек (= конечных последовательностей), построенных из символов заданного конечного набора, называемого «алфавитом» или «основным (терминальным) словарем». Цепочки интерпретируются как языковые объекты различных уровней: слоги (= цепочки фон), словоформы (= цепочки морф), предложения (= цепочки словоформ) и т.п. Формальные грамматики, введенные в лингвистику Н. Хомским, представляют собой средство строгого описания естественных языков. Они входят в математическую лингвистику, в рамках которой подразделяются на грамматики порождающие и распознающие. Порождающая грамматика задает множество (правильных) цепочек перечислением последних с указаниями об их строении. Порождающая грамматика может построить любую правильную цепочку, охарактеризовав ее структуру. Она не должна строить ни одной неправильной цепочки. Наиболее известные порождающие грамматики – это грамматики Хомского. Распознающая грамматика задает множество (правильных) цепочек распознаванием последних: для любой предъявленной цепочки грамматика решает, является ли она правильной. В случае положительного ответа дает указания о ее строении. Наиболее известные разновидности распознающих грамматик – категориальные, или К-грамматики (К. Айдукевич, И. Бар-Хиллел).