Эффективная конкатенация ДФА?

16

Существует теоретическое доказательство того, что наивная декартова конструкция продукта для пересечения DFAs - «лучшее, что мы можем сделать». А как насчет объединения двух DFA? Тривиальная конструкция включает в себя преобразование каждого DFA в NFA, добавление эпсилон-перехода и определение результирующего NFA. Можем ли мы сделать лучше? Существует ли известная граница для размера DFA с минимальной конкатенацией (в терминах размеров DFA с "префиксом" и "суффиксом")?

Арье
источник

Ответы:

20

Да - известно, что существуют DFA с и n состояниями, соответственно, так что минимальный DFA для объединения соответствующих языков имеет m * 2 n - 2 n - 1 состояний, что соответствует известной верхней границе.mnm2n2n1

Впервые это было замечено Масловым в 1970 году и вновь открыто Ю, Чжуаном и К. Саломаа в их работе «Сложность состояний некоторых основных операций на обычных языках», TCS 125 (1994), 315-328.

Джеффри Шаллит
источник
1
О(2N+м)
1
м*2N-2N-1