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 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:
- Tous les chemins potentiels à travers le DDFA conduisent à un état d'acceptation (nous l'appellerons un DDFA de type 1).
- 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 ?
Les épreuves (ou au moins les croquis modérément étoffés) sont appréciées, si elles ne sont pas trop compliquées.
la source