Langues acceptées par les versions modifiées des automates finis

16

Un automate fini déterministe (DFA) est un modèle de machine à états capable d'accepter tous et seulement les langages réguliers. Les DFA peuvent être (et sont généralement) définis de telle manière que chaque état doit fournir une transition pour tous les éléments de l'alphabet d'entrée; en d'autres termes, la fonction de transition δ:Q×ΣQ devrait être une fonction (totale).

Imaginez ce que nous appellerons un automate fini doublement déterministe (DDFA). Il est défini de manière similaire à un DFA, à deux exceptions près: premièrement, au lieu de la transition menant d'un état à un autre état pour chaque symbole d'entrée possible, il doit conduire à deux états distincts; deuxièmement, pour accepter une chaîne, tous les chemins potentiels doivent satisfaire l'une ou l'autre des conditions suivantes:

  1. Tous les chemins potentiels à travers le DDFA conduisent à un état d'acceptation (nous l'appellerons un DDFA de type 1).
  2. Tous les chemins potentiels à travers le DDFA conduisent au même état d'acceptation (nous l'appellerons un DDFA de type 2).

Maintenant pour ma question:

Quelles sont les langues acceptées par les DDFA de type 1 et de type 2? Plus précisément, est-il vrai que , ou ? Dans le cas où , existe-t-il une description facile de ?L(DFA)L(DDFA)L(DDFA)=L(DFA)L(DDFA)L(DFA)L(DDFA)L(DFA)L(DDFA)

Les épreuves (ou au moins les croquis modérément étoffés) sont appréciées, si elles ne sont pas trop compliquées.

Patrick87
la source

Réponses:

9

Ceci combiné avec la réponse d' Alex donne l'image complète.

peut être prouvé en adaptant la construction du jeu de puissance habituel avec une condition d'état final modifiée. Dans la construction de l'ensemble de puissance, les états sont des ensembles d'états de l'automate d'origine. Habituellement, après avoir effectué la construction du jeu de puissance, un état est final si l'un des états de l'ensemble est définitif dans l'automate d'origine.L(DDFA)L(DFA)

  • Dans DDFA de type 1, les états finaux de l'automate construit sont les ensembles où tous les éléments sont finaux dans l'automate d'origine.

  • Dans DDFA de type 2, les états finaux sont les ensembles singleton des états finaux de l'automate d'origine.

Dans les deux cas, les automates résultants sont des DFA.

Désormais, les 2DDFA de type ne peuvent exprimer que les langues et , selon que l'état de départ accepte ou non. En effet, les deux transitions d'un état doivent aller vers des états distincts, mais l'acceptation n'est possible que si elles aboutissent au même état.{ϵ}

Dave Clarke
la source
7

Pour commencer l'analyse, je peux dire que pour le type-1.L(DFA)L(DDFA)

Vous pouvez le faire en dupliquant un DFA et en ajoutant des bords aux états dupliqués. Si un état a une transition vers s 2 sur x , vous effectuez également une transition de s 1 vers s ' 2 sur x . De plus, s ' 1 a une transition vers s 2 et s ' 2 sur x . Évidemment, cela signifie que nous serons presque toujours dans les états s i et s i en même temps (ou peut-être seulement s is1s2xs1s2xs1s2s2xsisisi, initialement), et donc nous reconnaîtrons la même langue.

Mise à jour: nous avons également pour le type 2, car il n'existe pas de DDFA de type 2 qui reconnaît le langage { a } . Si vous essayez de créer un tel DDFA, vous avez un état de départ s , puis vous devez avoir deux fronts sortants vers les états s 1 et s 2 sur un a , mais ces états doivent être distincts, et donc les deux chemins d'acceptation se terminent dans différents États accepteurs.L(DFA)L(DDFA){a}ss1s2a

Avec la réponse de Dave Clarke, cela vous donne l'analyse complète.

Alex ten Brink
la source
Très agréable de repérer ce contre-exemple pour le type 2!
Dave Clarke
@Dave Clarke: merci. C'est un peu un exemple idiot, mais ça marche :)
Alex ten Brink
"Pathologique" au lieu de "idiot".
Dave Clarke
Très beau travail, les gars. Il y avait quatre choses à vérifier, et chacun de vous en a obtenu deux. À moins que l'un de vous ne s'y oppose, je vais choisir @DaveClarke comme réponse, uniquement parce qu'il a moins de représentants qu'Alex.
Patrick87
1
Sur une note connexe, aimeriez-vous développer les langues acceptées par les DDFA de type 2, ou devrais-je poser une question distincte et un lien vers celle-ci?
Patrick87