En informática , más precisamente en la teoría de autómatas , un conjunto reconocible de un monoide es un subconjunto que puede distinguirse por algún morfismo en un monoide finito. Los conjuntos reconocibles son útiles en teoría de autómatas, lenguajes formales y álgebra .
Esta noción es diferente de la noción de lenguaje reconocible . De hecho, el término "reconocible" tiene un significado diferente en la teoría de la computabilidad .
Definición
Dejar ser un monoide , un subconjuntoes reconocido por un monoide si existe un morfismo de a tal que , y reconocible si es reconocido por algún monoide finito. Esto significa que existe un subconjunto de (no necesariamente un submonoide de ) tal que la imagen de es en y la imagen de es en .
Ejemplo
Dejar ser un alfabeto : el conjunto de palabras terminadas es un monoide, el monoide libre en. Los subconjuntos reconocibles deson precisamente los lenguajes habituales . De hecho, tal lenguaje es reconocido por el monoide de transición de cualquier autómata que reconoce el lenguaje.
Los subconjuntos reconocibles de son los últimos conjuntos periódicos de números enteros.
Propiedades
Un subconjunto de es reconocible si y solo si su monoide sintáctico es finito.
El conjunto de subconjuntos reconocibles de está cerrado bajo:
El teorema de Mezei [ cita requerida ] establece que si es el producto de los monoides , luego un subconjunto de es reconocible si y solo si es una unión finita de subconjuntos de la forma , donde cada es un subconjunto reconocible de . Por ejemplo, el subconjunto de es racional y, por tanto, reconocible, ya que es un monoide libre. De ello se deduce que el subconjunto de es reconocible.
El teorema de McKnight [ cita requerida ] establece que sise genera de forma finita, entonces sus subconjuntos reconocibles son subconjuntos racionales . Esto no es cierto en general, ya que todo el es siempre reconocible pero no es racional si se genera infinitamente.
Por el contrario, un subconjunto racional puede no ser reconocible, incluso sise genera de forma finita. De hecho, incluso un subconjunto finito deno es necesariamente reconocible. Por ejemplo, el conjunto no es un subconjunto reconocible de . De hecho, si un morfismo de a satisface , luego es una función inyectiva , por lo tanto es infinito.
Además, en general, no está cerrado bajo la estrella de Kleene . Por ejemplo, el conjunto es un subconjunto reconocible de , pero no es reconocible. De hecho, su monoide sintáctico es infinito.
La intersección de un subconjunto racional y de un subconjunto reconocible es racional.
Los conjuntos reconocibles se cierran bajo morfismos inversos. Es decir, si y son monoides y es un morfismo entonces si luego .
Para grupos finitos el siguiente resultado de Anissimov y Seifert es bien conocida: un subgrupo H de un grupo finito G es reconocible si y sólo si H tiene índice finito en G . Por el contrario, H es racional si y solo si H se genera de forma finita. [1]
Ver también
Referencias
- ^ John Meakin (2007). "Grupos y semigrupos: conexiones y contrastes". En CM Campbell; MR Quick; EF Robertson; GC Smith (eds.). Grupos St Andrews 2005 Volumen 2 . Prensa de la Universidad de Cambridge. pag. 376. ISBN 978-0-521-69470-4. preimpresión
- Diekert, Volker; Kufleitner, Manfred; Rosenberg, Gerhard; Hertrampf, Ulrich (2016). "Capítulo 7: Autómatas". Métodos algebraicos discretos . Berlín / Boston: Walter de Gruyther GmbH. ISBN 978-3-11-041332-8.
- Jean-Eric Pin, Fundamentos matemáticos de la teoría de los autómatas , Capítulo IV: Conjuntos racionales y reconocibles
Otras lecturas
- Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Cambridge: Cambridge University Press. Parte II: El poder del álgebra. ISBN 978-0-521-84425-3. Zbl 1188.68177 .