|
31 G={V„,VT,P,S), у где N конечное непустое множество нетерминальных символов (нетерминалов); конечное непустое множество (алфавит) терминальных символов (терминалов), причем п ~0 ; Р конечное множество упорядоченных пар (правила подстановки, продукции); 5 начальный нетерминал (аксиома), е Vn . Эталонная формальная грамматика в компактной продукционной форме описывает возможные цепочки элементов (терминалов), составляющих заданный класс объектов (в нашем случае-СиПО), при этом правила подстановки определяют компактную конструктивную схему формирования этих цепочек. Таким образом, формальная грамматика служит средством компактного задания и генерации большого числа структур объектов с использованием конечных наборов исходных элементов и правил подстановки. Принятие решений с использованием процедур синтаксического анализа имеет целью установить, является ли входная цепочка элементов (элементов СпИО) синтаксически правильной по отношению к заданной грамматике G‘, описывающей 1 подкласс объектов. Проведенный анализ показал, что основное внимание при изложении теории формальных грамматик уделяется алгоритмическому аспекту. Функциональный аспект затрагивается в известных работах лишь в той мере, которая необходима для пояснения принципиальных вопросов, связанных с разрешимостью множеств, порождаемых языками различных типов, и вопросов, связанных с построением синтаксических анализаторов, |
45 Эталонная формальная грамматика в компактной продукционной форме описывает возможные цепочки элементов (терминалов), составляющих заданный класс образов, при этом правила подстановки определяют компактную конструктивную схему формирования этих цепочек. Таким образом, формальная грамматика служит средством компактного задания большого числа образов распознаваемых и обрабатываемых классов с использованием конечных наборов исходных элементов и правил подстановки. Распознавание с использованием процедур синтаксического анализа имеет целью установить, является ли входная цепочка элементов (цифровых сигналов) синтаксически правильной по отношению к заданной грамматике G,, описывающей / подкласс сигналов ЦФС. Проведенный анализ показал, что основное внимание при изложении теории формальных грамматик уделяется алгоритмическому аспекту. Функциональный аспект затрагивается в известных работах лишь в той мере, которая необходима для пояснения принципиальных вопросов, связанных с разрешимостью множеств, порождаемых языками различных типов, и вопросов, связанных с построением синтаксических анализаторов, алгоритмов синтаксического разбора, используемых в качестве процедурной компоненты методов распознавания образов. В ранних работах по теории формальных грамматик и языков изучался в основном синтаксис языка (грамматика), т.е. правила построения конструкций языка. В общем случае грамматика языка формализует конечное множество правил, которые рекурсивно задают язык как некоторую синтаксическую структуру, что отвечает необходимому этапу изучения языка представления распознаваемых и обрабатываемых образов и объектов естественного и искусственного происхождения. В современных работах все большее внимание уделяется процедурным и семантическим аспектам представления и обработки информации с использованием в первую очередь атрибутных грамматик, |