Généraliser l'algorithme de minimisation DFA de Brzozowski en automates finis avec différentes classes d'états accepteurs?

9

L'algorithme de Brzozowski pour convertir un DFA en DFA à état minimum équivalent est remarquablement simple: si dénote le NFA formé en inversant tous les bords d'un DFA D , faisant de l'ancien état de départ un état acceptant et faisant de l'ancien acceptant Etats commencent états, et si P ( N ) représente le résultat de l' application de la construction du sous - ensemble de la NFA N , alors P ( R ( P ( R ( D ) ) ) ) est un DFA minimum d'état avec la même langue que D .R(D)DP(N)N

P(R(P(R(D))))
D

Nous pouvons considérer un DFA comme un dispositif de calcul qui accepte une chaîne d'entrée et génère ensuite 0 si w se termine dans un état de rejet et 1 si w se termine dans un état d'acceptation. Une généralisation naturelle des DFA a associé chaque état du DFA à un certain nombre naturel compris entre 0 et k - 1 , inclus.wwwk−1

À ma connaissance, il est possible de minimiser ces classes modifiées de DFA en utilisant un algorithme de minimisation basé sur la distinction, tel que celui canonique de Hopcroft. Cependant, je ne vois pas comment il serait possible d'adapter l'algorithme de minimisation de Brzozowski à cette nouvelle classe d'automates car l'étape clé (inversion de l'automate) n'a plus d'interprétation claire dans ce cadre généralisé.

Existe-t-il une généralisation connue de l'algorithme de Brzozowski pour minimiser ces sortes d'automates? Sinon, y a-t-il des raisons théoriques pour lesquelles nous nous attendrions à ce qu'un tel algorithme modifié n'existe pas?

automata-theory minimization templatetypedef
la source
la "généralisation" ne semble pas être clairement définie. qu'est-ce que ? s'agit-il simplement d'associer chaque état d'un DFA à une valeur entière bornée? alors quoi? qu'est-ce qu'un exemple? qui travaille avec ça? etck
vzn
{0,1,2,3,...,k−1}
ok, ce n'est pas du tout communiqué dans la publication, "le DFA génère le # associé à l'état dans lequel se termine la chaîne", vous suggérons de résoudre ce problème. en outre, les DFA n'ont techniquement pas de "sortie". peut-être voulez-vous dire transducteur FSM? il existe en effet une théorie partielle associée à la minimisation du transducteur FSM qui n'est apparemment pas ("encore"?) totalement liée à la minimisation du DFA.
vzn

Réponses:

7

La réponse à ta question est oui.

Voir les articles de Bonchi, Bonsangue, Rutten et Silva, l'algorithme de Brzozowski (co) algébriquement (version courte de la conférence) et la dualité Algebra-Coalgebra dans l'algorithme de minimisation de Brzozowski (version de journal plus longue avec plus de généralisations).

Ils donnent une présentation (légèrement) catégorique de l'algorithme de Brzowzowski et l'utilisent pour en dériver des versions pour des classes d'automates plus générales, y compris les automates Moore (ce qui donne une réponse affirmative à votre question).

Neel Krishnaswami
la source
6

Juste pour ajouter à la réponse de Neel, dans mon livre Automatic Sequences avec Jean-Paul Allouche, nous discutons des DFAO (automates déterministes finis avec sorties), qui sont exactement ce que vous avez demandé (associer une sortie à chaque état). Et le théorème 4.3.3 décrit comment inverser une telle machine.

Jeffrey Shallit
la source