En informática , más precisamente en la teoría de autómatas , un conjunto racional de un monoide es un elemento de la clase mínima de subconjuntos de este monoide que contiene todos los subconjuntos finitos y está cerrado bajo unión , producto y estrella de Kleene . Los conjuntos racionales son útiles en teoría de autómatas , lenguajes formales y álgebra .
Un conjunto racional generaliza la noción de lenguaje racional (regular) (entendido como definido por expresiones regulares ) a monoides que no son necesariamente libres . [ ejemplo necesario ]
Definición
Dejar ser un monoide con elemento de identidad. El conjunto de subconjuntos racionales de es el conjunto más pequeño que contiene todos los conjuntos finitos y está cerrado bajo
- unión : si luego
- producto: si luego
- Estrella de Kleene : si luego dónde es el singleton que contiene el elemento de identidad, y donde .
Esto significa que cualquier subconjunto racional de puede obtenerse tomando un número finito de subconjuntos finitos de y aplicar las operaciones de unión, producto y estrella de Kleene un número finito de veces.
En general, un subconjunto racional de un monoide no es un submonoide.
Ejemplo
Dejar ser un alfabeto , el conjunto de palabras terminadas es un monoide. El subconjunto racional deson precisamente los lenguajes habituales . De hecho, los lenguajes regulares pueden definirse mediante una expresión regular finita .
Los subconjuntos racionales de son los últimos conjuntos periódicos de números enteros. De manera más general, los subconjuntos racionales deson los conjuntos semilineales . [1]
Propiedades
El teorema de McKnight establece que sise genera finitamente, entonces su subconjunto reconocible son conjuntos racionales. Esto no es cierto en general, ya que todo el es siempre reconocible pero no es racional si se genera infinitamente.
Los conjuntos racionales se cierran bajo el morfismo: dado y dos monoides y un morfismo, si luego .
no está cerrado bajo complemento como muestra el siguiente ejemplo. [2] Deja, los conjuntos y son racionales pero no es porque su proyección al segundo elemento no es racional.
La intersección de un subconjunto racional y de un subconjunto reconocible es racional.
Para grupos finitos el siguiente resultado de A. Anissimov y AW 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. [3]
Relaciones racionales y funciones racionales
Una relación binaria entre los monoides M y N es una relación racional si la gráfica de la relación, considerada como un subconjunto de M × N, es un conjunto racional en el producto monoide. Una función de M a N es una función racional si la gráfica de la función es un conjunto racional. [4]
Ver también
Referencias
- 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-Éric Pin , Fundamentos matemáticos de la teoría de los autómatas , Capítulo IV: Conjuntos racionales y reconocibles
- Samuel Eilenberg y MP Schützenberger , Conjuntos racionales en monoides conmutativos , Journal of Algebra, 1969.
- ^ Fundamentos matemáticos de la teoría de los autómatas
- ^ cf. Jean-Eric Pin, Fundamentos matemáticos de la teoría de los autómatas , p. 76, ejemplo 1.3
- ^ 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
- ^ Hoffmann, Michael; Kuske, Dietrich; Otto, Friedrich; Thomas, Richard M. (2002). "Algunos familiares de grupos automáticos e hiperbólicos". En Gomes, Gracinda MS (ed.). Semigrupos, algoritmos, autómatas y lenguajes. Actas de los talleres realizados en el Centro Internacional de Matemáticas, CIM, Coimbra, Portugal, mayo, junio y julio de 2001 . Singapur: World Scientific. págs. 379–406. Zbl 1031.20047 .
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 .