¿Por qué es {a^nb^n | n> = 0} no regular?

En un curso que estoy tomando CS no es un ejemplo de un lenguaje que no es regular:¿Por qué es {a^nb^n | n> = 0} no regular?

{a^nb^n | n >= 0}

Puedo entender que no es normal ya que no Autómatas de estados finitos/máquina se puede escribir y que valida acepta esta entrada ya que carece de un componente de memoria. (Corríjalo si me equivoco)

El wikipedia entry on Regular Language también enumera este ejemplo, pero no proporciona una prueba (matemática) de por qué no es regular.

¿Alguien puede aclararme sobre esto y proporcionar una prueba de esto, o señalarme un buen recurso?

Fuente

2010-02-22 Christophe Herreman

Lo que estás buscando es Pumping lemma for regular languages.

Aquí es un example con su problema exacto:

Ejemplos:
Sea L = {a ^m b ^m | m ≥ 1}.
Entonces L no es regular.
Prueba: Deje n estar como en Lem de bombeo.
Deje w = a ⁿ b ⁿ.
Deje w = xyz ser como en Lem de bombeo.
Por lo tanto, xy z ∈ L, sin embargo, xy z contiene más a's que b's.

Fuente

2010-02-22 08:53:54 cletus

Gracias, justo lo que estaba buscando. –

último reclamo necesita mejores explicaciones. La palabra x2yz contendría más letras de un tipo (si y tiene más a's que b's o viceversa), o duplicarlas rompería el orden de las letras, en donde b's debería aparecer después de todas las a. –

prueba incompleta. usted no ha definido x, y, z. x solo tiene la limitación de que | xy | <= p, donde p es la longitud de bombeo. tiene que dividir su prueba en tres casos, con cadenas y basadas en (a | ab | b) para que se completen. xy bien podría consistir en más b que a: x = a, y = b^n, z = b – oligofren

Porque no puede escribir una máquina de estados finitos que 'cuente' secuencias idénticas de símbolos 'a' y 'b'. En pocas palabras, las FSM no pueden 'contar'. Intente imaginarse un FSM: ¿cuántos estados le daría al símbolo 'a'? ¿Cuántos 'b'? ¿Qué pasa si tu secuencia de entrada tiene más?

Tenga en cuenta que si tuviera n < = X con X un valor entero, podría preparar dicho FSM (teniendo uno con un montón de estados, pero todavía un número finito); tal lenguaje sería regular.

Fuente

2010-02-22 08:56:56 lorenzog

Finite State Automaton no tiene estructura de datos (pila) - memoria como en el caso del autómata pushdown. Sí, puede darte un "a" seguido de una "b" pero no la cantidad exacta de "a" seguido de que no es "b".

Fuente

2015-02-26 06:16:25

¿Por qué es {a^nb^n | n> = 0} no regular?

Respuesta

Cuestiones relacionadas