En la teoría de los 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 0 , 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 0 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 qi y q j enQy cada símbolo de entradaxen Σ, δ (q i ,x) ≠ δ (q j ,x).
Un lenguaje formal es p-regular (también: un lenguaje de grupo puro ) si es aceptado por un autómata de permutación. Por ejemplo, el conjunto de cadenas de longitud uniforme forma un lenguaje p-regular: puede ser aceptado por un autómata de permutación con dos estados en los que cada transición reemplaza un estado por el otro.
Aplicaciones
Los lenguajes de grupo puro fueron la primera familia interesante de lenguajes regulares para los que se demostró que el problema de la altura de las estrellas era computable . [1] [3]
Otro problema matemático en los lenguajes regulares es el problema de separación de palabras , que pide el tamaño de un 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. El límite superior conocido en el caso general es. [4] Posteriormente se estudió el problema de la restricción a los autómatas de permutación. En este caso, el límite superior conocido cambia a. [5]
Referencias
- ^ a b McNaughton, Robert (agosto de 1967), "La complejidad de bucle de eventos de grupo puro", Información y control , 11 (1-2): 167-176, doi : 10.1016 / S0019-9958 (67) 90481-0
- ^ Thierrin, Gabriel (marzo de 1968). "Autómatas de permutación". Teoría de los sistemas informáticos . 2 (1): 83–90. doi : 10.1007 / BF01691347 .
- ^ Janusz A. Brzozowski : Problemas abiertos sobre lenguajes regulares , En: Ronald V. Libro, editor, Teoría del lenguaje formal — Perspectivas y problemas abiertos , págs. 23–47. Academic Press, 1980 (versión del informe técnico)
- ^ Demaine, ED ; Eisenstat, S .; Shallit, J .; Wilson, DA (2011). "Observaciones sobre la separación de palabras". Complejidad descriptiva de los sistemas formales . Apuntes de conferencias en Ciencias de la Computación. 6808 . págs. 147-157. doi : 10.1007 / 978-3-642-22600-7_12 . ISBN 978-3-642-22599-4.
- ^ JM Robson (1996), "palabras de separación con las máquinas y los grupos" , RAIRO - Informatique et théorique aplicaciones , 30 (1): 81-86 , recuperada 2012-07-15
 | Este artículo relacionado con métodos formales es un fragmento . Puedes ayudar a Wikipedia expandiéndolo . |
