Regular los idiomas y el lema de bombeo

Question

En ciertos rincones oscuros de la informática y la teoría de grupos, a menudo se quiere demostrar que un lenguaje no es un lenguaje regular (es decir, un lenguaje aceptado por un autómata de estado finito).

La única técnica en general sé que para hacer esto es el llamado "lema de bombeo", que dice que si L es un lenguaje regular, entonces existe algún n>0 con la siguiente propiedad. Si w es una palabra en L de longitud al menos n, entonces podemos escribir w=xyz (aquí x, y, y z son subpalabras) tales que y es trivial y xy^{k}z es un elemento de L para todo k>0.

Este lema básicamente refleja el hecho trivial de que en cualquier grafo dirigido, hay algunos n tal que cualquier camino de longitud al menos n contiene un bucle.

Pregunta: ¿existen otras técnicas generales para demostrar que un lenguaje no es regular?

Answer 1

Sea L_n será el número de palabras en L de longitud n. Si la suma L_n x^n no es una función racional, entonces L no puede ser regular. Ver la prueba en los comentarios.

Answer 2

Para condiciones necesarias y suficientes para que un lenguaje sea regular (a veces útil en la demostración de nonregularity cuando los trucos más simples, como el lema de bombeo fallar) ver la Myhill–Nerode teorema.

Answer 3

El habitual lema de bombeo sólo da una condición necesaria para que un lenguaje sea regular, pero hay más versiones más potentes de dar condiciones necesarias y suficientes, el uso de "bloque de bombeo propiedades".

A. Ehrenfeucht, R. Parikh, y G. Rozenberg, el Bombeo de los lemas para regular conjuntos, SIAM J. Comput. 10 (1981), 536-541.

S. Varricchio, Una de Bombeo de la Condición de Regular Conjuntos, SIAM J. Comput. 26 (1997), 764-771.

A. de Luca y S. Varricchio, la Finitud y la Regularidad en Semigroups y Lenguajes Formales (Monografías de la informática Teórica. Un EATCS de la Serie), Springer, 1999.
ISBN: 978-3-540-63771-4 (Impresión) 978-3-642-59849-4 (en Línea)

Answer 4

El siguiente lema, que vi en algunos libros antiguos, puede manejar la mayoría de los ejemplos de libro de bombeo lema de uso y normalmente es mucho más fácil de aplicar cuando se aplica. Deje $L$ ser un idioma, y supongamos que hay cadenas de $\alpha_1,\alpha_2,\ldots $ $\beta_1,\beta_2,\ldots$ con la propiedad de que $\alpha_i\beta_j\in L$ fib $i=j$. A continuación, $L$ no es regular (fácil la prueba utilizando un DFA).

Tenga en cuenta que el $\alpha$s y $\beta$s son sólo cadenas, ellos no necesitan estar en $L$ y generalmente no lo son.

Ejemplos:

1. $\alpha_k:=a^k$ $\beta_k:=b^k$ muestra $\lbrace a^kb^k : k\ge 0\rbrace$ no es regular.
2. $\alpha_k:=a^k$ $\beta_k:=ba^k$ muestra el conjunto de palíndromos no es regular.
3. $\alpha_k:=ba^k$ $\beta_k:=ba^k$ muestra $\lbrace ww : w\in\Sigma^*\rbrace$ no es regular.

Answer 5

Algunas variantes del lema de bombeo son completos para determinar si un lenguaje L es regular. Por ejemplo, considere esta partida de dos jugadores:

El jugador 1 elige un entero positivo k. El jugador 2 elige una cadena w de longitud k. El jugador 1 elige una cadena de partición w=abc, con b no vacíos. Jugador 2 selecciones z así que exactamente uno de {wz, zac} es L. El último jugador en un movimiento válido gana.

Entonces L es regular si el Jugador 1 tiene una estrategia ganadora. De esta forma, se Myhill-Nerode, como se mencionó anteriormente. Para un ejemplo similar, ver Jaffe.