Сопоставимость конечных автоматов
Пусть S=(As, Qs, Vs, ds, ls ) и Т=(Aт, Qт, Vт, dт, lт ) – два автомата. Тройка отображения f: Аs Þ Aт, g: QsÞQт, h: VsÞVт называется гомоморфизмом автомата S в автомат Т, если для любых аÎ Аs, qÎQs, vÎVs выполнены условия:
dт ( g(q), f(a) ) = g ( ds (q, a) );
lт ( g(q), f(a) ) = h ( ls (q, a) ).
Автомат Т называется гомоморфным автомату S. Если все три отображения сюръективны, то это двойка называется гомоморфизмом S на Т. Если, кроме того, эти три отображения взаимно однозначны, то они называются изоморфизмом S на Т; автоматы, для которых существует изоморфизм, называются изоморфными. Ясно, что мощности соответствующих алфавитов изоморфных автоматов должны быть одинаковыми.
Понятие изоморфизма имеет для автоматов имеет следующий смысл: автоматы S и Т изоморфны, если входы, выходы и состояния S можно переименовать так, что таблица переходов автомата S превратится в таблицу переходов автомата Т.
Автоматы S и T называются неотличимыми, если для любого состояния q автомата S найдется неотличимое состояние r автомата T и, наоборот, для любого состояния r из Т найдется неотличимое от него q из S. Неотличимость автоматов означает, что любое автоматное отображение, реализуемое одним из них, может быть реализовано другим; иначе говоря, их возможности по реализации преобразования входной информации в выходную совпадает. Отношения неотличимости между состояниями и автоматами рефлексивно, симметрично и транзитивно. Следовательно это отношение является отношением эквивалентности.
Пример. Возьмем в качестве S автономный автомат, заданный в таблице 3.10, а в качестве Т – автономный автомат, граф которого приведен на рис.3.10. Существует гомоморфизм S в Т.
Таблица 3.10 - Задание автомата S
| q | 1 2 3 4 5 6 7 8 9 |
| a | 3/0 4/0 4/0 7/0 4/2 5/0 6/1 9/0 9/1 |
w w
v v v v
v
Рис. 3.10 - Автомат Т
Никакое состояние S не отобразилось в r5; заметим, что r5 недостижимо из других состояний. Это – общее правило: если состояние Т не входит в область значений g при гомоморфизме, то оно должно быть недостижимым для любого состояния из этой области, иначе нарушится условие гомоморфизма. Если из автомата Т состояния r5 вместе с инцидентным ему ребром удалить, то получим новый автомат Т; описанная тройка отображений является гомоморфизмом S в Т и S на Т. Как показывает этот пример, число состояний и выходных букв при гомоморфизме может не сохранятся.
3.7. Синхронные сети из автоматов.
Если автоматы рассматривать, как устройства с входами и выходами, то присоединение выходов одних автоматов ко входам других дает схему, или сеть из автоматов, все автоматы которой работают одновременно. Под состоянием сети из m одновременно работающих автоматов S1, ... , Sm (компонент сети) понимается вектор (qi1, ... , qim), где qij - состояние автомата Sj. Поэтому в общем случае число возможных состояний сети равно произведению чисел состояний составляющих ее компонент. Возникает вопрос, является ли сеть из автоматов автоматом; если да, то как получить ее описание из описания ее подавтоматов?
Прежде всего необходимо отметить. что вектор - состояние сети указывает, в каких состояниях находятся компоненты сети в один и тот же момент времени. Таким образом, при описании автоматных сетей - в отличии от абстрактных автоматов - необходимо явно вводить понятие времени. Существует два основных способа введения времени - синхронный и асинхронный. Синхронный способ заключается в следующем. Вводится шкала времени , которая делится на отрезки одинаковой длины (такты); границы тактов называются моментами автоматного времени и нумеруются натуральными числами, начиная с нуля. Длина такта принимается за единицу времени. Входное слово (последовательность букв) рассматривается как временная последовательность сигналов или импульсов (каждый сигнал соответствует букве); интервал между соседними импульсами равен в точности длине такта. Следовательно, слово длины k занимает во времени ровно k тактов. Его буквы можно считать функциями от времени: a(t) - буква, появившаяся на входе в момент t. Автоматные функции d и l реализуются с задержкой. Время задержки функции d равно единице: d(q(t), a(t))=q(t+1); состояние q(0) определено заранее. Время задержки функции l обычно считается равным нулю: l(q(t), a(t))=v(t), но иногда равным единице: l(q(t), a(t))=v(t+1). Во втором случае должно быть определено v(0). Таким образом, под действием последовательности входных сигналов одинаковой длины каждый из автоматов порождает последовательность промежуточных или внутренних сигналов (реализующих состояния) и последовательность выходных сигналов, причем длины тактов этих последовательностей совпадают с длиной каждого такта. Таким образом на практике достигается такая всеобщая синхронизация - за счет внешних синхронизирующих часов либо за счет идеальных временных характеристик и среды в которой они функционируют - на данном уровне рассмотрения несущественно.
Дата добавления: 2015-10-05; просмотров: 894;