Детерминированные конечные автоматы. Эквивалентные состояния и автоматы

Детерминированный конечный автомат — набор из пяти элементов: где Sigma — алфавит, Q — множество состояний, s — начальное (стартовое) состояние, T — множество допускающих состояний, delta — функция переходов.

Детерминированный конечный автомат является специальным случаем недетерминированного конечного автомата, в котором

• отсутствуют состояния, имеющие e-переходы;

• для каждого состояния s и входного символа а существует не более одной дуги, исходящей из s и помеченной как а.

Детерминированный конечный автомат имеет для любого входного символа не более одного перехода из каждого состояния. Если для представления функции переходов ДКА используется таблица, то каждая запись в ней представляет собой единственное состояние. Следовательно, очень просто проверить, допускает ли данный ДКА некоторую строку, поскольку имеется не более одного пути от стартового состояния, помеченного этой строкой. Следующий алгоритм имитирует поведение ДКА при обработке входной строки.

Состояния q автомата М и q' автомата М' считаются эквивалентными, если оба автомата, получив одну и ту же (любую) входную последовательность символов, перерабатывают ее в одинаковую выходную последовательность.

Автоматы М и М' называются эквивалентными, если для каждого состояния автомата М существует эквивалентное ему состояние автомата М' и наоборот.

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

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

Автоматы с магазинной памятью. Язык, допускаемый магазинным автоматом. Построение автомата с магазинной памятью. Функции перехода. Способы задания функций перехода автомата с магазинной памятью.

КС-грамматика определяет структуру цепочек и позволяет строить цепочки определенного языка. Магазинные автоматы, подобно рассмотренным ранее конечным автоматам, позволяют решать для контекстно-свободных языков задачу распознавания, которая заключается в том, что по заданной цепочке необходимо определить принадлежит ли она заданному языку.
В работах, связанных с формальными языками и грамматиками,используется модель м агазинного автомата, состоящая из входной ленты, устройства управления и вспомогательной ленты, называемой магазином или стеком.
Входная лента разделяется на клетки (позиции), в каждой из которых может быть
записан символ входного алфавита. При этом предполагается, что в неиспользуемых клетках входной ленты расположены пустые символы e.
Вспомогательная лента также разделена на клетки, в которых могут располагаться символы магазинного алфавита. Начало вспомогательной ленты называется дном магазина. Связь устройства управления с лентами осуществляется двумя головками, которые могут перемещаться вдоль лент.

Головка входной ленты может перемещаться только в одну сторону - вправо или
оставаться на месте. Она может выполнять только чтение. Головка вспомогательной ленты способна выполнять как чтение, так и запись, но эти операции связаны с перемещением головки определенным образом:
- при записи головка предварительно сдвигается на одну позицию вверх, а затем символ заносится на ленту,
- при чтении символ, находящийся под головкой считывается с ленты, а затем головка сдвигается на одну позицию вниз,т.о.головка всегда установлена против последнего записанного символа. Позицию, находящуюся в рассматриваемый момент времени под головкой, называют вершиной магазина.

Определение. Магазинный автомат Мопределяется следующей совокупностью семи объектов: M={P, S, sо, f, F, H, hо },

где
P - входной алфавит,
S - алфавит состояний,
s_о - начальное состояние,
s_о О S,
F - множество конечных состояний,F является подмножеством S,
H - алфавит магазинных символов, записываемых на вспомогательную ленту,
h_о - маркер дна, он всегда записывается на дно магазина, h_о О H,
f - функция переходов
f: {P И { e }} x S x H ® S x H*,
если М-автомат - детерминированный, и
f:{P И { e }} x S x H ® M(S x H*),
если М-автомат - недетерминированный.

Функция f отображает тройки (p_i , s_j , h_k ) в пары (s_r , u), где u О H* и h_k - символ в вершине магазина, для детерминированного автомата или в множество пар для недетерминированного автомата.
Эта функция описывает изменение состояния магазинного автомата, происходящее при чтении символа с входной ленты и премещении входной головки.
В дальнейшем при построении магазинных автоматов потребуются две разновидности функций переходов, изменяющих состояние автомата без перемещения входной головки: 1) функция переходов с пустым символом в качестве входного символа:

f⁰(s, e, h) = (s', b),

которая, независимо от того какой символ находится под читаюшей гловкой входной ленты, предписывает прочитать символ h из вершины магазина, изменить состояние автомата на s' и записать цепочку b в магазин.
2)функция переходов с определенным входным символом:

