Así en frío, de forma algebráica no sabría decirte, pero nuestro profesor nos enseñó un método muy sencillo por el que reconocer casi a golpe de vista el tipo de lenguaje que era.
Es un sistema de pilas que funciona de la siguiente forma:
Un lenguaje regular no necesita ninguna pila para ser aceptado.
Un lenguaje irregular necesita alguna pila para ser aceptado.
¿Qué es esto de las pilas? Creo que con un par de ejemplos te lo imaginarás mejor:
L = {a^i b^j / i>= j>=0}
O lo que es lo mismo, un lenguaje con mayor o igual número de 'a's que de 'b's y con un número indefinido de 'b's.
Para saber en qué momento deja de cumplirse el requisito al leer una palabra necesitas "recordar" lo que has leido previamente. Cuando necesitas recordar, quieres decir que todo lo que leas se introduce en una pila, y por lo tanto que es un lenguaje irregular.
En este caso, por cada 'a' que leemos la vamos insertando en la pila imaginaria, y luego, cuando empezamos a leer las 'b's, por cada una que leamos, se elimina una 'a' de la pila. Así, si lees 'b's sin que queden 'a's en la pila significa que j > i y esa palabra no pertenece al lenguaje. Se aceptará la palabra si al terminar de leerla la pila está vacía o sólo quedan 'a's.
En el caso de un lenguaje regular, no hace falta ninguna pila. Así que haz la prueba, intenta verificar mentalmente si puedes comprobar que una palabra pertenece a un lenguaje sin necesidad de recordar lo leido anteriormente.
L = {1 0^n / n>=0}
Fíjate que aquí lees un 1, todo va bien, lees el primer 0, ya pertenece al lenguaje, sigues leyendo 0s sin que te importe lo anterior. No necesitas pila alguna y por tanto es un lenguaje regular.
En tu caso:
L={x € {a,b}* / |x|a Mod 2 = 1}
Necesitas ir llevando la cuenta de 'a's que tiene la palabra. Traduciéndolo a al ejemplo de la pila, la primera 'a' se introduce en la pila, la segunda 'a' elimina la 'a' anterior. Así, cuando termines de leer la palabra, si hay una 'a' en la pila significa que había un número impar, sino hay, es que las 'a's de la palabra estaban pares.
Creo que no me he equivocado, aunque tengo esto algo oxidado, espero que te sirva de ayuda. Practícalo un poco y verás como le coges el truco.
