Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Хотя недетерминированный конечный автомат располагает на первый взгляд «большими возможностями», чем детерминированный, «допускающая сила» обоих типов автоматов оказывается одинаковой. Именно, для любого недетерминированного конечного автомата А с алфавитом V, множеством состояний S = (S0, ..., Sp) и функцией переходов M можно построить эквивалентный ему детерминированный конечный автомат А' следующим образом. Состояниями автомата А' будут всевозможные подмножества S; функция переходов M' автомата А' определяется соотношением
M (а, о)= (J M (a, S);
S ест
начальным состоянием А' будет подмножество S, состоящее из одного состояния — начального состояния автомата А, заключитель- Гл. X. Автоматные языки и конечные автоматы
167
ными — все подмножества S, содержащие хотя бы одно заключительное состояние А. Детерминированность автомата А' и его эквивалентность автомату А устанавливаются без труда.
10.3.2. Двусторонние автоматы
Еще одно естественное обобщение понятия конечного автомата можно получить, допустив перемещение ленты в обоих направлениях (до сих пор мы считали, что лента движется только в одном направлении). Тогда, обозревая символ в некоторой ячейке ленты, автомат сможет «возвращаться назад», обозревать другой символ, снова протягивать ленту вперед и т. д. вплоть до самого левого символа рабочей цепочки.
Формально перемещение ленты задается в двустороннем автомате функцией переходов; эта функция имеет такую же область определения, как у обычного конечного автомата, и принимает значения из произведения S X {Л,П}, где S — множество состояний, а JI и П обозначают сдвиг ленты на одну ячейку влево и вправо.
Можно доказать, что всякому двустороннему автомату можно поставить в соответствие эквивалентный «обычный», т. е. односторонний, автомат. Таким образом, и это обобщение не изменяет класса допускаемых языков (получаются по-прежнему А-языки).
10.3.3. k-определенные автоматы
Специальный класс конечных автоматов образуют автоматы, у которых текущее состояние зависит только от k последних прочитанных символов рабочей цепочки, причем k для каждого автомата фиксировано. Ответ на вопрос, принадлежит ли предъявленная цепочка языку, порождаемому данным автоматом, можно получить, рассматривая только k последних символов этой цепочки.
Вот пример автомата, не являющегося ^-определенным ни при каком kl): 168
Часть II. Некоторые замечательные классы языков
Понятие ft-определенного автомата использовалось для исследования естественных языков, в частности при изучении й-буквен-ных сочетаний в письменном тексте. Берется матрица, строки которой соответствуют всем последовательностям из k букв рассматриваемого языка, а столбцы — буквам этого языка. На пересечении строки і и столбца j записывается вероятность того, что буква встретится в тексте вслед за последовательностью букв рг-. Порождение слова ft-определенным автоматом, представленным посредством подобной матрицы, выполняется так. Находясь в состоянии, которое соответствует самой левой в слове последовательности из k букв: Cii1Cil2 ... aik, автомат выдает в зависимости от этих k букв букву uj и переходит в состояние, соответствующее последовательности ahah ... CilkCLl.
§ 10.4. СВОЙСТВА ЗАМКНУТОСТИ.
ПРЕДСТАВЛЕНИЕ А-ЯЗЫКОВ ПО КЛИНИ
Покажем, что А-языки образуют булеву алгебру.
10.4.1. Объединение
Объединение А-языков есть А-язык. Это утверждение доказывается так же, как аналогичное утверждение для КС-языков.
10.4.2. Дополнение
Рассмотрим (детерминированный) конечный автомат А, допускающий язык L. Построй^ по А автомат А' следующим образом (нам будет удобно говорить при этом не о самих автоматах, а о соответствующих графах). Все вершины и дуги графа автомата А войдут в граф А'. Кроме того, граф А' будет содержать еще одну вершину R, в которую будут вести следующие дуги: а) если из какой-либо вершины 5 исходного графа не выходит ни одной дуги, помеченной символом а, то из S в R идет дуга, помеченная этим символом; б) для каждого основного символа а из R в R идет дуга («петля»), помеченная этим символом. Начальная вершина нового графа будет совпадать с начальной вершиной старого; заключительными вершинами будут R и все незаключительные вершины старого графа Из детерминированности А сразу следует, что А' не допустит ни одной цепочки языка L. В то же время любая цепочка в основном словаре, не принадлежащая L, будет допущена автоматом А': если она является началом какой-либо цепочки из L, она будет «написана» на некотором пути, ведущем из начальной вершины в незаключительную вершину старого графа, в противном случае — на пути, ведущем из начальной вершины в R. Таким образом, А' допускает дополнение L. Гл. X. Автоматные языки и конечные автоматы
169
Итак, дополнение А-языка есть А-язык.
Из этого результата вместе с предыдущим вытекает, что и пересечение двух А-языков есть А-язык.
10.4.3. Произведение и итерация
Произведение А-языков есть А-язык. Для доказательства достаточно рассмотреть А-грамматики Gi и G2 с непересекающимися вспомогательными словарями и объединить множества их правил, заменив при этом каждое правило вида А ->а грамматики Gi правилом A-^aB0, где B0 — аксиома грамматики G2.