f*(s, a, h) = (s', b),

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

Цепочка a называется допустимойдля автомата М, если существует последовательность конфигураций, в которой первая конфигурация является начальной c цепочкой a, а последняя - заключительной. (sо, a, hо) |--* (s1, $, $), где s1 О F.

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

L(М)= {a ¦ (s_о, a, h_о) ¦--* (s', $, $) & s' О F }

ЕслиГ = { Vт, Va, I, R }является КС-грамматикой, то по ней можно построить такой магазинный автомат М, что L(M) = L(Г).

В основе доказательства лежит способ построения магазинного автомата по заданной КС-грамматике.Чтобы сделать процесс построения автомата более простым и наглядным, условимся использовать магазинные автоматы с одним состоянием s₀. Итак, пусть задана грамматика Г = { Vт, Va, I, R }. Определим компоненты автомата М следующим образом:

S = { s₀ }, P = V_т, H = V_тИ V_aИ { h₀}, F = { s₀ },

в качестве начального состояния автомата примем s₀ и построим функцию переходов так:
1. Для всех A О V_A, таких что встречаются в левой части правил
<A> ® a, построим команды вида:

f⁰(s ₀, e, <A>) = (s₀, a^R),

где a^R -зеркальное отображение a.

2. Для всех a ОV_т построим команды вида

f (s₀, a, a) = (s₀, $)

3. Для перехода в конечное состояние построим команду

f (s₀, e, h₀) = (s₀, $)

4. Начальную конфигурацию автомата определим в виде:

(s₀, w, h₀<I>),

где w - заданная цепочка, записанная на входной ленте.
Автомат, построенный по приведенным выше правилам, работает следующим образом. Если в вершине магазина находится терминал, и символ, читаемый с входной ленты, совпадает с ним, то по команде типа (2) терминал удаляется из магазина, а входная головка сдвигается. Если же в вершине магазина находится нетерминал, то выполняется команда типа (1), которая вместо терминала записывает в магазин цепочку, представляющую собой правую часть правила грамматики. Следовательно, автомат, последовательно заменяя нетерминалы, появляющиеся в вершине магазина, строит в магазине левый вывод входной цепочки, удаляя полученные терминальные символы, совпадающие с символами входной цепочки. Это означает, что каждая цепочка, которая может быть получена с помощью левого вывода в грамматике Г, допускается построенным автоматом М.

Конфигурацией автомата М называют тройку (s, a, g) О S x P* x H*,

где s - текущее состояние управляющего устройства,
a -неиспользованная часть входной цепочки a О P*,самый левый символ этой цепочки a находится под головкой. Если a =e, то считается, что входная цепочка прочитана.
g -цепочка, записанная в магазине, g О H*,самый правый символ цепочки считается вершиной магазина. Если g= $, то магазин пуст.
Работа автомата может быть представлена как смена конфигураций. Один такт работы автомата заключается в определении новой конфигурации по заданной. Это записывается так:
(s, aa, g h) |-- (s', a, gb)

При этом предполагается, что автомат читает символ a, находящийся под головкой, и символ h,
находящийся в вершине магазина, определяет новое состояние s' и записывает цепочку b в
магазин вместо символа h. Если b =$, то верхний символ оказывается удаленным из магазина.
Такая смена конфигураций возможна, если функция f(s, a, h) определена и ей принадлежит
значение (s', b). Описанный такт работы выполняется с перемещением головки. Для описания работы автомата нам потребуется другой вид такта, предполагающий изменение состояний и магазина без перемещения входной головки. Если f⁰(s, e, h) определена и ей принадлежит значение (s', b), то он определяет смену конфигураций так:

(s, aa, g h) |-- (s', aa, gb)

Таким образом, могут быть три случая при работе автомата:

• f(s, a, h) определена и выполняется такт работы,
• f(s, a, h) не определена, но определена функция f⁰(s, e, h) и выполняется пустой такт.
• Функции f(s, a, h) и f⁰(s, e, h) не определены, в этом случае дальнейшая работа автомата невозможна.

В общем виде действия, задаваемые функцией переходов и выполняемые автоматом, демонстрирует следующая форма записи:

f(s, <входной символ>, <магазинный символ>)=(s₁, <заносимая цепочка>)

При этом следует иметь в виду, что при выполнении такта вначале читается символ в вершине, а затем на его место заносится новый символ или цепочка. Отдельные значения функции переходов часто называют командами магазинного автомата.
Начальной конфигурацией называется конфигурация (s_о, a, h_о), где s_о -начальное состояние и h_о - маркер дна магазина, а заключительной - конфигурация (s, $, $), где s принадлежит множеству конечных состояний F.
Для обозначения последовательности сменяющих друг друга конфигураций условимся
использовать знак |--*. Таким образом последовательность

(s₁, a ₁, g ₁ ) |-- (s₂, a ₂, g ₂) |--...|-- (s_n, a _n,g _n )

записывается в сокращенном виде так:

(s₁,a ₁, g ₁ ) |--* (s_n, a _n,g _n ).