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

— система правил, описывающая множество конечных последовательностей символов. Конечные последовательности (цепочки), входящие в указанное множество, наз. предложениями, а само множество — языком, описываемым данной Г. ф. Различают два типа Г. ф.: грамматики порождающие — системы правил, позволяющие строить предложения языка, и грамматики распознающие — алгоритмы, распознающие по любой цепочке, является ли она предложением. Это деление в значительной степени условно, т. к. любая распознающая грамматика по существу задает способ построения всех предложений. Кроме того, для наиболее существенных классов порождающих грамматик (в частности, для грамматик составляющих, бесконтекстных и автоматных) существуют алгоритмы, позволяющие по любой цепочке символов определить, является ли она предложением. Различают, кроме того, такие классы Г. ф. (напр., грамматики категориальные), которые в одинаковой мере можно рассматривать как порождающие и как распознающие. Г. ф. применяют чаще всего для описания естественных и искусственных языков в лингвистике математической. Теперь порождающие грамматики применяют больше, чем распознающие.