Синтез цифровых автоматов. Захаров Н.Г - 18 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

17
Поскольку практическая реализация структурных методов распознавания обра-
зов основана на использовании некоторых идей и методов математической лингвис-
тики, рассмотрим ее основные понятия.
Термин формальная грамматика представляет собой общее название несколь-
ких типов исчислений, используемых в математической лингвистике для описания
строения естественных языков, а также некоторых искусственных языков, в частно-
сти, языков программирования.
Под грамматиками в математической лингвистике понимают некоторые специ-
альные системы правил, задающие (или характеризующие) множества цепочек (ко-
нечных последовательностей) символов. Эти объекты могут интерпретироваться как
языковые объекты различных уровней, например, как словоформы, словосочетания и
предложения (цепочки словоформ) и т. п.
Следовательно, формальные грамматики имеют дело с абстракциями, возни-
кающими в результате обобщения таких стандартных лингвистических понятий как
словоформа, словосочетание и предложение. Из определенного набора символов
(обозначающих, например, все словоформы русского языка) можно строить произ-
вольные цепочки; одни из них естественно считать правильными или допустимыми, а
другие – неправильными или недоступными.
Формальные грамматики задают правильные цепочки, если для любой предъ-
явленной цепочки грамматика позволяет установить, является или нет эта цепочка
правильной, и в случае положительного ответа дается указание о строении этой це-
почки, либо грамматика позволяет построить любую правильную цепочку, давая при
этом указания о ее строении, и не строит ни одной неправильной цепочки. В первом
случае формальная грамматика называется распознающей, во втором – порождающей.
Формальные грамматики обладают двумя существенными особенностями. Во-
первых, существующие формальные грамматики описывают только совокупность
возможных результатов, не давая прямых указаний, как именно можно получить ре-
зультат, соответствующий определенной исходной задаче. Во-вторых, в формальных
грамматиках все утверждения формируются исключительно в терминах небольшого
числа четко определенных и весьма элементарных символов и операций. Это делает
формальные грамматики очень простыми с точки зрения их логического строения и
обеспечивает изучение их свойств дедуктивными методами.
Структурные методы распознавания базируются на порождающей граммати-
ке – системе, состоящей из четырех частей: основной, или терминальный словарь;
вспомогательный словарь; начальный символ; набор правил подстановки исходных
элементов, из которых строят цепочки, порождаемые грамматикой. Элементы основ-
ного словаря называют основными (терминальными) символами.
Вспомогательный (нетерминальный) словарь. Это набор символов, которы-
ми обозначаются классы исходных элементов или цепочек исходных элементов, а
также в отдельных случаях некоторые специальные элементы (вспомогательные или
нетерминальные).
Начальный символ. Это выделенный нетерминальный символ, обозначающий
совокупность (класс) всех тех языковых объектов, для описания которых предназна-
чается данная грамматика. Так в грамматике, порождающей предложения, начальным
будет символ, означающий предложение; в грамматике, порождающей допустимые
слоги, начальный символ означает слог, и т. п.

Страницы