¿Cuáles son los posibles conjuntos de longitudes de palabras en un idioma normal?

15

Dado un lenguaje , defina el conjunto de longitud de L como el conjunto de longitudes de palabras en L : L S ( L ) = { | u | u L }LLL

LS(L)={|u|uL}

¿Qué conjuntos de enteros pueden ser el conjunto de longitud de un lenguaje normal?

Gilles 'SO- deja de ser malvado'
fuente

Respuestas:

14

Primero, una observación que no es crucial pero conveniente: el conjunto S de conjuntos de enteros que son LS(L) para algún lenguaje regular L en un alfabeto no vacío A no depende de la elección del alfabeto. Para ver eso, considere un autómata finito que reconoce L ; Las longitudes de las palabras que están en L son las longitudes de las rutas en el autómata visto como un gráfico sin etiquetar desde el estado inicial hasta cualquier estado de aceptación. En particular, se puede etiquetar cada flecha a a y obtener un lenguaje regular con el mismo conjunto longitud sobre el alfabeto {a} . Por el contrario, siL es un lenguaje regular sobre un alfabeto de un elemento, se puede inyectar trivialmente en un alfabeto más grande, y el resultado sigue siendo un lenguaje regular.

Por lo tanto, estamos buscando los conjuntos de longitud posibles para las palabras sobre un alfabeto singleton. En un alfabeto singleton, el idioma es la longitud establecida en unario: LS(L)={nNanL} . Tales lenguas se llaman lenguas unarias.

Deje que L sea un lenguaje regular, y considerar un autómata finito determinista (DFA) que reconoce L . El conjunto de longitudes de palabras de L es el conjunto de longitudes de rutas en el DFA visto como un gráfico dirigido que comienza en el estado de inicio y termina en uno de los estados de aceptación. Un DFA en un alfabeto de un elemento es bastante manso (los NFA serían más salvajes): es una lista finita o una lista circular. Si la lista es finita, numere los estados de 0 a h siguiendo el orden de la lista; si es circular, numere los estados de 0 a h siguiendo el encabezado de la lista, y de h a h+r largo del ciclo.

autómatas en forma de lista

Sea F el conjunto de índices de estados de aceptación hasta h , y G el conjunto de índices de estados de aceptación de h a h+r . Luego

LS(L)=F{kr+xxG,kN}

Por el contrario, supongamos que h y r son dos enteros y F y G son dos conjuntos finitos de enteros de manera que xF,xh y xG,hxh+r . Entonces el conjunto LF,G,r={akr+xxG,kN}es un lenguaje regular: es el idioma reconocido por el DFA descrito anteriormente. Una expresión regular que describe este lenguaje esaFaG(ar) .

Para resumir en inglés, los conjuntos de longitud de los idiomas regulares son los conjuntos de enteros que son periódicos¹ por encima de un cierto valor .

