Es posible transformar un AF a una GLC, recordemos que las GLC pueden generar a los lenguajes regulares, por lo tanto suena posible que un AF que acepta a un Lenguaje Regular pueda trasformarse en un AF.
Transformación #
- Cambiar los estados por símbolos auxiliares que conformaran V, un símbolo auxiliar por estado q del AF.
- Por cada transición crear una regla de producción con el siguiente formato:
Donde A representa a un estado origen y B un estado destino a través del símbolo a.
- Agregar una transición con la siguiente forma por cada transición del AF original que termine en un estado final.
Ejemplo #
Considere el siguiente AF:
Número par de bes
-
Proponer símbolos auxiliares \[V = \{A_{q_0}, B_{q_1}\}\]
-
Agregar reglas de producción por transición \[\begin{array}{rl} A \rightarrow & aA \\ A \rightarrow & aB \\ B \rightarrow & aB \\ B \rightarrow & bA \\ \end{array}\]
-
Agregar reglas de producción por transición que llega a estado final \[\begin{array}{rl} A \rightarrow & a \\ B \rightarrow & b \\ \end{array}\]
Nuestra gramática completa queda: \[\begin{array}{rl} A \rightarrow & aA \\ A \rightarrow & aB \\ B \rightarrow & aB \\ B \rightarrow & bA \\ A \rightarrow & a \\ B \rightarrow & b \\ \end{array}\]
La siguiente es la derivación para la cadena aabbabaaaaba:
\[\begin{array}{rl} A \Rightarrow & aA\\ \Rightarrow & aaA\\ \Rightarrow & aabB\\ \Rightarrow & aabbA\\ \Rightarrow & aabbaA\\ \Rightarrow & aabbabB\\ \Rightarrow & aabbabaB\\ \Rightarrow & aabbabaaB\\ \Rightarrow & aabbabaaaB\\ \Rightarrow & aabbabaaaaB\\ \Rightarrow & aabbabaaaab\\ \end{array}\]Dada la forma de las reglas es posible ver que siempre hay un sólo símbolo no terminal en lado derecho de la derivación, esto origina que sólo haya una derivación posible y además un árbol de derivación (que se muestra a continuación), es decir este tipo de gramáticas no son ambiguas.
