L'inversion d'un DFA minimal est-elle également minime?

Le DFA minimal acceptant l'inversion de la langue peut être plus petit. Considérons le langage fini Les mots sont , donc tout DFA pour nécessite au moins 12 états; en fait, il existe un DFA avec exactement 12 états. La langue inverse est acceptée par un DFA avec seulement 9 états: un état initial, des états correspondant à initial , états correspondant à initial , un état d'acceptation et un état d'échec; c'est aussi le DFA optimal, car sont inéquivalents.

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$

En résumé, le DFA minimal pour nécessite 12 états, tandis que celui pour ne nécessite que 9 états. $L$ $L^R$

Comme jmite mentionne dans leur commentaire, pour NFA avec de multiples états de départ ce phénomène ne peut se produire, car si vous retournez la direction de toutes les flèches dans un NFA pour , vous obtenez un NFA valable pour . $L$ $L^R$

Yuval Filmus
la source

Merci! J'ai en quelque sorte compris dans ma tête que vous pouviez inverser un DFA et (directement) récupérer un DFA, je pense que je l'ai confondu avec le complément.

jmite

@jmite J'ai eu le même pet de cerveau, et j'ai tapé une preuve élégante par contradiction avec la mauvaise réponse. :) C'est un complément qui fonctionne comme je le pensais, pas une inversion. Oops.

Patrick87

L'inversion d'un DFA minimal est-elle également minime?

Réponses: