La question est à peu près dans le titre. Y a-t-il jamais un moment où une langue peut être acceptée par un DFA minimal avec états, mais , l'inversion de , peut être acceptée par un DFA avec états, où ?L R L m m < n
10
La question est à peu près dans le titre. Y a-t-il jamais un moment où une langue peut être acceptée par un DFA minimal avec états, mais , l'inversion de , peut être acceptée par un DFA avec états, où ?L R L m m < n
Réponses:
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.ϵ , 0 , 1 , 2 , 00 , 01 , 02 , 11 , 12 , 22 , 000 , 001 L
En résumé, le DFA minimal pour nécessite 12 états, tandis que celui pour ne nécessite que 9 états.L RL LR
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 RL LR
la source