¿Hay ejemplos de bombeo de lemas con idiomas "reales"?

Question

El pumping lemma es una propiedad de regular languages y context-free languages. Pero todos los ejemplos que he visto son cosas como:

L = {0 ^{n n n}: n ≥ 0}

(que, por cierto, es un no lenguaje sin contexto).

Pero lo que me interesa es esto: ¿hay algún ejemplo de su uso con cualquier idioma remotamente real o útil? No he podido encontrar ninguno. ¿Es esta una de esas cosas o un valor puramente teórico sin ninguna aplicación práctica?

Answer 1

L = {0 ^{n n}: n ≥ 0} ser un lenguaje libre de contexto.

coincidente paréntesis en una expresión puede ser considerada de forma semejante es decir

L = {(ⁿ) ⁿ: n ≥ 0}

Answer 2

Un uso práctico es el hecho de que todo el mundo puede dejar de intentar construir un autómata finito para reconocer la sintaxis de C# o Fortran.

Otro uso práctico es el hecho de que todos pueden dejar de intentar construir un autómata pushdown para reconocer la semántica de C# o Fortran. (Aunque en Fortran si escribe mal un nombre de variable obtiene una nueva variable gratis, la nueva variable probablemente no funcione con los operadores que codificó cuando tenía la intención de nombrar una de sus variables declaradas.)

Answer 3

"Is ¿Esta es una de esas cosas o un valor puramente teórico sin ninguna aplicación práctica?

Hrm. ¿Qué es una aplicación práctica? Sabiamente etiquetó su pregunta "ciencia de la computación". Así que supongo que la pregunta está destinado a preguntar, "¿es práctico para la informática?

En cuyo caso, la respuesta es ...

Por supuesto que lo es! Se enseña como una de las primeras formas de clasificar diferentes clases de complejidad de lenguaje, más allá de solo "big-O (whateverthehell)". Muestra que hay problemas relacionados con la computación más allá del tiempo de ejecución, en este caso que algunos modelos simplemente no pueden calcular algunas funciones. * Es bastante bajo -Introducción de pelota a las pruebas formales sobre la teoría de autómatas.

Una gran parte de la informática que la mayoría de los estudiantes de informática (mis pares) parecen Intenta evitar es la Teoría de la Computación, una clasificación a la que los lemmas de bombeo obviamente recaen.

El hecho, afortunadamente obvio, es que la teoría de la computación, le guste o no, es fundamental para la informática. Para no captar la idea de las diferentes clases de complejidad (la gran O por sí misma realmente no funciona) no deletreará la muerte del científico informático, pero ocultará una parte considerable del campo de su vista.

* Sí, generalmente el problema de detención se muestra como el primero, pero nunca lo consiguen la primera vez.

En cuanto a la interpretación más cínica de su pregunta, en la que quiere decir "¿alguna pieza de software realmente usa esto?", Mi respuesta es por supuesto que no. Es parte de la base de la computación, no de sus aplicaciones. Esto no es para sonar desdeñoso de sus aplicaciones, en absoluto. Ambos son de valor igual, noble.

Answer 4

este programa Python es válida:

print ((((((((((((((((((((((((1)))))))))))))))))))))))) 

, así como todas las demás declaraciones equivalentes con una cantidad igual de ( a la izquierda y ) en el lado derecho.

No puede compilar una expresión regular para verificar eso, por lo tanto, debe usar un analizador.

No es para nada teórico. Es la razón por la cual no puede usar expresiones regulares para analizar HTML.