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

Фон:

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

Вопросов:

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

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

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

Работать с @MichaelWehar

fl.formal-languages automata-theory dfa Whosyourjay
источник

Классическая декомпозиция - теория Крона-Родса - на что посмотреть.

Рассмотрим производные Бжозовского. ru.wikipedia.org/wiki/Brzozowski_derivative

Виджай Д

@halfTrucker Теория Крона-Родса имеет дело с венком. ОП спрашивает о декартовом произведении.

scaaahu

Спасибо @halfTrucker, это действительно интересно! Как говорит scaaahu, я ищу декартово произведение, но ваша ссылка все еще велика.

Whosyourjay

Ответы:

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

Shaull
источник

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

scaaahu

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

Шалл

Давайте дадим очевидный способ восстановить один «фактор» автомата продукта. Если и обозначает автомат произведения, то если мы определим т.е. просто забываю о $\mathcal A_i = (Q_i, \delta_i, q_{0i}, F_i), i = 1,2$ $\mathcal A = \mathcal A_1 \times \mathcal A_2$

π_{1} ((Q, Q^{'})) знак равно Q

$\pi_1( (q, q') ) := q$

A_{2}

$\mathcal A_2$ или проецируя на второй компонент, мы имеем

, также если мы хотим знать, что

выбирает некоторое

и вычисляет в произведенном автомате

Q_{1} = π (Q_{1} \times Q_{2})

$Q_1 = \pi(Q_1\times Q_2)$

δ_{1} (q, x)

$\delta_1(q,x)$

q^{'} \in Q_{2}

$q' \in Q_2$

, следовательно, мы также можем восстановить переход в

π ((δ_{1} (q, x), δ_{2} (q^{'}, x)) = δ_{1} (q, x)

$\pi((\delta_1(q,x), \delta_2(q', x)) = \delta_1(q,x)$

A_{1}

$\mathcal A_1$

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

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

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

A_{1} \times ... \times A_{К} ≅ В_{1} \times ... \times В_{L}

$\mathcal A_1 \times \ldots \times \mathcal A_k \cong \mathcal B_1 \times \ldots \times \mathcal B_l$

, подразумевает ли это

для некоторого переупорядочения

A_{i}, B_{j}

$\mathcal A_i, \mathcal B_j$

k = l

$k = l$

A_{i} ≅ B_{π (i)}

$\mathcal A_i \cong \mathcal B_{\pi(i)}$

. Я предполагаю, что это правда, но у меня пока нет доказательств.

π : {1, \dots k} \to {1, \dots k}

$\pi : \{1,\ldots k \}\to \{1,\ldots k \}$

2) для любых двух автоматов , существует ли третий автомат таким образом, что . $\mathcal A, \mathcal B$ $\mathcal C$ $\mathcal A = \mathcal B \times \mathcal C$

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

π_{1} ((δ_{1} (Q, Икс), δ_{2} (Q^{'}, Икс)) знак равно δ_{1} (Q, Икс) знак равно δ_{1} (π_{1} (Q, Q^{'}), Икс)

$\pi_1( (\delta_1(q, x), \delta_2(q', x)) = \delta_1(q,x) = \delta_1(\pi_1(q,q'), x)$

q \in Q_{1}, q^{'} \in Q_{2}

$q \in Q_1, q' \in Q_2$

π

$\pi$

A_{1} \times A_{2}

$\mathcal A_1 \times \mathcal A_2$

A_{2}

$\mathcal A_2$

$\mathcal A$ $\mathcal B$ $\mathcal B$ $\mathcal A$

$\mathcal B$ $\mathcal A$

$M$ $N$ $M$ $N$

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

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

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

StefanH
источник