Есть ли четко определенная операция деления на конечных автоматах?

15

Фон:

Учитывая два детерминированных конечных автомата A и B, мы формируем произведение C, позволяя состояниям в C быть декартовым произведением состояний в A и состояний в B. Затем мы выбираем переходы, начальное состояние и конечные состояния, так что язык, принятый C является пересечением языков для A и B.

Вопросов:

(1) Можем ли мы «разделить» C на B, чтобы найти A? Является ли А даже уникальным, с точностью до изоморфизма? Мы заботимся о диаграммах состояния, а не о языках здесь и ниже. Таким образом, мы не позволяем сжимать диаграммы состояний, чтобы уменьшить количество состояний.

(2) Если A уникален, существует ли эффективный алгоритм его поиска?

(3) Каждый ли детерминированный конечный автомат имеет уникальную факторизацию на «простые числа». Штрих здесь означает автомат, который не может быть разложен на множители, то есть записан как произведение двух меньших автоматов.

  • Работать с @MichaelWehar
Whosyourjay
источник
5
Классическая декомпозиция - теория Крона-Родса - на что посмотреть.
2
Рассмотрим производные Бжозовского. ru.wikipedia.org/wiki/Brzozowski_derivative
Виджай Д
2
@halfTrucker Теория Крона-Родса имеет дело с венком. ОП спрашивает о декартовом произведении.
scaaahu
2
Спасибо @halfTrucker, это действительно интересно! Как говорит scaaahu, я ищу декартово произведение, но ваша ссылка все еще велика.
Whosyourjay

Ответы:

8

Взгляните на эту статью MFCS 2013 , которая изучает композицию в автоматах. Возможно, это поможет.

Shaull
источник
2
+1 за ссылку. Цитируя из обсуждения статьи, хотя общий случай все еще открыт , кажется, что статья исследует только случай автоматов перестановки. Есть ли более поздние разработки для общих случаев? Я имею ввиду в смысле декартово произведение? (Теория Крона-Родса имеет дело с венком) Спасибо.
scaaahu
3
Я не знаю ни о каких недавних событиях. Я могу сказать вам, что не было прямой последующей работы над этим документом. Но это может служить признаком того, что проблема действительно не из легких.
Шалл
4

Давайте дадим очевидный способ восстановить один «фактор» автомата продукта. Если и A = A 1 × A 2 обозначает автомат произведения, то если мы определим π 1 ( ( q , q ) ) : = q т.е. просто забываю о A 2Aязнак равно(Qя,δя,Q0я,Fя),язнак равно1,2Aзнак равноA1×A2

π1((Q,Q'))знак равноQ
A2или проецируя на второй компонент, мы имеем , также если мы хотим знать, что δ 1 ( q , x ) выбирает некоторое q Q 2 и вычисляет в произведенном автомате π ( ( δ 1 ( q , x ) , δ 2 ( q , x ) ) = δ 1 ( qQ1знак равноπ(Q1×Q2)δ1(Q,Икс)Q'Q2 , следовательно, мы также можем восстановить переход в A 1 .π((δ1(Q,Икс),δ2(Q',Икс))знак равноδ1(Q,Икс)A1

Поэтому, если мы знаем, что автомат является декартовым (или внешним) автоматом произведения, мы можем легко восстановить факторы.

Но я думаю, что это не то, что вы имеете в виду в отношении других ваших вопросов. Здесь возникают два вопроса (далее под автоматным изоморфизмом я подразумеваю изоморфный как граф состояний, т. Е. Безотносительно к начальным или конечным состояниям, как вы сказали, язык здесь не так важен):

1) Для любого автомата, который изоморфен производному автомату (т.е. может быть каким-либо образом разложен) некоторого конечного числа автоматов, является ли это разложение по существу уникальным? (учитывая, что факторы не могут быть разложены дальше, иначе явно нет). Более точно, если для неразложимых автоматов A i

A1×...×AКВ1×...×ВL
, подразумевает ли это k = l и A iB π ( i ) для некоторого переупорядоченияAя,ВJКзнак равноLAяВπ(я) . Я предполагаю, что это правда, но у меня пока нет доказательств.π:{1,...К}{1,...К}

2) для любых двух автоматов , существует ли третий автомат С таким образом, что = В × С .A,ВСAзнак равноВ×С

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

π1((δ1(Q,Икс),δ2(Q',Икс))знак равноδ1(Q,Икс)знак равноδ1(π1(Q,Q'),Икс)
QQ1,Q'Q2πA1×A2A2

A ВВA

ВA

MNMN

Х. Штраубинг, П. Вейль Введение в конечные автоматы и их связь с логикой,

Сайт курса с большим количеством информации.

Примечание . Существует также другое понятие « факторинга », см. Википедию: фактор-автомат , но это просто правило для коллапсирующих состояний и используется в алгоритмах обучения / вывода языка или минимизации состояний.

StefanH
источник