Me preguntaba, ya que es en sí mismo un lenguaje sin estrellas, ¿existe un lenguaje normal que no sea un idioma sin estrellas? ¿Podrías dar un ejemplo?
(de wikipdia ) Lawson define lenguajes sin estrellas como:
Se dice que un lenguaje regular no tiene estrellas si puede describirse mediante una expresión regular construida a partir de las letras del alfabeto, el símbolo de conjunto vacío, todos los operadores booleanos, incluida la complementación, y la concatenación, pero no la estrella de Kleene.
Aquí está la prueba de ser libre de estrella:
está libre de estrellas
está libre de estrellas
Si entonces está libre de estrellas
Si entonces es sin estrellas
formal-languages
regular-languages
automata
Intitulado
fuente
fuente
Respuestas:
Los lenguajes regulares son aquellos que pueden describirse mediante una lógica monádica de segundo orden débil (WMSO) [1].
fuente
Schützenberger (1965) dio una caracterización algebraica de los lenguajes libres de estrellas: un lenguaje regular está libre de estrellas si y solo si su monoide sintáctico es aperiódico. Contrariamente a la caracterización lógica (sin estrellas = FO [<]), esta caracterización algebraica proporciona un algoritmo para decidir si un lenguaje regular dado está libre de estrellas (el lenguaje regular puede ser dado por un autómata finito, una expresión regular o un gramática regular). Usando la caracterización lógica (debido a McNaughton y Papert), uno puede decidir el siguiente problema: dada una fórmula WMSO, ¿hay una fórmula FO que describa el mismo lenguaje?
M.-P. Schützenberger, Sobre monoides finitos que tienen solo subgrupos triviales, Información y Control 8 (1965), 190-194.
R. ~ McNaughton y S. ~ Papert, Autómatas sin mostrador, The MIT Press, Cambridge, Massachusetts, Londres, 1971.
Se puede encontrar una prueba completa del teorema de Schützenberger en varios libros de texto o en encuestas. Para una presentación elemental del algoritmo correspondiente (sin una prueba), vea
J.-É. Pin, semigrupos finitos e idiomas reconocibles: una introducción, en Semigrupos del Instituto de Estudios Avanzados de la OTAN, Idiomas y grupos formales , J. Fountain (éd.), 1-32, Editores académicos de Kluwer, (1995).
fuente
Los lenguajes libres de estrellas se describen mediante expresiones regulares que incluyen concatenación, complementación, unión, intersección, pero no Kleene-star.
Dado que los idiomas regulares están cerrados en todas estas operaciones (donde la complementación es el punto crucial), entonces cada lenguaje sin estrellas también es regular.
¿Quizás te refieres a lo contrario? ¿Están todos los idiomas normales sin estrellas? La respuesta a esto último es no. Vea este documento para más detalles.
fuente
Un ejemplo de separación simple es (aa) *. Más sofisticado: todas las cadenas binarias con paridad par (o impar).
fuente