Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
(at, Sj)-+ Sk.
Число команд конечно; левая часть (аг-, Sj) называется ситуацией автомата, а правая часть (Sh) есть состояние, в котором автомат будет находиться на следующем шаге (после выполнения данной команды).
Если автомат оказывается в ситуации (ati, S/(), не являющейся левой частью какой-либо команды, то он останавливается. Если после проведения вычислений над цепочкой а автомат возвращается к ситуации (В, S0), говорят, что автомат допускает цепочку а. Множество цепочек, допускаемых данным автоматом, есть по определению язык, допускаемый этим автоматом. Класс языков, допускаемых описанным классом, совпадает с классом А-языков.
Пример. Вот множество команд конечного автомата, допускающего язык [ambn I m, п > 0}:
(a, S0)-+S1 (a, SІ)-+S1 (Ь, S1) -+S2 ОЬ, S2)-+S2 (В, S2)-+S0.
10.2.3. Различные варианты определения конечного автомата
В литературе встречаются различные варианты сформулированного определения. Основные из них связаны со следующими mq~ Дификациями. 164
Часть II. Некоторые замечательные классы языков
Пустой символ можно использовать в качестве маркера, а можно и вообще отказаться от него.
Вместо того чтобы в конце вычислений возвращаться в начальное состояние S0, автомат может принимать одно из выделенных заключительных состояний-, в частности, он может иметь единственное заключительное состояние.
Переходы автомата из одного состояния в другое могут описываться не командами описанного выше вида, а матрицей переходов:
aL
sS Sk
или же функцией переходов. (Ясно, впрочем, что это различие относится лишь к способу записи.)
Пример. Язык {ambn} может быть задан посредством следующей матрицы:
а b в
^0
<Г2 ^2 S0
Функцию переходов мы будем обозначать через М(а{, Sj). Она определена на подмножестве декартова произведения F X 5 и принимает значения из S для случая детерминированного автомата, который мы здесь рассматриваем; если же автомат недетерминированный, то значениями функции M являются подмножества S (см. ниже, п. 10.3.1).
Мы будем доопределять M на множестве V* X 5 следующим образом. Пусть фєРиф = фійі\ тогда
M (ф> Si) = ЛГ (а„ M (фх, Si)). Гл. X. Автоматные языки и конечные автоматы
165
10.2.4. Представление конечного автомата с помощью графа
Произвольному конечному автомату можно поставить в соответствие некоторый «размеченный» граф, действуя следующим образом. Каждому состоянию автомата сопоставляется вершина графа, каждой команде вида (a,, Sj) -> Sh сопоставляется дуга, ведущая из Sj в Sh и помеченная символом а{.
Пример. Автомату из предыдущих примеров отвечает следующий граф:
Аналогичным образом можно сопоставить граф А-грамматике: нетерминальным символам ставятся в соответствие вершины графа, каждому правилу вида Ai-*ujAh — дуга с пометкой aj, ведущая из Ai в Ah\ каждому правилу вида Ai-* a j отвечает дуга с пометкой uj, ведущая из Ai в особую вершину R, не отвечающую никакому нетерминальному символу. Так, для грамматики (0Прав) на стр. 160 мы получим следующий граф:
От графа, отвечающего конечному автомату, граф А-граммати-ки отличается тем, что в первом невозможно, чтобы две дуги, выходящие из одной и той же вершины А и помеченные одним и тем же символом а, входили в разные вершины В я С, тогда как для второго графа такого ограничения нет. Строго говоря, и автомату, и грамматике ставится в соответствие не граф, а мультиграф.
а
Ь
Ь 166
Часть II. Некоторые замечательные классы языков
§ 10.3. НЕКОТОРЫЕ ОБОБЩЕНИЯ И ВИДОИЗМЕНЕНИЯ КОНЕЧНЫХ АВТОМАТОВ
10.3.1. Недетерминированные конечные автоматы
Недетерминированный конечный автомат отличается от определенного выше детерминированного (ср. п. 10.2.3) тем, что значениями функции переходов являются не состояния, а множества состояний, или — в терминах команд — возможны различные команды с одинаковыми левыми частями.
В (мульти) графе, отвечающем недетерминированному конечному автомату, возможно, как и в графе А-грамматики, чтобы различные дуги соединяли одну и ту же пару вершин.
Сходство правил А-грамматик и команд недетерминированных конечных автоматов, а также сходство представляющих их графов настолько велико, что эквивалентность А-грамматик и недетерминированных конечных автоматов оказывается почти очевидной. Эта эквивалентность становится совсем очевидной, если принять следующее соглашение: все правила грамматики записываются в виде Ai-* ujAk, причем терминальные правила имеют вид Ai-^ajR, где R— особый символ, не принадлежащий вспомогательному словарю, А\ — аксиома.
Грамматике, все правила которой имеют указанный вид, сопоставляется автомат, у которого
— алфавит совпадает с W,
— состояния суть символы из Va U {R}',
— начальное состояние есть A1, заключительное состояние есть/?;
— команды имеют вид («j, Л,) —>-(для каждого правила грамматики Ai-^ajA/,).
Любая цепочка, порождаемая данной грамматикой, допускается построенным автоматом, и обратно. Совершенно аналогичным образом для любого недетерминированного конечного автомата можно построить эквивалентную ему А-грамматику.
