Pensé que todos los idiomas regulares podrían expresarse con expresiones regulares (si un idioma es regular, puede expresarse con expresiones regulares), pero me han dicho que necesita las tres operaciones regulares (concatenación, unión y estrella) para eso sostener.
Por ejemplo, me han dicho que si solo puedo usar las operaciones de expresión regular de unión y concatenación (2 de las 3), habría un lenguaje regular que no puedo describir con solo esos dos.
Lo mismo con solo Kleene Star y Union. ¿Cuáles son algunos ejemplos de esto?
formal-languages
regular-languages
regular-expressions
kleene-star
usuario3295674
fuente
fuente
fuente
Si ahora se permite usar estrellas, pero no estrellas anidadas , entonces es un problema abierto (durante al menos 45 años) saber si se pueden obtener todos los idiomas habituales. Esta pregunta se conoce como el problema generalizado de la altura de la estrella . Es similar al problema de la altura de la estrella mencionado por Yuval Filmus, con la diferencia de que ahora se permite la complementación.
fuente