Autómata de permutación

En la teoría de autómatas , un autómata de permutación , o autómata de grupo puro , es un autómata finito determinista tal que cada símbolo de entrada permuta el conjunto de estados. ^{[ 1 ] [ 2 ]}

Formalmente, un autómata finito determinista A puede definirse mediante la tupla ( Q , Σ, δ, q ₀ , F ), donde Q es el conjunto de estados del autómata, Σ es el conjunto de símbolos de entrada, δ es la función de transición que lleva un estado q y un símbolo de entrada x a un nuevo estado δ( q , x ), q ₀ es el estado inicial del autómata y F es el conjunto de estados de aceptación (también: estados finales) del autómata. A es un autómata de permutación si y solo si, para cada dos estados distintos q _i y q _j en Q y cada símbolo de entrada x en Σ, δ( q _i , x ) ≠ δ( q _j , x ).

Un lenguaje formal es p-regular (también llamado lenguaje de grupo puro ) si es aceptado por un autómata de permutación. Por ejemplo, el conjunto de cadenas de longitud par forma un lenguaje p-regular: puede ser aceptado por un autómata de permutación con dos estados en el que cada transición reemplaza un estado por el otro.

Los lenguajes de grupo puro fueron la primera familia interesante de lenguajes regulares para la cual se demostró que el problema de la altura de la estrella era computable . ^{[ 1 ] [ 3 ]}

Otro problema matemático sobre lenguajes regulares es el problema de separación de palabras , que pide determinar el tamaño del autómata finito determinista más pequeño que distingue entre dos palabras dadas de longitud como máximo n , aceptando una palabra y rechazando la otra. La cota superior conocida en el caso general es${\displaystyle O(n^{2/5}(\log n)^{3/5})}$. ^{[ 4 ]} El problema fue estudiado posteriormente para la restricción a autómatas de permutación. En este caso, el límite superior conocido cambia a${\displaystyle O(n^{1/2})}$. ^{[ 5 ]}