User:BENAMARA.amine/sandbox

En théorie des automates, un automate de permutation, ou automate à groupe pur, est un automate fini déterministe tel que chaque symbole d'entrée permute l'ensemble des états.

Formellement, un automate fini déterministe A peut être défini par le tuple (Q, Σ, δ, q₀, F), où Q est l'ensemble des états de l'automate, Σ est l'ensemble des symboles d'entrée, δ est la fonction de transition (anglais) qui prend un état q et un symbole d'entrée x pour mener à un nouvel état δ(q,x), q₀ est l'état initial de l'automate, et F est l'ensemble des états acceptants (ou finaux) de l'automate. A est un automate de permutation si et seulement si, pour chaque paire d'états distincts q_i et q_j dans Q et chaque symbole d'entréex dans Σ, δ(q_i,x) ≠ δ(q_j,x).

Un langage formel est dit p-régulier (ou langage à groupe pur) s'il est accepté par un automate de permutation. Par exemple, l'ensemble des chaînes de longueur paire forme un langage p-régulier : il peut être accepté par un automate de permutation avec deux états dans lesquels chaque transition remplace un état par l'autre.

Applications

Les langages à groupe pur ont été la première famille intéressante de langages réguliers pour lesquels le problème de la hauteur de l'étoile a été prouvé comme étant calculable(Anglais).

Un autre problème mathématique sur les langages réguliers est le problème de séparation des mots, qui consiste à déterminer la taille de l'automate fini déterministe le plus petit qui distingue deux mots donnés de longueur au plus n, en acceptant un mot et en rejetant l'autre. La borne supérieure connue dans le cas général est$O(n^{2/5}(\log n)^{3/5})$. Ce problème a été étudié par la suite pour la restriction aux automates de permutation. Dans ce cas, la borne supérieure connue change pour $O(n^{1/2})$.