11. Порождающие грамматики Хомского

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

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

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

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

Итак, грамматика определяется следующими характеристиками:

• Е — набор (алфавит) терминальных символов

• N — набор (алфавит) нетерминальных символов

• P — набор правил вида: «левая часть» -> «правая часть», где:

- «левая часть» — непустая последовательность терминалов и нетерминалов, содержащая хотя бы один нетерминал

- «правая часть» — любая последовательность терминалов и нетерминалов

• S — стартовый (начальный) символ из набора нетерминалов.

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

По иерархии Хомского, грамматики делятся на 4 типа:

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

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

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

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

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

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

11. Автоматная грамматика

Автоматная грамматика , где А – основной алфавит; Р – правила вида – аксиома. Конечный автомат , где А – основной алфавит; S – алфавит состояний; s₀ – начальное состояние; s_k – конечное состояние; Р – правила вида

Пример 3. Для языка L₁ заданы:

а) б)

множество состояний автомата

V =

 – маркер конца слова

АГ – правила порождения КА – правила перехода

1. 1.

2. 2.

3. 3.

4. 4.

АГ порождает слова языка L₁ КА распознаёт слова языка L₁.

Если заданы правила АГ, то правила КА получаются формальными переносами символов A из правой части правил в левую (см. пример). Если заданы правила КА, то правила АГ переносом символов A в правую часть правил.

КА задается графом переходов и по сути является машиной состояний (SM).

12. Конечный автомат

Конечный автомат – это простейший распознаватель без вспомогательной памяти. Детерминированным конечным автоматом (ДКА) называется пятерка объектов:

, (2.1)

где - конечное множество состояний автомата;

T- конечное множество допустимых входных символов;

F - функция переходов, отображающая множество QT во множество состояний Q;

H - конечное множество начальных состояний автомата;

Z - множество заключительных состояний автомата, Z  Q.

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

Существуют следующие три способа представления функции переходов.

Командный способ. Каждую команду КА записывают в форме , где .

Табличный способ. Строки таблицы переходов соответствуют входным символам автомата t  T, а столбцы – состояниям Q. Ячейки таблицы заполняются новыми состояниями, соответствующими значению функции . Неопределенным значениям функции переходов соответствуют пустые ячейки таблицы.

Графический способ. Строится диаграмма состояний автомата – неупорядоченный ориентированный помеченный граф. Вершины графа помечены именами состояний автомата. Дуга ведет из состояния в состояниe и помечается списком всех символов t  T, для которых . Вершина, соответствующая входному состоянию автомата, снабжается стрелкой. Заключительное состояние на графе обозначается двумя концентрическими окружностями.