Problema no resuelto en la teoría del lenguaje formal
Problema sin resolver en informática :
¿Pueden todos
los lenguajes regulares expresarse utilizando expresiones regulares generalizadas con una profundidad de anidamiento limitada de
estrellas Kleene ?
El problema generalizado de la altura de las estrellas en la teoría de lenguajes formales es la cuestión abierta de si todos los lenguajes regulares pueden expresarse utilizando expresiones regulares generalizadas con una profundidad de anidamiento limitada de estrellas de Kleene . Aquí, las expresiones regulares generalizadas se definen como expresiones regulares , pero tienen un operador de complemento incorporado. Para un lenguaje regular, su altura de estrella generalizada se define como la profundidad de anidamiento mínima de estrellas de Kleene necesaria para describir el lenguaje por medio de una expresión regular generalizada, de ahí el nombre del problema.
Más específicamente, es una pregunta abierta si se requiere una profundidad de anidamiento de más de 1 y, de ser así, si existe un algoritmo para determinar la altura de estrella mínima requerida. [1]
Los lenguajes regulares de altura de estrella 0 también se conocen como lenguajes sin estrellas . El teorema de Schützenberger proporciona una caracterización algebraica de los lenguajes sin estrellas mediante monoides sintácticos aperiódicos . En particular, los lenguajes sin estrellas son una subclase decidible propia de los lenguajes regulares.
Véase también
Referencias
- ^ Sakarovitch (2009) pág. 171
- Janusz A. Brzozowski (1980). "Problemas abiertos sobre lenguajes regulares". En Ronald V. Book (ed.). Teoría del lenguaje formal: perspectivas y problemas abiertos . Academic Press. págs. 23–47.
- Wolfgang Thomas (1981). "Observación sobre el problema de la altura de las estrellas". Ciencias Informáticas Teóricas . 13 (2): 231–237. doi : 10.1016/0304-3975(81)90041-4 . MR 0594062.
- Jean-Eric Pin; Howard Straubing; Denis Thérien (1992). "Algunos resultados sobre el problema generalizado de la altura de las estrellas" (PDF) . Información y Computación . 101 (2): 219–250. doi :10.1016/0890-5401(92)90063-L.
- Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Cambridge: Cambridge University Press . ISBN 978-0-521-84425-3.Zbl 1188.68177 .
- Marcel-Paul Schützenberger (1965). "Sobre monoides finitos que tienen sólo subgrupos triviales". Información y Control . 8 (2): 190–194. doi : 10.1016/S0019-9958(65)90108-7 . Zbl 0131.02001.
Enlaces externos
- Jean-Eric Pin: El problema de la altura de las estrellas
