L'équivalence entre les deux automates
Qui est la meilleure ou la plus facile méthode pour la détermination de l'équivalence entre deux automates?
I. e., si, étant donnés deux automates nis A et B, comment puis-je déterminer si les deux reconnaissent le même langage?
Ils sont à la fois déterministe ou les deux de façon non déterministe.
Vous devez signaler vos devoirs avec [devoirs]. Cela rend plus facile pour nous de fournir l'aide appropriée. Vous devez fournir votre meilleure réponse afin que nous puissions commenter. S'il vous plaît ne nous demandez pas de faire vos devoirs pour vous. Qu'apprenez-vous alors?
cela devrait être dans le cstheory.stackexchange.com
Qu'entendez-vous par "équivalent"? Vous dites qu'ils génèrent la même langue. Entendez-vous les graphiques sont isomorphe?
DFA = AFD, NFA = APN, NFA-lambda = AFN-lambda
Les automates ne génèrent pas de langues, d'automates reconnaître les langues
cela devrait être dans le cstheory.stackexchange.com
Qu'entendez-vous par "équivalent"? Vous dites qu'ils génèrent la même langue. Entendez-vous les graphiques sont isomorphe?
DFA = AFD, NFA = APN, NFA-lambda = AFN-lambda
Les automates ne génèrent pas de langues, d'automates reconnaître les langues
OriginalL'auteur franvergara66 | 2011-08-01
Vous devez vous connecter pour publier un commentaire.
Deux finis non déterministes automota (NFA) sont équivalentes si elles acceptent le même langage.
Afin de déterminer s'ils acceptent le même langage, nous regardons le fait que tous les NFA a un minimum de DFA, où aucun des deux états sont identiques. Un minimum de DFA est également unique. Ainsi, compte tenu de deux NFA, si vous trouvez que leur correspondant minimale DFA sont équivalentes, alors que les deux ADN doit également être équivalent.
Pour une étude approfondie sur ce sujet, je vous recommande fortement de lire Une Introduction aux langages Formels et Automates.
Une autre solution serait de générer une DFAs pour le Fan (par exemple, par le sous-ensemble de la construction), calculer le complément de l'un des deux DFAs (par exemple en acceptant des états de rejet et vice-versa), la construction du produit Cartésien de la machine et le test de l'intersection de voir si elle accepte le vide de la langue (par exemple, par l'analyse des chaînes de longueur n). Je ne dirais pas ce efficace, mais vous auriez encore besoin de tester graphique isomorphisme sur la sortie de Stargazer712 de réponse.
la détermination de la suffisant n pourrait ne pas être facile, ou est-il un algorithme pour le calcul? Et qu'entendez-vous par la nécessité de tester le graphique isomorphisme?
Je pense que la détermination de l'équivalence de deux minimes DFA devrait être facile, il suffit de faire une BFS à travers les deux dans le même ordre. Comme les arêtes correspondantes devraient être marquées par les mêmes caractères, il suffit de trier les sortants bords de chaque état par ceux-ci.
juste assez. J'ai supprimé ce paragraphe de la réponse, car il n'était pas nécessaire, ni même répondre à la question d'origine. Quiconque étudie ce sujet devrait être très familier avec les techniques de réduction de l'ADN d'une TFD de toute façon.
OriginalL'auteur riwalk
Un autre, l'approche la plus simple est de compléter et recouper les automates. Un automate
A
est équivalent àB
iffL(A)
est contenue dansL(B)
et inversement, ce qui est le forum de l'intersection entre le complément deL(B)
etL(A)
est vide, et vice-versa.Voici l'algorithme pour vérifier si
L(A)
est contenue dansL(B)
:B
en utilisant le sous-ensemble de la construction. Ensuite, chaque état acceptant de rejet et chaque de rejet de l'état de l'accepter. Vous obtenez un automate qui reconnaît le complément deL(B)
.L(B)
etL(A)
. I. e., construire un automate pour l'intersection de l'automate à partir de l'étape 1 etA
. À l'intersection de deux automatesU
etV
vous construire un automate à étatsU x V
. L'automate se déplace à partir de l'état(u,v)
à(u',v')
avec lettrea
le forum il y a des transitionsu --a--> u'
dansU
etv --a--> v'
dansV
. Le acceptant les états sont des états(u,v)
oùu
est accepter dansU
etv
est accepter dansV
.Si
L(A)
est contenue dansL(B)
nous avons besoin pour exécuter le même algorithme pour vérifier siL(B)
est contenue dansL(A)
.OriginalL'auteur Guy
Je suis juste de reformuler la réponse par @Guy.
De comparer les langues acceptées par les deux nous demander si
L(A) is equal to L(B)
ou pas.Ainsi, vous devez savoir si
L(A)-L(B) and L(B)-L(A)
est null ou non. (Reason1)Part1:
Pour le savoir, nous construisons NFA X à partir de l'ADN d'UN et NFA B, .
Si X est vide alors
L(A) = L(B)
d'autreL(A) != L(B)
. (Reason2)Part2:
Maintenant, nous devons trouver un moyen efficace de confirmer ou infirmer
X is empty set
. Quand sera vide de X comme DFA ou de l'ADN? Réponse: X sera vide quand il n'y a pas de chemin menant de l'état de départ de tout de l'état final de X. On peut utiliser BFS ou DFS pour cela.Reason1: Si les deux sont nuls alors
L(A) = L(B)
.Reason2: Nous pouvons prouver que l'ensemble des langages réguliers est fermé en vertu de l'intersection et d'union. Ainsi, nous serons en mesure de créer de la NFA X efficacement.
et pour les ensembles:
OriginalL'auteur foxtrot9