(N) DFA avec les mêmes états initial / acceptant

Que sait-on de la classe des langages reconnus par les automates finis ayant le même état initial et acceptant? Il s'agit d'un sous-ensemble approprié des langues régulières (puisque chaque langue de ce type contient la chaîne vide), mais à quel point est-elle faible? Existe-t-il une caractérisation algébrique simple?

Idem pour les langues reconnues par des automates non déterministes ayant le même ensemble d'états initiaux et accepteurs.

Cette question est résolue pour les automates déterministes et pour les automates sans ambiguïté du livre [1]

[1] J. Berstel, D. Perrin, C, Reutenauer, Codes et automates, vol. 129 de l'Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2009.

Dans le cas des automates déterministes, la caractérisation est donnée dans la proposition 3.2.5. Rappelons qu'un sous-magnoïde de A $M$$A^*$ est droit unitaire si, pour tout , u , u v ∈ M implique v ∈ M . $u, v \in M$$u, uv \in M$$v \in M$

Proposition . Soit un sous-ensemble régulier de A ∗ . Les conditions suivantes sont les mêmes:$L$$A^*$

1. est un submonoïde unitaire droit,$L$
2. pour un code de préfixe P ,$L = P^*$$P$
3. L'automate minimal de a un état final unique, à savoir l'état initial.$L$
4. Il existe un automate déterministe reconnaissant ayant l'état initial comme état final unique.$L$

Pour les automates sans ambiguïté, la caractérisation découle du théorème 4.2.2 et peut être énoncée comme suit:

Proposition . Soit un sous-ensemble régulier de A ∗ . Les conditions suivantes sont les mêmes:$L$$A^*$

1. est un submonoïde libre de A ∗ ,$L$$A^*$
2. pour un code C ,$L = C^*$$C$
3. Il existe un automate sans ambiguïté reconnaissant ayant l'état initial comme état final unique.$L$

Enfin, pour les automates non déterministes, la caractérisation est simplement que est un sous-monoïde de A ∗ .$L$$A^*$

Les automates finis dans lesquels l'état initial est également l'unique état accepteur ont la forme , où $r^∗$$r$ est une expression régulière. Cependant, comme J.-E. Pin indique ci-dessous, l'inverse n'est pas vrai: il existe des langues de la forme qui ne sont pas acceptées par un DFA avec un état d'acceptation unique.$r^*$

Intuitivement, étant donné une séquence d'états tels que q 0 = q n soit n = 0 ou le diagramme d'état sous-jacent doit avoir un cycle impliquant q 0 . Ce dernier cas est capturé algébriquement par l'étoile Kleene.$q_0, \ldots, q_n$$q_0 = q_n$$n = 0$$q_0$

Une sous-classe importante de cette famille est une sous-classe de langues 0 réversibles. Une langue est 0-réversible si l'inversion du DFA minimal pour la langue est également déterministe. L'opération d'inversion est définie comme l'échange d'états initial et final et l'inversion de la relation de bord du DFA. Cela signifie qu'une langue 0 réversible ne peut avoir qu'un seul état d'acceptation. Votre question ajoute une restriction supplémentaire selon laquelle cet état devrait être l'état initial. Votre restriction ne définit pas les langues réversibles 0 car un DFA minimal pour ces langues peut avoir des états initial et final distincts.

La classe des langues réversibles est intéressante car elle a été l'une des premières familles de langues à infiniment de chaînes qui ne pouvaient être apprises qu'à partir d'exemples positifs. L'article d'Angluin fournit également une caractérisation algébrique.

Inférence des langues réversibles , Dana Angluin, Journal of the ACM, 1982

Vous pouvez vous référer aux automates semi-fleur, comme le dit leur article: "Un automate semi-fleur (SFA) est un automate de trim avec un état initial unique qui est égal à un état final unique dans lequel tous les cycles doivent passer par le état initial- final ". Reportez-vous à "LA DÉCOMPOSITION HOLONOMIQUE DE LA SEMI-FLEUR AUTOMATIQUE CIRCULAIRE" -Shubh Narayan Singh, KV Krishna.