Una condición suficiente y necesaria sobre la regularidad de un idioma.

¿Cuál de las siguientes afirmaciones es correcta?

1. existen condiciones suficientes y necesarias sobre la regularidad de un idioma pero aún no se han descubierto.

2. No hay una condición suficiente y necesaria sobre la regularidad de un idioma.

3. El lema de bombeo es una condición necesaria para la no regularidad de un idioma.

4. El lema de bombeo es una condición suficiente para la no regularidad de un idioma.

Sé que # (4) es correcto y # (3) es falso porque "lo contrario de esta afirmación no es cierto: un lenguaje que satisfaga estas condiciones aún puede ser no regular", pero lo que se puede decir sobre (1) y (2)?

Aquí hay algunas condiciones necesarias y suficientes para que un idioma sea regular.

Teorema. Deje . Las siguientes condiciones son equivalentes:$L\subseteq\Sigma^*$

• $L$ es generado por una expresión regular (es decir, la definición de lenguaje regular).
• $L$ es reconocido por un autómata finito no determinista ( Kleene ).
• $L$ es reconocido por un autómata finito no determinista sin transiciones de .$\varepsilon$
• $L$ es reconocido por un autómata finito determinista ( Scott y Rabin ).
• ( N , Σ , P , S ) N Σ $L$ es generado por una gramática , donde es un subconjunto finito de ( Frazier y Page ).$(N,\Sigma,P,S)$$N$$\Sigma^*$
• $L$ es generado por una gramática libre de contexto izquierda (respectivamente derecha).
• El índice de la relación de Nerode es finito (Anil Nerode, Transformaciones de autómatas lineales , 1958). Esto se conoce ampliamente (e incorrectamente) como el teorema de Myhill-Nerode. ≡ L es la relación utilizada para construir el DFA mínimo de un lenguaje normal.$\equiv_L$$\equiv_L$
• $\sim_L$$\sim_L$
• $L$$\sim_L$$L$
• $L$
• $L$

Si un lenguaje no no satisface las condiciones del lema de bombeo para lenguajes regulares , entonces es no regular. Esto significa que el bombeo de lema es una condición suficiente para la falta de regularidad de un idioma.

En resumen, las declaraciones 1, 2 y 3 son falsas, mientras que la declaración 4 es verdadera, como usted mencionó.

Es suficiente (y necesario) mostrar la existencia de un DFA, NFA o expresión regular para demostrar que un lenguaje es regular, lo que refuta (1) y (2). Para mostrar que un idioma no es regular, es necesario mostrar que no existe una expresión DFA, NFA o regular.

El lema de bombeo es una herramienta útil para mostrar (posiblemente por contradicción) que un lenguaje no es regular, al mostrar que no existe DFA.

$L$$L$

Sin embargo, esta condición no hace que sea fácil demostrar la falta de regularidad de un idioma. No conozco ninguna condición que sea fácil de verificar que siempre demuestre la no regularidad de un lenguaje no regular.

Hay dos 'pruebas' más que pueden demostrar la falta de regularidad de un idioma (aunque pueden no funcionar): puede intentar dar un lenguaje regular de modo que su unión / intersección / diferencia / concatenación / cociente no sea regular ( hay más operaciones como esta), y puede intentar contar cuántas palabras genera y verificar si contradice la expresión para la cantidad de palabras en un idioma normal (como se puede encontrar en la página de Wikipedia que ha vinculado).

Existe esta maravillosa conexión entre la teoría del lenguaje formal y las series de poder formal probadas por Chomsky y Schützenberger [CS63] . En la forma encontrada en [SS78] Cap. II, teorema 5.1

$L$$\mathbb{K}$$\mathrm{char}(L)$$\mathbb{K}$

$\mathrm{char}(L)$

[SS78] Arto Salomaa y Matti Soittola. Aspectos teóricos de autómatas de la serie de energía formal. Springer-Verlag, Nueva York, 1978.

[CS63] Noam Chomsky y Marcel P. Schützenberger. La teoría algebraica de los lenguajes libres de contexto. En P. Braffort y D. Hirschberg, editores, Programación informática y lenguajes formales, páginas 118–161. Holanda Septentrional, 1963.

$I_{L}$$x$$y$$x I_{L} y$

1. $z_{x}$$xz_{x} \in L$$yz_{x} \in L$
2. $z_{y}$$yz_{y} \in L$$xz_{y} \in L$

$I_{L}$$L$

$I_{L}$