Minimização do DFA em vários idiomas

Estou interessado em uma ligeira generalização do DFA. Como sempre, temos definido pelo estado , alfabeto finito , uma ação definida em por e estado inicial ; mas em vez do conjunto de terminais de costume, nós tomamos uma família de subconjuntos de . Um DFA multilíngue é a tupla $Q$ $\Sigma$ $\Sigma^*$ $Q$ $\delta : Q\times\Sigma\rightarrow Q$ $q_0$ $(T_i)_{i\in 1..n}$ $Q$ $M$

$(Q, \Sigma, \delta, q_0, (T_i))$

e é reconhecido por iff para alguns . Defina para ser a família de idiomas reconhecida por M, se desejar. $L \subseteq \Sigma^*$ $M$ $L = \{s\in\Sigma^*|q_0s\in T_i\}$ $i\in 1..n$ $(L_i(M))_{i\in 1..n}$

Ok, agora a minha pergunta: dada uma família de idiomas regulares , quero encontrar o mínimo DFA multilíngue, conforme descrito acima, para que para tudo , isto é, tal queé minimizado em todas essas máquinas. Minha pergunta é: existem formas eficientes conhecidas de fazer isso, talvez análogas à teoria padrão de minimização do DFA? Por outro lado, há alguma evidência de que esse problema possa ser difícil? $(L_i)_{i\in 1..n}$ $M$ $L_i = L_i(M)$ $i\in 1..n$ $|Q|$

automata-theory dfa gdmclellan
fonte

Parece-me que o algoritmo padrão baseado no refinamento de partição, modificado apenas para começar particionando o conjunto inicial de estados, se eles estão aceitando / não aceitando para cada um dos subconjuntos vez de um único conjunto , deve funcionar imediatamente. Por que não? Ele só divide pares de estados quando eles devem ser divididos, portanto, ainda gera o refinamento mais grosseiro possível dos estados.

T_{i}

$T_i$

T

$T$

David Eppstein 15/02

A prova do comentário de @DavidEppstein é fácil se você definir a relação de equivalência se para cada , onde é a relação de equivalência Myhill-Nerode. Você pode seguir as mesmas linhas do algoritmo de minimização padrão.

x \sim y

$x\sim y$

x \sim_{T_{i}} y

$x\sim_{T_i}y$

i

$i$

x \sim_{T_{i}} y

$x\sim_{T_i} y$

Shaull

não entendo direito. a resposta para esse problema é encontrar o DFA mínimo de uma união de DFAs com a mesma "configuração", exceto diferentes estados finais, cada DFA por ? também a definição de reconhecimento de não parece fazer sentido exatamente, parece misturar seqüências de caracteres e conjuntos de estados.

1.. n

$1..n$

L = {. . .}

$L=\{...\}$

vzn

Os argumentos de DavidEppstein e Shaull parecem convincentes; encontrarei algum tempo para analisar o teorema de Myhill-Nerode quando tiver tempo para me convencer de que o quociente ainda produz o autômato mínimo. Em retrospecto, parece óbvio demais.

Gdmclellan

@ vzn: definitivamente não queremos unir os idiomas do autômato original; e o

podem sobrepor-se. A multi-idioma DFA com linguagens

deve ser capaz de relatório, por exemplo, que

, mas

. Quanto à notação usada na definição do reconhecimento de um idioma, a notação é definida estendendo

a uma ação

pelas seguintes regras para todos os

T_{i}

$T_i$

A

$A$

B

$B$

s \in A

$s\in A$

s \notin B

$s\notin B$

δ

$\delta$

Σ^{*}

$\Sigma^*$

Q

$Q$

q \in Q, σ \in Σ, s \in Σ^{*}

$q\in Q, \sigma\in\Sigma, s\in\Sigma^*$

q σ = δ (q, σ), q (s σ) = (q s) σ

$q\sigma = \delta(q, \sigma), q(s\sigma) = (qs)\sigma$

Gdmclellan

Respostas:

Resposta curta . Dada uma família finita de linguagens regulares , existe um multi-autômato completo determinístico mínimo exclusivo que reconhece essa família. $\mathcal{L} = (L_i)_{1 \leqslant i \leqslant n}$

Detalhes . O caso corresponde à construção padrão e o caso geral não é muito diferente em espírito. Dada uma linguagem e uma palavra , deixe- . Defina uma relação de equivalência em , definindo $n = 1$ $L$ $u$ $u^{-1}L = \{ v \in A^* \mid uv \in L \}$ $\sim$ $A^*$ Como os são regulares, essa congruência tem índice finito. Além disso, é fácil de ver que cada é saturado por e que, para cada , implica . Vamos denotar por a palavra vazia e por o de classe de uma palavra

u \sim v ⟺ for each L \in L, u^{- 1} L = v^{- 1} L

$u \sim v \iff \text{for each }L \in \mathcal{L},\ u^{-1}L = v^{-1}L$

L_{i}

$L_i$

L_{i}

$L_i$

\sim

$\sim$

a \in A

$a \in A$

u \sim v

$u \sim v$

u a \sim v a

$ua \sim va$

1

$1$

[u]

$[u]$

\sim

$\sim$

u

$u$ . Deixe

ser o determinista multi-autómato definidos como se segue:

A_{L} = (Q, [1], \cdot, (F_{i})_{1 ⩽ i ⩽ n})

$\mathcal{A}_\mathcal{L} = (Q, [1], \cdot, (F_i)_{1 \leqslant i \leqslant n})$

, $Q = \{ [u] \mid u \in A^*\}$
, $[u] \cdot a = [ua]$
. $F_i = \{ [u] \mid u \in L_i\}$

Por construção, se e somente se e, portanto, aceita a família . Resta provar que é mínima. Na verdade, é mínimo em um forte sentido algébrico (o que implica que ele tenha o número mínimo de estados). Seja e $[1] \cdot u \in F_i$ $u \in L_i$ $\mathcal{A}_\mathcal{L}$ $\mathcal{L}$ $\mathcal{A}_\mathcal{L}$ $\mathcal{A} = (Q, q_-, \cdot, (F_i)_{1 \leqslant i \leqslant n})$ são dois multi-autômatos. Um morfismo é um mapa subjetivo de para tal modo que $\mathcal{A}' = (Q', q'_-, \cdot, (F'_i)_{1 \leqslant i \leqslant n})$ $f: \mathcal{A} \to \mathcal{A}'$ $Q$ $Q'$

, $f(q_-) = q'_-$
para , , $1 \leqslant i \leqslant n$ $f^{-1}(F'_i) = F_i$
para todos e , . $u \in A^*$ $q \in Q$ $f(q \cdot u) = f(q) \cdot u$

Então, para qualquer determinista multi-autómato acessível aceitar , existe um morfismo de para . Para provar isso, primeiro verifica-se que se , então . Agora é definido por onde é qualquer palavra que $\mathcal{A}$ $\mathcal{L}$ $\mathcal{A}$ $\mathcal{A}_\mathcal{L}$ $q_- \cdot u_1 = q_- \cdot u_2 = q$ $u_1 \sim u_2$ $f$ $f(q) = [u]$ $u$ . Então, pode-se mostrar que satisfaz as três propriedades necessárias. $q_- \cdot u = q$ $f$

O final é um pouco superficial, deixe-me saber se você precisar de mais detalhes.

J.-E. PIN
fonte