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

Математический метод всегда следует двум основным принципам (по Колмогорову А.Н.):

1. Обобщение (абстрагирование). Математика изучает только специальные математические сущности, которые образуются из реальных объектов путем обобщения (учета одних свойств и отвлечения от остальных).

2. Строгость рассуждений - единственный критерий проверки результатов на истинность.

Чтобы изучать языки с помощью математических методов, необходимо сначала выделить из языка его свойства, которые представляются важными для изучения, а затем эти свойства строго определить.

Полученная таким образом абстракция обозначается термином "формальный язык" — математическая модель реального языка.

How to Read Mathematics  (перевод на русский: Как читать математику)

Примечание: reading protocol (протокол чтения) - reading model (модель чтения)

Формальный язык — математическая модель реального языка.

Содержание конкретной математической модели зависит от того, какие свойства важны для изучения, т.е. что планируется в данный момент выделить и изучать.

Реальный язык (для математика) - способ коммуникации (передачи информации).

Математическое определение понятия «язык» исходит из того, что «язык» это только средство передачи информации. В формальных языках изучается с использованием математических методов только т.н. коммуникативная функция языка. Другие функции языка (когнитивная, аксиологическая, творческая) здесь не изучаются и не рассматриваются.

Для информационного обмена используется конечный набор знаков (символов) - алфавит.

Символы алфавита образуют линейные последовательности (выписываются или проговариваются в строгом временном порядке).

Последовательности символов называют цепочками (словами или предложениями).

Таким образом, здесь рассматривается только т.н. коммуникативная функция языка, которая изучается с использованием математических методов. Другие функции языка здесь не изучаются и, потому, не рассматриваются.

В теории формальных языков представляется важным изучить синтаксические свойства текстов (законы расположения слов рядом друг с другом).

Поэтому формальный язык задается как множество последовательностей, составленных из элементов конечного алфавита.

Определим это более строго:

Алфавит - непустое конечное множество элементов.

В настоящее время, в исследовательских целях, рассматриваются и бесконечные алфавиты

