Je viens de commencer à apprendre la théorie du calcul ce semestre et un peu confus par l'expression "DFA pour un langage". S'il est demandé de construire un DFA pour une collection de chaînes binaires L, est-ce que cela signifie de trouver DFA M avec L (M) = L ou seulement $ L (M) \ supset L $?Définition de la "DFA pour une langue"
La plupart des cours de compilateur/théorie tendent à avoir des styles différents entourant l'enseignement des définitions des automates finis déterministes et des langages formels, mais je vais essayer de rendre cette description aussi agnostique que possible .
L'expression "DFA pour un langage" signifie: un DFA qui accepte tous les word dans la langue et rejette tous les word non dans la langue. La façon dont j'ai appris les DFA est d'avoir des états finaux/acceptants et des états réguliers qui suppriment la nécessité d'un état d'erreur implicite. Cela signifie qu'un DFA accepte un mot si l'état dans lequel il se trouve à la fin de l'entrée est accepting et il rejette le mot si l'état n'est pas accepting.
Ex:
Définissons L comme la langue qui contient un nombre pair de 1s. Ce seront des chaînes binaires donc les symboles sont juste 0 et 1. 00, 110,
, 111
1111, etc. sont des exemples de mots dans ce langage. Notez que la chaîne vide est dans cette langue.
Nous pouvons avoir deux états dans notre DFA. L'état de départ, appelons-le even 1s, est également un état d'acceptation, car 0 ones est pair. L'autre état est odd 1s, ce n'est pas accepté. Comme pour les transitions, lorsque even 1s reçoit un 1, il passe à odd 1s. Et quand odd 1s reçoit un 1, il passe à even 1s. Maintenant, le nombre de 0 n'a pas d'importance, donc dans l'un ou l'autre état, il passe à lui-même.
Toutes mes excuses pour la double flèche, ce website est grand, mais je ne pouvais pas comprendre comment séparer les transitions entre even 1s et odd 1s
Écrivez votre question de manière précise. ici, DFA pour une langue signifie que vous devez construire une machine pour un langage particulier, mais pas pour un sous-ensemble ou un surensemble. Construire DFA maachine pour lequel L (M) = L.