Является ли обращение минимального DFA также минимальным?

Вопрос в значительной степени в названии. Есть ли время, когда некоторый язык может быть принят минимальным DFA с состояниями, но , обращение , может быть принято DFA с состояниями, где ? $L$ $n$ $L^R$ $L$ $m$ $m<n$

formal-languages reference-request automata finite-automata jmite
источник

Обратная сторона DFA даже не обязательно детерминирована. DFA, который принимает регулярное выражение AAA +, имеет состояние терминала с двумя входящими стрелками с одинаковой меткой.

Ян

Минимальный DFA, принимающий изменение языка, может быть меньше. Рассмотрим конечный язык Слова не эквивалентны, поэтому для любого DFA для требуется как минимум 12 состояний; на самом деле существует DFA с ровно 12 штатами. Обратный язык принят DFA только с 9 состояниями: начальное состояние, состояния, соответствующие начальные , состояния, соответствующие начальным , принимающему состоянию и состоянию отказа; это также оптимальный DFA, поскольку неэквивалентны.

L = (0 + 1)^{2} 2 + (0 + 2)^{2} 1 + (1 + 2)^{2} 0.

$L = (0+1)^22+(0+2)^21+(1+2)^20.$

ϵ, 0, 1, 2, 00, 01, 02, 11, 12, 22, 000, 001

$\epsilon,0,1,2,00,01,02,11,12,22,000,001$

L

$L$

L^{R} = 2 (0 + 1)^{2} + 1 (0 + 2)^{2} + 0 (1 + 2)^{2}

$L^R = 2(0+1)^2 + 1(0+2)^2 + 0(1+2)^2$

0, 1, 2

$0,1,2$

0 (1 + 2), 1 (0 + 2), 2 (0 + 1)

$0(1+2),1(0+2),2(0+1)$

ϵ, 0, 1, 2, 01, 12, 20, 011, 000

$\epsilon,0,1,2,01,12,20,011,000$

Подводя итог, минимальный DFA для требует 12 состояний, а для требуется только 9 состояний. $L$ $L^R$

Как jmite упоминает в своем комментарии для NFAS с многократным запуском утверждает , это явление не может произойти, так как если вы изменить направление всех стрелок в NFA для , то вы получите действительный НКА для . $L$ $L^R$

Юваль Фильмус
источник

Спасибо! Мне почему-то пришло в голову, что вы можете отменить DFA и (напрямую) вернуть DFA, я думаю, что я перепутал это с дополнением.

Jmite

@jmite У меня было то же самое пердение мозга, и я напечатал элегантное доказательство, противореча неправильному ответу. :) Это дополнение, которое работает, как я думал, а не наоборот. К сожалению.

Patrick87

Является ли обращение минимального DFA также минимальным?

Ответы: