25-08-2023
Блокиро́вочное соедине́ние, или блокиро́вка семейства конечных автоматов , определяется заданием множества предикатов блокировки переходов этих автоматов:
где — множество состояний автомата . Предикаты блокировки , выражают взаимные ограничения на переходы автоматов, связанных блокировочным соединением.
Если , где , то автомат «заблокирован» набором состояний остальных автоматов: все переходы автомата «запрещены», любой входной сигнал автомата заменяется тождественным входным сигналом.
Если , то переходы автомата не зависят от состояний других автоматов: все переходы автомата «разрешены», автомат ведет себя в соответствии с собственными функциями переходов и выходов.
Если , то блокировочное соединение автоматов и определяется парой предикатов блокировки и . Обозначим:
Элементы множеств и называются разрешающими состояниями автоматов и соответственно, элементы множеств и — запрещающими состояниями автоматов и .
Если один из двух автоматов или находится в разрешающем состоянии, то другой работает как бы «сам по себе», как предписывают его собственные функции переходов и выходов. Если же один автомат находится в запрещающем состоянии, то работа другого автомата полностью блокируется: каждый его входной сигнал заменяется тождественным.
Если одно из множеств запрещающих состояний или пусто, то блокировка называется односторонней. В противном случае – двусторонней или взаимной. При односторонней блокировке работа только одного из соединяемых автоматов зависит от состояния другого.
Односторонняя блокировка есть частный случай каскадного соединения автоматов. Взаимная блокировка не является частным случаем каскадного соединения.
Односторонняя блокировка автомата автоматом называется максимальной, если множество содержит ровно один элемент. При максимальной односторонней блокировке автомат работает (в соответствии со своими функциями переходов и выходов) только при одном состоянии автомата . Все остальные состояния автомата являются блокирующими для автомата .
Автомат группы сильно связен точно тогда, когда его группа транзитивна. Группа автомата максимальной односторонней блокировки перестановочного автомата сильно связным перестановочным автоматом есть подстановочное сплетение групп автоматов и . Обратно, подстановочное сплетение конечной группы и транзитивной конечной группы изоморфно группе максимальной односторонней блокировки перестановочного автомата , группа которого есть , перестановочным автоматом , группа которого есть .
Взаимная блокировка автоматов и называется максимальной, если их множества разрешающих состояний и содержат ровно по одному элементу. Группа максимальной взаимной блокировки двух сильно связных перестановочных автоматов и , число состояний которых равно и соответственно, есть либо симметрическая группа , либо знакопеременная группа . Второй случай имеет место тогда и только тогда, когда группы обоих автоматов и содержат только четные подстановки.
Блокировочное соединение автоматов.