¿Se pueden expresar todos los lenguajes regulares utilizando expresiones regulares generalizadas con una profundidad de anidación limitada de estrellas de Kleene ?
El problema generalizado de la altura de las estrellas en la teoría del lenguaje formal es la cuestión abierta de si todos los lenguajes regulares pueden expresarse utilizando expresiones regulares generalizadas con una profundidad de anidación 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 mínima de anidación de las estrellas de Kleene necesaria para describir el lenguaje mediante 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 anidación de más de 1 y, de ser así, si existe un algoritmo para determinar la altura mínima requerida de la estrella. [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 lenguajes sin estrellas mediante monoides sintácticos aperiódicos . En particular, los lenguajes sin estrellas son una subclase propiamente decidible de los lenguajes regulares.
Ver también
- Teorema de Eggan y secciones de altura de estrella generalizada del artículo de altura de estrella
- Problema de altura de estrella
Referencias
- ↑ Sakarovitch (2009) p.171
- Janusz A. Brzozowski (1980). "Problemas abiertos sobre lenguajes regulares". En Ronald V. Book (ed.). Teoría del lenguaje formal: perspectivas y problemas abiertos . Prensa académica. págs. 23–47.
- Wolfgang Thomas (1981). "Comentario sobre el problema de la altura de las estrellas". Informática Teórica . 13 (2): 231–237. doi : 10.1016 / 0304-3975 (81) 90041-4 . Señor 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 .