¹ Para aferrarse a una noción bien establecida , periódico significa la función característica del conjunto (que es una función N{false,true} que elevamos a una función Z{false,true} ) es periódico. Periódico por encima de cierto valor significa que la función está restringida a [h,+[ puede prolongarse en una función periódica.

Gilles 'SO- deja de ser malvado'
fuente
Su observación sobre la irrelevancia del alfabeto sugiere que se puede aplicar el teorema de Parikh. Específicamente, muestra que LS (L) = LS (L ') donde en L' todas las letras se contraen en un solo alfabeto. Pero LS (L ') es el mapeo de Parikh del lenguaje L, que se sabe que es semilineal para cualquier lenguaje regular.
Suresh
Buen enfoque! 1) Creo que el primer párrafo se puede reemplazar con la observación de que los lenguajes regulares están cerrados contra los homomorfismos de cuerdas. 2) Para mayor claridad, debe considerar dar la segunda parte de como { h + k r + ( x - h ) ... } , módulo off-by-one-errors. 3) ¿Qué es un conjunto de "enteros" periódico? LS(L){h+kr+(xh)}
Raphael
1
@Suresh, Raphael (1): Prefiero exponer la prueba de manera elemental, ni los homomorfismos ni las asignaciones de Parikh se mencionaron en mi clase CS 102.
Gilles 'SO- deja de ser malvado'
@Raphael (2) Donde empiezas a indexar no importa, podría eliminar la condición h G , ya que F puede absorber tantos elementos pequeños como queramos. (3) Un conjunto que es periódico por encima de un cierto valor es uno que se puede poner en el formulario que se muestra arriba. solhsolF
Gilles 'SO- deja de ser malvado'
5

Cualquier subconjunto finito puede ser el conjunto de longitud de un lenguaje regular L , ya que puede tomar un alfabeto unario { 0 } y definir L como { 0 1 , ... , 0 n } (esto incluye el idioma vacío y { ε } ).{1,,n}NL{0}L{01,,0n}{ε}

Ahora para los conjuntos infinitos. Daré un breve análisis, aunque la respuesta final podría no ser lo suficientemente explícita. No daré más detalles a menos que me lo pidas, porque creo que es intuitivo y porque no tengo mucho tiempo ahora.

Sean expresiones regulares que generan lenguajes L 1 y L 2 , respectivamente. Es (más o menos) fácil ver quer1,r2L1L2

  • .LS(L(r1+r2))=LS(L1L2)=LS(L1)LS(L2)
  • . Esto se denota L S ( L 1 ) + L S ( LLS(L(r1r2))=LS(L1L2)={1+2:1LS(L1),2LS(L2)} .LS(L1)+LS(L2)
  • LS(L(r1))={0}n1{i=1ni:(1,,n)(LS(L1))n}.

Por lo tanto, los posibles conjuntos de enteros que pueden ser el conjunto de longitud de un lenguaje regular son los que son subconjuntos finitos de o que se pueden construir tomando los subconjuntos finitos S 1 , S 2 de N y usando las fórmulas anteriores un finito numero de veces.NS1,S2N

Aquí, estamos usando que los lenguajes regulares se construyen, por definición, aplicando las reglas para construir una expresión regular un número finito de veces. Tenga en cuenta que podemos comenzar con cualquier subconjunto finito de , aunque en las expresiones regulares comenzamos con palabras de longitud 0 y 1 solo como el caso base. Esto se justifica fácilmente por el hecho de que todas las palabras (finitas) son concatenaciones (finitas) de los símbolos del alfabeto.N

Janoma
fuente
No veo ninguna respuesta final. (¿Tenía la intención de terminar su respuesta más tarde?) Esperaba una descripción simple de los posibles conjuntos y una conexión con autómatas.
Gilles 'SO- deja de ser malvado'
La respuesta final está ahí: "Por lo tanto, los posibles conjuntos de enteros ...". De hecho, es una descripción simple, aunque está conectada con expresiones regulares, no con autómatas.
Janoma
Hay una descripción más simple que no implica tomar un punto de fijación. ¡Quizás esta pregunta no sea tan elemental como pensaba!
Gilles 'SO- deja de ser malvado'
No creo que pueda evitar la última regla, ya que es el operador estrella el que puede producir conjuntos de longitud infinitos, al igual que produce lenguajes infinitos.
Janoma
@Gilles ¿Entonces quiere una forma cerrada del punto de fijación más pequeño de la solución inductiva que proporciona Janoma?
Raphael
2

De acuerdo con el lema de bombeo para lenguajes regulares, existe una tal que una cadena x de longitud al menos igual a n se puede escribir de la siguiente forma: x = u v w Donde se cumplen las siguientes tres condiciones: | u v | < n | v | > 0 u v k w Lnxn

x=uvw
|uv|<n
|v|>0
uvkwL

Esto nos da una prueba para los conjuntos: un conjunto no puede ser el conjunto de longitud de un lenguaje normal a menos que todos sus elementos se puedan expresar como un conjunto arbitrario de enteros no mayor que un fijo , más algún múltiplo de un valor indeterminado m (la longitud de v ), más algún valor finito arbitrario.nmv

En otras palabras, parece que los posibles conjuntos de longitudes de lenguaje para los idiomas regulares es el cierre con respecto a la unión de conjuntos (como se discutió en EDIT y EDIT2, gracias a los comentaristas) de conjuntos descritos como sigue: Para a , b N fijos y todos los conjuntos finitos S , por el lema de bombeo para los idiomas regulares (gracias a Gilles por señalar un error tonto en mi versión original, por el cual estaba definiendo el conjunto N ).

{a+bn|nN}S
a,bNSN

EDITAR: Un poco más de discusión. Ciertamente, todos los conjuntos finitos de enteros son conjuntos de longitud. Además, la unión de dos conjuntos de longitud también debe ser un conjunto de longitud, como debe ser el complemento de cualquier conjunto de longitud (por lo tanto, intersección, por lo tanto, diferencia). La razón de esto es que los idiomas regulares están cerrados bajo estas operaciones. Por lo tanto, la respuesta que doy arriba es (posiblemente) incompleta; en realidad, cualquier unión de tales conjuntos es también el conjunto de longitud de algún lenguaje regular (tenga en cuenta que he abandonado la necesidad de intersección, complemento, diferencia, etc., ya que estos están cubiertos por el hecho de que los idiomas regulares están cerrados bajo estas propiedades, como discutido en EDIT3; creo que solo la unión es realmente necesaria, incluso si los otros tienen razón, lo que podría no ser el caso).

EDIT2: Aún más discusión. La respuesta que doy es básicamente donde terminarías si llevaras la respuesta de Janoma un poco más lejos; la parte proviene de la estrella de Kleene, la a proviene de la concatenación, y la discusión sobre unión, intersección, diferencia y complemento proviene del + de las expresiones regulares (así como otras propiedades de cierre de los lenguajes regulares) demostrables a partir de autómatas) .bna

EDITAR3: a la luz del comentario de Janoma, olvidemos las propiedades de cierre de los conjuntos de longitud del lenguaje que analizo en la primera EDICIÓN. Dado que los idiomas regulares tienen estas propiedades de cierre, y dado que cada idioma regular tiene un DFA, se deduce que el lema de bombeo para los idiomas regulares se aplica a todas las uniones, intersecciones, complementos y diferencias de los idiomas regulares, y lo dejaremos así. ; ni siquiera es necesario considerar ninguno de estos, excepto la unión, que todavía creo que podría ser necesario para hacer que mi original (modificado, gracias a los aportes de Gilles) sea correcto. Entonces, mi respuesta final es esta: lo que digo en la versión original, más el cierre de los conjuntos de longitud de lenguaje con respecto a la unión de conjuntos.

Patrick87
fuente
1
está en el camino correcto, pero usted tiene un cuantificador algún lugar equivocado, se está generando N . {a+bna,b,nN}SN
Gilles 'SO- deja de ser malvado'
1
L=L(a)Σ={a,b}LNL¯N+
@Gilles Pero el conjunto de todos los números naturales es un conjunto de longitud válido, ¿verdad? No estoy generando todos los subconjuntos de números naturales, ¿verdad? Estoy de acuerdo en que sería problemático. Editar: oh espera, veo lo que estás diciendo. Sí tienes razón. Se solucionará cuando vuelva a la computadora.
Patrick87
@Janoma Excelente punto, tendrá que considerar cómo eso podría cambiar el conjunto de cosas que estoy definiendo ...
Patrick87