En la sección anterior vimos que un AF se puede transformar en una GLC ¿La dirección contraria se puede? Es decir una GLC se pude transformar en un AF. Sabemos que no se pude para todos, porque existen GLC que generan lenguajes que no son regulares ¿Entonces bajo que condición se podría? Sólo se podrá para lo que denominaremos como:
GR #
Una Gramática Regular (GLC) es una tupla
\((V,\Sigma,P,S)\)
donde:
- \(V\) es un alfabeto de símbolos no terminales o símbolos auxiliares
- \(\Sigma\) es un alfabeto de símbolos terminales, que conforman nuestras cadenas
- \(P\) es un conjunto de reglas que con la forma \(A \rightarrow bB | c \) donde \(b \in \Sigma, c \in \Sigma, A \in V, B \in V \)
- \(S \in V\) lo denominamos símbolo inicial
Si comparamos lo único que cambia con respecto a las GLC es la forma de la regla. Pasa de ser: \[A \rightarrow \alpha\] A esta forma que es mas restrictiva: \[A \rightarrow bB | c \]
Con esto en mente, toda GR se puede convertir en un AF siguiendo un proceso inverso al presentado en la sección anterior.