Для обозначения алфавита будем использовать латинское T (

Символы - элементы алфавита.

Для обозначения символов алфавита — будем использовать начальные строчные буквы латинского алфавита.

Например, выражение T = {a,b} обозначает алфавит из двух символов a и b.

Формальные языки — это просто множества цепочек, составленных из символов некоторого алфавита (как правило, конечного).

Общий вид формальной модели языка:  L = {G | пояснение к G}, где

• L - язык (некоторое подмножество множества над некоторым множеством (алфавита),
  формально определенное над ним (с помощью грамматики - системы правил)

• G - задающая язык формальная грамматика (формализованная система правил, на основе которых из некоторого множества (алфавита) выделяется некоторое подмножество (собственно язык, определенный над данным алфавитом)

Пример формальной модели языка (с конечным числом слов):

L = {a^n | n - 2, 3, 4} - это формальная модель языка, который:

• состоит всего из 3 слов: aa, аaa, ааaa

• определен над одноэлементным алфавитом а

• с помощью грамматики G=a^n, где n - 2, 3, 4

• слова образуются возведением символа алфавита в степень, задаваемую нетерминальным символом n (который может принимать три разных значения: 2, 3, 4)

Грамматика - любой способ конечного задания языка (выделения некоторого подмножества из множества всех слов некоторого конечного алфавита)

Например, в качестве грамматики может быть последовательное перечисление всех цепочек (пригодно только для конечных языков, очень неэффективно).

Для бесконечных языков нужны формальные грамматики.

Формальная грамматика - математическая модель конечная задания языка (конечного или бесконечного)

Конечное задание может описать бесконечные совокупности только в том случае, если строение всех цепочек языка основано на конечном числе единых принципов.

Пример:

Пусть  каждая цепочка языка начинается с символов a, за которыми идет столько же символов b.

Грамматика G = {a^nb^n} (здесь n — натуральное число) задает язык L, состоящий из цепочек вида ab, aabb, aaabbb и т.д.
Язык L представляет собой бесконечное множество цепочек, а его грамматика G конечна (состоит из 10 символов).

Если язык представляет собой бесконечную совокупность случайным образом набранных цепочек, строение которых не подчиняется единым принципам, то для такого языка нельзя придумать грамматику.

Вопрос - можно ли считать такую совокупность языком?

В целях математической строгости и единообразия подхода обычно такие совокупности языком считают.

Формальная грамматика задает язык описывая законы внутреннего строения его цепочек (синтаксис).

Формальная грамматика - конечное математическое описание синтаксиса языка.

Для практики интересны не просто грамматики, но грамматики, которые могут быть заданы на основе единого метаязыка (описаны в рамках единой метамодели (подхода, формализма парадигмы)).

Для таких грамматик можно созадать алгоритм для компьютера, который будет брать на вход описание грамматики, сделанное на этом метаязыке, и обрабатывать (автоматически) цепочки языка.

Такие метаязыки (метамодели, парадигмы описания грамматик) называют синтаксическими теориями.

Формальная грамматика — это математическая модель грамматики, описанная в рамках конкретного метаязыка (синтаксической теории).

Самый известный метаязык для задания грамматик — порождающие грамматики Хомского.

Другой популярный формализм — окрестностные грамматики.

Основные модели (виды) грамматик:

• Порождающие грамматики. Этот вид систем (моделей) используется для порождения (генерации) цепочек языков по требованию.

• Распознающие грамматики. Такие грамматики представляют собой системы (модели, устройства, алгоритмы), которым на вход подается цепочка языка, а на выходе система выдает:

  • «Да», если цепочка принадлежит языку,

  • «Нет» — в противном случае.

• Перечисляющие грамматики выдают одну за другой все цепочки языка. Если язык состоит из бесконечного числа цепочек, то процесс перечисления можно остановить принудительно в нужный момент времени, например, когда будет напечатана нужная цепочка.

Формальная модель формальной грамматики G, это четверка:

G = {T, N, S, P), где:

• T - множество (алфавит) терминальных символов (terminals);

• N - множество (алфавит) нетерминальных символов  (nonterminals);

• S  - начальный символ (start symbol) грамматики из N (множества нетерминальных символов);

• P - множество правил (production rules или productions) вида: «левая часть» Ú «правая часть»,
  где: «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал, а  «правая часть» — любая последовательность терминалов и нетерминалов.

Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут стандартные символы ASCII — латинские буквы, цифры и спец. символы.

Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.

Вывод  —  последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путём замены некоторой подстроки по одному (любому) из правил. Конечной строкой является строка, полностью состоящая из терминалов, и следовательно являющаяся словом языка.

Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.

Чтобы задать грамматику, требуется задать алфавиты терминалов и нетерминалов, набор правил вывода, а также выделить в множестве нетерминалов начальный.

Подробнее: И.А. Волкова, А.А. Вылиток, Т.В. Руденко Формальные грамматики и языки

По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):

• тип 0. неограниченные грамматики — возможны любые правила

• тип 1. контекстно-зависимые грамматики — левая часть может содержать один нетерминал, окруженный «контекстом» (последовательности символов, в том же виде присутствующие в правой части); сам нетерминал заменяется непустой последовательностью символов в правой части.

• тип 2. контекстно-свободные грамматики (сontext-free grammar) — грамматики, у которых в левых частях всех правил стоят только одиночные нетерминалы. Контекстно-свободные грамматики задают контекстно-свободные языки (context-free language).

• тип 3. регулярные грамматики — более простые, эквивалентны конечным автоматам.

Для компьютерного моделирования и автоматической обработки естественных языков наибольшее практическое значение (до сих пор!) имеют тип3 и тип4:

• Контекстно-свободные грамматики широко применяются в грамматическом анализе.

• Регулярные грамматики (в виде регулярных выражений) широко применяются в лексическом анализе и текстовом поиске (как поисковые шаблоны).

Замыкание (алгебра) — минимально возможное расширение заданного множества относительно заданного набора алгебраических операций, в котором любое применение этих операций к элементам такого расширения не выходит за его пределы.

Алгебраически замкнутое множество  — множество, совпадающее со своим замыканием.

Примеры:

• Алгебраическим замыканием поля вещественных чисел является поле комплексных чисел.

• Алгебраическим замыканием поля рациональных чисел является поле алгебраических чисел.

• Поле арифметических чисел алгебраически замкнуто.

Свойство замкнутости позволяет создать распознаватель языка.

Семантически замкнутые языки  — языки, в которых семантические понятия (например, предикат истинности), применимы к самим выражениям этого языка.

JFLAP (Java Formal Languages and Automata Package) — свободная кроссплатформенная программа моделирования исследования формальных языков и грамматик.

Преобразования грамматик:

• Порождающие грамматики могут быть преобразованы в перчисляющие (достаточно генерировать цепочки, упорядочив их, по длине и порядку символов)

• Перечисляющие грамматики в распознающие в общем случае нельзя преобразовать.

Можно использовать следующий метод. Получив на вход цепочку, запустить процесс перечисления цепочек и ждать, напечатает ли перечисляющая грамматика эту цепочку или нет. Если такая цепочка напечатана, то заканчиваем процесс перечисления и печатаем «Да». Если цепочка принадлежит языку, то она обязательно будет напечатана и, таким образом, распознана. Но, если цепочка не принадлежит языку, то процесс распознавания будет продолжаться бесконечно. Программа распознающей грамматики зациклится.

В этом смысле мощность распознающих грамматик меньше мощности порождающих и перечисляющих.

Это важно при сравнении порождающих грамматик Хомского и распознающих машин Тьюринга.