Lenguaje libre de estrellas versus lenguaje regular

11

Me preguntaba, ya que a 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 a ser libre de estrella:

está libre de estrellas
Σ=¯ está libre de estrellas
SiAΣ entoncesΣAΣ está libre de estrellas
SiAΣ entoncesA=Σ(ΣA)Σ¯ es sin estrellas

A=Σ(ΣA)Σ¯AΣA

Intitulado
fuente
AΣAΣ
A
@reinierpost Edité la publicación para que sea más fácil de leer. Gracias por la respuesta.
Sin título el
¡Gracias! Difícil de perder ahora.
reinierpost

Respuestas:

11

Los lenguajes regulares son aquellos que pueden describirse mediante una lógica monádica de segundo orden débil (WMSO) [1].

<

(aa)


  1. Débitos aritméticos de segundo orden y autómatas finitos de Büchi (1960)
  2. Autómatas sin mostrador de McNaughton y Papert (1971)
  3. (aa)

     [x.Pa(x)][x.Pa(x)[X.X(0)[x,y.X(x)suc(x,y)¬X(y)][x,y.¬X(x)suc(x,y)X(y)][x.last(x)¬X(x)]]].

    X

  4. Ver también aquí .
Rafael
fuente
Sé lo que es "monádico" en la lógica. ¿Sabes cuál es la restricción "débil"?
Hendrik Jan
1
ω
14

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).

J.-E. Alfiler
fuente
7

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.

Shaull
fuente
Sí, quise decir lo contrario, edité la pregunta.
Sin título
1

Un ejemplo de separación simple es (aa) *. Más sofisticado: todas las cadenas binarias con paridad par (o impar).

Holger Petersen
fuente
1
¿Qué agrega esto sobre la respuesta aceptada?
Raphael
@Raphael El ejemplo de paridad. Aunque sería bueno si Holger explicara por qué no está libre de estrellas.
David Richerby