Page 53 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS
P. 53

53


                     FASES DE LA COMPILACIÓN VS LENGUAJES FORMALES VS AUTÓMATAS.

                  Como  ya  se  dijo,      conceptualmente,  un  compilador  opera  en  fases,  cada  una  de  las  cuales

                  transforma al programa fuente de una representación en otra.


                  Una expresión regular denota un conjunto de secuencias de símbolos válidas que se construyen

                  en base al alfabeto de un lenguaje. A su vez, las expresiones regulares son operaciones que se
                  realizan sobre conjuntos de símbolos que pertenecen al alfabeto de un lenguaje.


                  Una expresión regular es un método formal para describir un patrón y puede ser empleada para

                  construir un analizador léxico que lo reconozca en una computadora. De hecho, la expresión sufre

                  una serie de transformaciones para llegar a ser explotada como tabla.  Así las cosas, una expresión
                  regular se convierte en un autómata finito no determinístico (NFA), y este se convierte en un

                  autómata finito determinístico (DFA), que se representan como tablas.
                  Todas las transformaciones constituyen autómatas finitos, mismos que son en términos generales:

                  un conjunto de nodos y aristas que representan trayectorias para generar una expresión bajo un
                  alfabeto. Un diagrama de transición es un autómata finito. Y como ya vimos un autómata finito

                  no determinístico lo definimos como un modelo matemático que contiene una tupla que define:


                      1-  Un conjunto de estados.

                      2-  Un conjunto de símbolos de entrada.

                      3-  Una función de transición que corresponde pares estado-símbolo a conjuntos de estados.
                      4-  Un estado que denota como el estado inicial.

                      5-  Un conjunto de estados f que denotan los estados de aceptación o finales.


                  Expresada esta relación de equivalencia entre jerarquía de gramáticas de Chomsky, máquinas
                  abstractas, y la teoría de la computabilidad, vamos a entrar en lo que son lenguajes regulares y los

                  autómatas finitos.
   48   49   50   51   52   53   54   55   56   57   58