RECONOCEDOR DE LENGUAJE

AF como reconocedor de un Lenguaje:

• Cuando un AF transita desde q0 a un estado final en varios movimientos, se ha producido el RECONOCIMIENTO o ACEPTACIÓN de la cadena de entrada.
• Cuando un AF no es capaz de alcanzar un estado final, se dice que el AF NO RECONOCE la cadena de entrada y que ésta NO PERTENECE al lenguaje reconocido por el AF.

Ejemplo:

A partir del autómata, comprobar si reconoce la palabra “aabbaba”.

Empezaríamos en el estado P, al recibir una "a", pasaríamos a Q, al recibir una "a" de nuevo, seguiríamos en Q, después al recibir una "b", pasaríamos a R, y recibiendo otra "b", seguiríamos en R. A continuación recibiríamos una "a", que nos llevaría a R y así hasta el final. Por lo tanto al quedar después de la palabra leída en el estado R, y dado que este no es un estado final como lo es Q, la palabra no se reconocería. En cambio la palabra “aa” si que se reconocería puesto que terminaríamos en el estado final Q. Se trata por tanto de un autómata que reconoce lenguajes formados exclusivamente por una o varias “a”.