Автоматные языки и грамматики.
Сложность работы с языками, как объектами бесконечного множества, заключается в трудности их задания. Механизмы задания языков имеют особую важность не только в теории естественных языков, но и в теории формальных языков.
Способы задания языков являются основным разделом математической лингвистики, которая разрабатывает теорию языков и грамматик. Математическая лингвистика разрабатывалась как наука о строении естественных языков. Большой вклад в развитие математической лингвистики внес Н. Хомский. Подход Хомского оказался примененим и к алгоритмическим языкам, которые проще устроены и легче поддаются формаливации.
По характеру используемого математического аппарата теория формальных языкови грамматик близка к математической логике, теории лгоритмов и теории автоматов.
При изучении языков выделяют три состовляющие: синтаксис, семантику и прагматику языка.
Под синтаксисом языка понимается набор правил построения и анализа цепочек (слов). Другими словами, синтаксис языка изучает методы порождения и распознования цепочек в данном алфавите.
Семантика языка ставит в соответствие цепочам (словам) язык некоторый «смысл» или «значение». Таким образом, семантика есть свод правил интерпретации предложений языка, т.е. правила сопоставления предложениям некоторого значения из множества допустимых значений.
Прагматика языка определяется тем, какие цели ставит перед собой носитель языка. Например, цель лектора – донести некоторые знания до слушателей. Этот раздел носит социально-филосовский характер, и мы его касаться не будем.
Определение. Под грамматикой G понимается любой конечный механизм задания языка.
Таким образом, грамматика языка есть конечное множество правил, определяющих этот язык. Формальные языки, по мере развития теории вычислительных систем, все больше приближаются к формально построенным математическим конструкциям, и в этом смысле грамматика есть теория повторяющихся закономерностей построения предложений, называемую синтаксической структурой языка.
Форматизация языков и грамматик сформулировала два основных требования к грамматикам. Первое требование заключается в том, чтобы грамматика преписывала каждому предположению языка его структурное описание. Например, используемые символы для записи математической формулы, их правописание, правила и порядок расстановки скобок и т.п. Второе правило заключается в том, что число правил, описывающих язык и грамматику, должно быть конечным.
Две грамматики G1 и G2 называются слабо эквивалентными, если они если они пораждают один и тот же язык L G1 LG2 . Другими словами слабо эквивалентные грамматики формируют (порождают) множество совпадающих цепочек.
Две грамматики называются сильно эквивалентными, если они порождают не только одни и те же цепочки, но и присваивают им одинаковые описания их структур. В этом смысле можно говорить, что грамматика языка это конечное множество правил, задающее язык как синтаксическую структуру.
В формальных грамматиках все утверждения формулируются в виде простого набора правил, операций и элементарных символов, что делает эти грамматики достаточно простыми с точки зрения изучения их свойств.
Различают три типа формальных грамматик: порождающие, распознающие и преобразующие.
Определение. Формальная грамматика называется порождающей, если она может построить правильную цепочку, указывая при этом правила ее построения, и не строит ни одной не правильной цепочки. (рис. 1, а.)
Определение. Формальная грамматика называется распознающей, если для любой рассматриваемой цепочки она указывает, является ли эта цепочка правильной или нет, и, в случае положительного ответа дать указание о строении этой цепочки. (рис. 1, б.)
Определение. Формальная грамматика называется преобразующей, если для любой правильно построенной цепочки она может построить ее отображение в виде другой правильно построенной цепочки, задавая при этом правила построения этого отображения. (рис.1, в.)
| Порождающая грамматика | Правильная цепочка |
| из языка L |
А)
| Цепочка из V* | Распознающая грамматика | «Да, цепочка | |
| принадлежит L» «Нет, цепочка | |||
| не принадлежит L» |
Б)
| Цепочка из V* | Преобразующая грамматика | Цепочка из V** |
В)
Рис. 5.1. Типы грамматик.
Исходя из этих трех определений, конечный автомат можно рассматривать как устройство, способное некоторым образом обрабатывать конечные последовательности цепочек, т.е. выполнять алгоритмические операции над языками.
Например, автомат может распознавать исходный текст программы и разбивать его на такие логические единицы, как идентификаторы, ключевые слова, знаки пунктуации.
Операция распознавания позволяет выделить среди всех цепочек те, которые принадлежат входному языку и преобразовать эти цепочки в программу на некотором языке. Такая, широко распространенная операция, называется трансляцией.
В теории формальных языков большое внимание уделяется порождающим грамматикам или грамматикам Холмского. Это объясняется тем, что роль распознающей грамматики может выполнять конечный автомат, реализующий алгоритм разделения входных цепочек на два класса – принадлежащие и не принадлежащие языку L. Задача распознавания принадлежности цепочек к некоторому языку облегчается тем, что в формальных грамматиках все утверждения формулируются в терминах небольшого числа определенных операций и символов. Конечные автоматы, распознающие принадлежность языка грамматике могут быть реализованы как схемным, так и программным путем.
Конечные автоматы, выполняющие роль распознающих грамматик, называются конечным автоматом-распознавателем.