Comment voulez-vous construire l'union de deux DFA?
Quelqu'un aurait-il une simple description de l'algorithme pour la construction de l'union de deux DFA? Par exemple, disons que nous avons deux DFA plus de {0,1} où
{w|w has an odd number of characters}
w has states A and B
delta | 0 | 1
----------------
A | B | B
----------------
B | A | A
{x|x has an even number of 1s}
x has states a and b
delta | 0 | 1
----------------
a | a | b
----------------
b | b | a
Je avoir une table de transition montrant l'union:
delta | 0 | 1
----------------
Aa | Ba | Bb
----------------
Ab | Bb | Ba
----------------
Ba | Aa | Ab
----------------
Bb | Ab | Aa
J'ai une solution picturale dans mes notes de cours, mais aimerait voir comment d'autres pourraient le décrire. De cette manière, je peux voir que nous avons essentiellement de "multiplier" ces deux tables d'origine à l'aide de leurs valeurs d'état à engendrer une grande table de transition. Le DFAE peut donc être tirée de la table résultante. Est-ce son droit et si cela fonctionne pour tous les DFA cas, ou est-il quelque chose que je suis absent?
OriginalL'auteur Old McStopher | 2010-12-15
Vous devez vous connecter pour publier un commentaire.
La clé pour comprendre, c'est que vous devez exécuter les deux DFAs simultanément, ou en général, vous devez maintenir les membres des deux DFAs dans l'union DFA.
C'est pourquoi vous devez créer les nouveaux états de l'union DFA comme un direct à la multiplication de l'état d'origine. De cette façon, vous avez un état pour chaque combinaison des états d'origine DFAs.
Les règles transitoires pour la nouvelle DFA peut être directement calculé, alors. Par exemple, si vous êtes en état d'Ab, et vous obtenez un 0 sur la première entrée du DFA serait aller à l'état B et la seconde à l'état b, de sorte que l'union DFA l'état suivant pour cette entrée sera Bb.
Cette méthode fonctionne dans tous les cas, lorsque vous avez besoin de faire une union de deux ou plusieurs DFAs. La résultante de l'IFD peut-être pas optimal, mais plus tard, vous pouvez la réduire avec l'algorithme que vous aimez.
Vous ajoutez E (erreur) de l'état de l'automate qui a impossible de transition. Que l'automate de rester dans cette stat pour le reste de la séquence d'entrée. Disons que c'est la première. Il vous faudra alors Aa, Ab, Ba, Bb, Ea, Eb états dans le nouvel automate.
Je pense qu'il serait similaire si un automate seulement a {0,1} comme entrer des symboles, et l'autre a {1,2} comme entrée de symboles. Nous aurions alors à étendre les deux automates à états d'Erreur (E) pour les première et e pour le second) où 1ère irait à E si 2 est l'entrée, et le 2ème serait aller à l'état si la valeur 0 est l'entrée.
OriginalL'auteur buc