En matemáticas e informática , el monoide sintáctico de un lenguaje formal es el monoide más pequeño que reconoce el idioma.
Cociente sintáctico
El monoide libre en un conjunto dado es el monoide cuyos elementos son todas las cadenas de cero o más elementos de ese conjunto, con la concatenación de cadenas como operación monoide y la cadena vacía como elemento de identidad . Dado un subconjunto de un monoide libre , se pueden definir conjuntos que consisten en inversos formales a la izquierda oa la derecha de elementos en. Estos se denominan cocientes y se pueden definir cocientes de derecha o de izquierda, dependiendo de qué lado se esté concatenando. Por lo tanto, el cociente correcto de por un elemento de es el set
De manera similar, el cociente izquierdo es
Equivalencia sintáctica
El cociente sintáctico induce una relación de equivalencia en, llamada relación sintáctica , o equivalencia sintáctica (inducida por).
La equivalencia sintáctica correcta es la relación de equivalencia
- .
De manera similar, la equivalencia sintáctica izquierda es
- .
Observe que la equivalencia sintáctica derecha es una congruencia izquierda con respecto a la concatenación de cadenas y viceversa; es decir, para todos .
La congruencia sintáctica o Myhill congruencia [1] se define como [2]
- .
La definición se extiende a una congruencia definida por un subconjunto de un monoide general . Un conjunto disyuntivo es un subconjunto tal que la congruencia sintáctica definida por es la relación de igualdad. [3]
Déjanos llamar la clase de equivalencia de para la congruencia sintáctica. La congruencia sintáctica es compatible con la concatenación en el monoide, en que uno tiene
para todos . Por tanto, el cociente sintáctico es un morfismo monoide e induce un cociente monoide
- .
Este monoide se llama el monoide sintáctico de. Se puede demostrar que es el monoide más pequeño que reconoce ; es decir, reconoce , y por cada monoide reconociendo , es un cociente de un submonoide de. El monoide sintáctico dees también el monoide de transición del autómata mínimo de. [1] [2] [4]
Un idioma de grupo es aquel para el que el monoide sintáctico es un grupo . [5]
Teorema de Myhill-Nerode
El teorema de Myhill-Nerode establece: un lenguaje es regular si y solo si la familia de cocientes es finito, o equivalentemente, la equivalencia sintáctica izquierda tiene un índice finito (lo que significa que se divideen un número finito de clases de equivalencia). [6]
Este teorema fue probado por primera vez por Anil Nerode ( Nerode 1958 ) y la relaciónPor lo tanto, algunos autores se refieren a ella como congruencia de Nerode . [7] [8]
Prueba
La prueba de la parte "sólo si" es la siguiente. Suponga que un autómata finito que reconoce lee la entrada que lleva al estado . Si es otra cadena leída por la máquina, que también termina en el mismo estado , entonces claramente uno tiene . Por tanto, el número de elementos en es como máximo igual al número de estados del autómata y es como máximo el número de estados finales.
Para una prueba de la parte "si", suponga que el número de elementos en es finito. Entonces se puede construir un autómata donde es el conjunto de estados, es el conjunto de estados finales, el lenguaje es el estado inicial, y la función de transición viene dada por . Claramente, este autómata reconoce. Por lo tanto, un idioma es reconocible si y solo si el conjunto es finito. Tenga en cuenta que esta prueba también construye el autómata mínimo.
Ejemplos de
- Dejar ser el idioma terminado de palabras de longitud uniforme. La congruencia sintáctica tiene dos clases, sí mismo y , las palabras de longitud extraña. El monoide sintáctico es el grupo de orden 2 en. [9]
- El monoide bicíclico es el monoide sintáctico del lenguaje Dyck (el lenguaje de conjuntos equilibrados de paréntesis).
- El monoide libre en (dónde ) es el monoide sintáctico del lenguaje , dónde es la inversión de la palabra .
- Cada monoide finito es homomórfico [se necesita aclaración ] al monoide sintáctico de algún lenguaje no trivial, [10] pero no todo monoide finito es isomórfico a un monoide sintáctico. [11]
- Cada grupo finito es isomorfo al monoide sintáctico de algún lenguaje no trivial. [10]
- El idioma terminado en el que el número de apariciones de y son modulo congruentes es un lenguaje grupal con monoide sintáctico . [5]
- Los monoides traza son ejemplos de monoides sintácticos.
- Marcel-Paul Schützenberger [12] caracterizó los lenguajes sin estrellas como aquellos con monoides sintácticos aperiódicos finitos . [13]
Referencias
- ↑ a b Holcombe (1982) p.160
- ↑ a b Lawson (2004) p.210
- ^ Lawson (2004) p.232
- ^ Straubing (1994) p.55
- ↑ a b Sakarovitch (2009) p.342
- ^ Nerode, Anil (1958), "Transformaciones de autómatas lineales", Actas de la AMS , 9 , JSTOR 2033204
- ^ Brzozowski, Janusz; Szykuła, Marek; Ye, Yuli (2018), "Complejidad sintáctica de los ideales regulares", Teoría de los sistemas informáticos , 62 (5): 1175–1202, doi : 10.1007 / s00224-017-9803-8 , hdl : 10012/12499
- ^ Crochemore, Maxime; et al. (2009), "De la congruencia de Nerode al sufijo autómata con desajustes", Theoretical Computer Science , 410 (37): 3471–3480, doi : 10.1016 / j.tcs.2009.03.011
- ^ Straubing (1994) p.54
- ^ a b McNaughton, Robert; Papert, Seymour (1971). Autómatas sin contador . Monografía de investigación. 65 . Con un apéndice de William Henneman. Prensa del MIT. pag. 48 . ISBN 0-262-13076-9. Zbl 0232.94024 .
- ^ Lawson (2004) p.233
- ^ Marcel-Paul Schützenberger (1965). "Sobre monoides finitos que tienen sólo subgrupos triviales" (PDF) . Información y Computación . 8 (2): 190-194. doi : 10.1016 / s0019-9958 (65) 90108-7 .
- ^ Straubing (1994) p.60
- Anderson, James A. (2006). Teoría de los autómatas con aplicaciones modernas . Con contribuciones de Tom Head. Cambridge: Cambridge University Press . ISBN 0-521-61324-8. Zbl 1127.68049 .
- Holcombe, WML (1982). Teoría de autómatas algebraicos . Estudios de Cambridge en Matemáticas Avanzadas. 1 . Prensa de la Universidad de Cambridge . ISBN 0-521-60492-3. Zbl 0489.68046 .
- Lawson, Mark V. (2004). Autómatas finitos . Chapman y Hall / CRC. ISBN 1-58488-255-7. Zbl 1086.68074 .
- Pin, Jean-Éric (1997). "10. Semigrupos sintácticos". En Rozenberg, G .; Salomaa, A. (eds.). Manual de teoría del lenguaje formal (PDF) . 1 . Springer-Verlag . págs. 679–746. Zbl 0866.68057 .
- Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Prensa de la Universidad de Cambridge . ISBN 978-0-521-84425-3. Zbl 1188.68177 .
- Straubing, Howard (1994). Autómatas finitos, lógica formal y complejidad de circuitos . Progreso en Informática Teórica. Basilea: Birkhäuser. ISBN 3-7643-3719-2. Zbl 0816.68086 .