13) Понятие о конечных автоматах. Эквивалентность и произведение конечных автоматов.

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

Например:  = {0, 1} – бинарный или двоичный алфавит;

 = {a, b, …, z} – множество строчных букв английского алфавита;

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

Языком (формальным) назовем множество цепочек L, каждая из которых принадлежит ^* (L ≤ ^*).

Автоматом называют устройство, которое без непосредственного участия

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

преобразование материальных объектов, энергии, информации.

Для удобства аналитического описания абстрактный автомат считают дискретным устройством -

входные сигналы поступают в автомат, состояние автомата меняется и выходные сигналы формируются

в определенные моменты времени, а не непрерывно.

Автоматные функции.

Для описания функционирования автомата используют систему канонических уравнений конечного автомата в виде соотношений:

q(t₁)=q₀;

q(t_i+1)=Ψ(q(t_i),x(t_i));

y(t_i)=Ξ(q(t_i),x(t_i));

где i - номер такта, t_i - момент времени, q₀ - начальное состояние автомата, Ψ(q(t_i),x(t_i)) функция переходов состояний автомата, Ξ(q(t_i),x(t_i)) - функция выхода. Обобщающее название функций переходов и выходов - автоматные функции.

Конечным автоматом Мили называется шестерка объектов: А = < X, Y, Q, q₀, ψ, θ >, где:

Q – конечное непустое множество состояний;

X – конечное непустое множество входных сигналов (входной алфавит);

Y – конечное непустое множество выходных сигналов (выходной алфавит);

q₀ <Q – начальное состояние;

ψ: QX  Q – функция переходов;

θ : QX  Y – функция выходов.

Пусть A = <X, Y, Q, q0, ψ, θ> – конечный автомат.

Расширенными функциями перехода и выхода автомата А называются функции ψ* : Q´X*→ Q и θ*: Q´X*→ Y*, определенные так:

ψ* (q, e) =q; ψ*(q, ag)=ψ*(ψ(q, a), g);

θ*(q, e) = e; θ*(q, ag) = θ(q, a) ^ θ*(ψ(q, a), g).

Здесь e – пустая цепочка, a - символ,

g – произвольная цепочка.

Другими словами: обычные функции определены на всех входных сигналах, а расширенные функции переходов и выходов – на множестве входных цепочек.

Состояние q конечного автомата называется достижимым тогда и только тогда, когда существует такая цепочка g, что ψ*(q₀, g) = q (т.е. под воздействием какой-либо цепочки входных сигналов, автомат переходит в состояние q). Противоположно – недостижимо.

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

Два конечных автомата эквивалентны, если реализуемые ими отображения вход-выход эквивалентны.

Конечные автоматы A = <Xа, Yа, Qа, q0а, ψа, θа> и В = <Xв, Yв, Qв, q0в, ψв, θв> называются эквивалентными, если

выполнены два условия:

1) их входные алфавиты совпадают: Ха = Хв =Х;

2) реализуемые ими отображения совпадают для любой цепочки g : θа(q0а, g) = θв(q0в, g).

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

При входной цепочке aabbсb автоматы выдают одинаковые выходы: A: → 000010, B: →000010.

Минимальный автомат – эквивалентный заданному и имеющий наименьшее из всех возможных количество состояний

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

Два состояния p и q конечного автомата A = <X, Y, Q, q0, ψ, θ> называются эквивалентными, если для любого z из X* выполнено θ*(p, z) = θ*(q, z).

Эквивалентные состояния можно объединить в один класс, и настроить новый автомат, состояниями которого являются классы эквивалентности состояний.

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

Доказательство эквивалентности автоматов

Конечный автомат, являющийся прямым произведением двух конечных автоматов, в качестве своих состояний имеет пары состояний исход­ных автоматов, его начальное состояние есть пара их начальных состояний, вы­ходной алфавит — множество пар выходных символов автоматов-множителей, а функции переходов и выходов определены покомпонентно.

Т.о, пря­мое произведение конечных автоматов — это просто два стоящих рядом невзаи­модействующих конечных автомата, синхронно работающих на одном общем входе.

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

Автоматы Мура образуют другой класс моделей, с точки вычислительной мощности полностью эквивалентный классу автоматов Мили. В автомате Мура функция θ определяется не на паре (состояние, входной сигнал), а только на состоянии: θ : S à Y

Эквивалентные конечные автоматы Мили и Мура

Примеры: