Siempre hay un AFN sin lambda-movimientos que reconoce el lenguaje L, pero no siempre existe una expresión regular que denota al lenguaje L.

No siempre existe un AFD que reconozca el lenguaje L.

Siempre hay un AFN sin lambda-movimientos que reconoce el lenguaje L, pero no siempre existe un AFD que reconoce L.

Siempre hay una expresión regular que denota al lenguaje L.

Si tomamos , se observa que para , no pertenece a para cualquier elección de , y de acuerdo al enunciado del lema de pumping, lo que demuestra la no regularidad de .

Se trata de un lenguaje regular que verifica el lema de pumping.

Si tomamos , se observa que para , no pertenece a para cualquier elección de , y de acuerdo al enunciado del lema de pumping, lo que demuestra la no regularidad de .

Si tomamos , no existe ningún que demuestre la no regularidad de .

8 estados

7 estados

5 estados

6 estados

{q1}

{q1,q3}

{q1,q2}

{q1,q2,q3}

Dos.

Cuatro.

Tres.

Cinco.

lq=(a+b)lq  lq=(a+b)*

lq=(a+b)lq+λ  lq=(a+b)

lq=(a+b)lp+b lq=(a+b)*b

lq=(a+b)lq+b  lq=(a+b)*b

(aa+ab+ba)* (a+b)

(a+ba)* (b+λ)

(aa+ab+ba)*

(a+ab)*

Cinco

Seis

Cuatro

Tres

Palabras que tienen el doble de b's que de a's.

Palabras que comienzan con cualquier número de a's, y después tienen un número par de b's.

Palabras formadas repitiendo la cadena "abb" cualquier numero de veces.

Palabras en las que las b's que haya aparecen siempre en grupos con un número par de ellas.