Hispanopedia Wiki
Articulo de referencia

Autómata de estados finitos aperiódico

Un autómata de estados finitos aperiódico (también llamado autómata sin contador ) es un autómata de estados finitos cuyo monoide de transición es aperiódico . Propiedades Un le...

Hispanopedia WikiContenido en espanolLectura gratuita

Un autómata de estados finitos aperiódico (también llamado autómata sin contador ) es un autómata de estados finitos cuyo monoide de transición es aperiódico .

Propiedades

Un lenguaje regular es libre de estrellas si y solo si es aceptado por un autómata con un monoide de transición finito y aperiódico . Este resultado de la teoría de autómatas algebraicos se debe a Marcel-Paul Schützenberger . [ 1 ] En particular, el autómata mínimo de un lenguaje libre de estrellas siempre es libre de contadores (sin embargo, un lenguaje libre de estrellas también puede ser reconocido por otros autómatas que no son aperiódicos).

Un lenguaje sin contador es un lenguaje regular para el cual existe un entero n tal que para todas las palabras x , y , z y enteros m ≥ n se cumple que xy m z pertenece a L si y solo si xy n z pertenece a L. Para estos lenguajes, cuando una cadena contiene suficientes repeticiones de cualquier subcadena (al menos n repeticiones), cambiar el número de repeticiones a otro número que sea al menos n no puede cambiar la pertenencia al lenguaje. (Esto es automáticamente cierto cuando y es la cadena vacía , pero se convierte en una condición no trivial cuando y no está vacía). Otra forma de enunciar el teorema de Schützenberger es que los lenguajes sin estrella y los lenguajes sin contador son lo mismo.

Un autómata aperiódico satisface la conjetura de Černý . [ 2 ]

Referencias

  1. ↑ Schützenberger, Marcel-Paul (1965). "Sobre monoides finitos que solo tienen subgrupos triviales" (PDF) . Information and Control . 8 (2): 190– 194. doi : 10.1016/s0019-9958(65)90108-7 .
  2. ↑ Trahtman, Avraham N. (2007). "La conjetura de Černý para autómatas aperiódicos" . Discrete Math. Theor. Comput. Sci. 9 (2): 3– 10. ISSN 1365-8050 . Zbl 1152.68461 . Archivado del original el 23 de septiembre de 2015. Consultado el 5 de abril de 2014 .  
  • McNaughton, Robert; Papert, Seymour (1971). Autómatas sin contador . Monografía de investigación. Vol.  65. Con un apéndice de William Henneman. MIT Press. ISBN 0-262-13076-9. Zbl 0232.94024 . 
  • Sonal Pratik Patel (2010). Un examen de los autómatas sin contador (PDF) (Tesis de maestría). Universidad Estatal de San Diego.— Un examen exhaustivo de McNaughton, Papert (1971).
  • Thomas Colcombet (2011). "Las relaciones de Green y su uso en la teoría de los autómatas". En Dediu, Adrián-Horia; Inenaga, Shunsuke; Martín-Vide, Carlos (eds.). Proc. Teoría y aplicaciones del lenguaje y los autómatas (LATA) (PDF) . LNCS. vol.  6638. Saltador. págs. 1 a 21. ISBN  978-3-642-21253-6.— Utiliza las relaciones de Green para demostrar el teorema de Schützenberger y otros teoremas.