Diferencia entre lenguas regulares y no regulares

Question

No entiendo la diferencia, en clases he visto el lema de bombeo para lenguajes regulares y se como aplicarlo para demostrar si un lenguaje es regular o no, pero siento que no entiendo el significado de fondo del mismo.... Por ejemplo:

$(0^*1^*)$ es un lenguaje regular definido por una expresión regular, mientras que el lenguaje definido por $\{0^n1^n, n \geq 0\}$ no lo es, pero al fin y al cabo, ¿no representan el mismo conjunto de cadenas?, para mí, cualquier cadena con $0$ o más ceros, seguido de $0$ o más deben pertenecer a ambas lenguas.

Answer 1

Un lenguaje regular es aquel que puede ser reconocido por una máquina finita, es decir, por un ordenador con una cantidad finita de memoria.

$\mathtt 0^*\mathtt 1^*$ es la familia de cadenas que tienen algunos ceros seguidos de algunos unos. Supongamos que tuviéramos una cadena de mil millones de símbolos y tuviéramos que decidir si tiene esta forma. Podrías hacerlo sin apenas memoria: sólo tienes que escanear la cadena de izquierda a derecha, y llevar la cuenta de si has visto un $\mathtt 1$ todavía. Si lo hubieras hecho, y luego vieras un $\mathtt 0$ podrías detenerte y decir "¡No! Forma equivocada". Si llegabas al final de la cadena antes de que eso ocurriera, podías decir "¡Sí!". Acertarías siempre, y lo único que tendrías que recordar sería "¿He visto alguna ${\mathtt 1}$ s todavía?"

Pero $\{\mathtt 0^n\mathtt 1^n\mid n\ge 0\}$ es la familia de cadenas que tienen algunos ceros seguidos de exactamente el mismo número de unos. Si tuvieras una cadena de mil millones de símbolos y quisieras decidir si tiene esta forma, la única manera sería cuente el número de ceros y luego compararlo con el número de unos. Y si sólo tuvieras una cantidad finita de memoria, habría algún número de ceros tan grande que no tendrías memoria suficiente para recordarlo. Si la cadena fuera demasiado larga, perderías la cuenta y obtendrías una respuesta errónea.

(El lema de bombeo demuestra que $\{\mathtt 0^n\mathtt 1^n\mid n\ge 0\}$ no es regular es una formalización precisa de la afirmación de que, si la cadena fuera lo suficientemente larga, perderías la cuenta y obtendrías la respuesta incorrecta).