Частичные автоматы
В инженерной практике часто встречаются автоматы, на входы которых некоторые последовательности сигналов никогда не подаются. Такие последовательности будем называть запрещенными входными словами данного автомата, а сам автомат – частичным автоматом. У частичного автомата функции переходов и выходов определены не на всех парах ai, xj. На месте неопределенных состояний и выходных сигналов ставится прочерк. При синтезе обычно производят доопределение частичного автомата, чтобы его схемная реализация получилась как можно проще.
|
xj\ai |
a0 |
a1 |
a2 |
a3 |
|
x1 |
a1/y1 |
a3/y3 |
a2/y2 |
a2/y1 |
|
x2 |
- / - |
- / - |
a0/y4 |
a0/y2 |
Эквивалентность автоматов
Определение. Два автомата Sa и Sb с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакции на любое входное слово совпадают.
Другими словами, при подаче на вход эквивалентных автоматов, находящихся в одинаковом состоянии одних и тех же слов, их выходные слова также должны быть одинаковыми. Оказывается, что для любого автомата Мили существует эквивалентный ему автомат Мура, и, обратно, для любого автомата Мура существует эквивалентный ему автомат Мили.
Рассмотрим алгоритм перехода от произвольного конечного автомата Мили к эквивалентному ему автомату Мура.
Пусть дан конечный автомат Мили Sa = {Aa, Xa, Ya, da, lа},имеющий множество состояний Aa = {a0,a1, …, ai, …, an}, множество входных и выходных сигналов Xa = {x1, x2, …,xj, …, xm} и Y = {y1, y2, …, yg, …, yk}, а также функции переходов da(a,x) и выходов la(a,x).
Требуется построить эквивалентный ему автомат Мура Sb = {Ab, Xb, Yb, db, lb}, у которого Xb = Xa, Yb = Ya, т.к. множества входных и выходных сигналов у эквивалентных автоматов должны совпадать.
Для определения множества состояний Ab автомата Мура образуем всевозможные пары вида (ai, yg), где yg – выходной сигнал, приписанный входящей в ai дуге. Например, для вершины ai имеем пары (ai, y1), (ai, y2), (ai, y3). Если такие пары мы образуем для всех вершин, то получим множество пар, которое является множеством состояний автомата Мура Ab = {(a0, y1), (a0, y2), …, (an, yk)} = {b1, b2, …, bn}, где bl = (ai, yg).
предыдущая темаследующая