Problema no resuelto en la teoría del lenguaje formal.
Problema no resuelto en informática :
¿Se pueden expresar todos
los lenguajes regulares utilizando expresiones regulares generalizadas con una profundidad de anidación limitada de
estrellas 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, la altura generalizada de su estrella se define como la profundidad mínima de anidación de estrellas Kleene necesaria para describir el lenguaje mediante una expresión regular generalizada, de ahí el nombre del problema.
Más específicamente, es una cuestión 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 con altura de estrella 0 también se conocen como lenguajes sin estrellas . El teorema de Schützenberger proporciona una caracterización algebraica de las lenguas sin estrellas mediante monoides sintácticos aperiódicos . En particular, los lenguajes sin estrellas son una subclase adecuada y decidible de lenguajes regulares.
Ver también
Referencias
- ^ Sakarovich (2009) p.171
- Janusz A. Brzozowski (1980). "Problemas abiertos sobre lenguajes regulares". En Ronald V. Libro (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.
- Sakarovich, Jacques (2009). Elementos de la teoría de los autómatas . Traducido del francés por Reuben Thomas. Cambridge: Prensa de la Universidad de Cambridge . 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
