Relacion Entre Automatas Finitos Y Gramaticas Regulares

RELACIÓN ENTRE AUTÓMATAS Y GRAMÁTICAS
Una Gramática Regular y un Autómata de Estado Finito se relacionan entre sí, ya que cualquiera de ellos se vincula directamentecon un determinado Lenguaje Regular. Hay una estrecha relación entre una Gramática Regular  que produce un determinado Lenguaje Regular y el Autómata Finito  que aceptaexactamente las cadenas de ese mismo Lenguaje. Dado el Autómata que reconoce números reales y exponenciales sin signo, analizado previamente, se puede construir unaGramática Regular que produce tal Lenguaje, por ejemplo. Este hecho favorece a los alumnos de un curso de compiladores, ya que pueden diseñar con el Autómata un compiladorpersonal y de ahí se deducen las reglas gramaticales. Para definir la Gramática del Lenguaje Regular aceptada por un Autómata Finito, se sigue el siguiente procedimiento:a) Los símbolos de entrada de A son los terminales de G.
b) Los estados se convierten en los símbolos no terminales.
c) El estado inicial se transforma en el símboloinicial.
d) Las composiciones corresponden a los arcos dirigidos.
Si existe un arco con la entrada x de A hacia B se incluye en la Gramática Regular la regla deproducción A→ xB
.Además, si esa misma transición se dirige hacia un estado de aceptación, por ejemplo si B lo fuera en este caso, se incluye la composición A→ x, aparte dela anterior.

 
 
EJEMPLO:
Determinar la Gramática Regular que produce el Lenguaje Regular aceptado por el Autómata Finito que se muestra a continuación

N = {A,B, C, D} T ={a,b} σ0={A}
P = {A→ aB | bC |bD, B→ aB,
C→ aC | bD, D→aB | bB | bD,
A→ a, A → b, B →a, C →a, D →a, D →b}