Page 40 - LENGUAJES FORMALES AUTOMATAS Y COMPILADOS
P. 40

40


                  En el siguiente cuadro se esquematiza la relación entre lenguajes, gramáticas, máquinas abstractas
                  y problemas. Atendiendo al lenguaje o tipo del lenguaje, así mismo se asocia un tipo de autómata,
                  así las cosas, se definirán  los lenguajes clasificados según Chomsky.


                       Gramáticas            Lenguajes             Máquinas               Problemas

                                                                                          NO COMPUTABLES



                       Tipo 0 de Chomsky  Recursivamente         Máquinas de Turing            Computables
                                             Numerables
                                             Lenguajes           Autómatas lineales acotados
                       Tipo 1 de Chomsky  sensibles al
                                             contexto
                                             Lenguajes           Autómatas a pila
                       Tipo 2 de Chomsky  independientes
                                             del contexto
                       Tipo 3 de Chomsky  Lenguajes              Autómatas finitos             Expresiones
                                             regulares           deterministas                 regulares

                      En estos tipos:

                            Tipo 3: gramáticas regulares que generan lenguajes regulares.
                            Tipo  2:  gramáticas  incontextuales  o  libres  de  contexto  que  generan  lenguajes
                             incontextuales o también denominadas fuera de contexto.
                            Tipo 1: gramáticas contextuales o dependientes del contexto, que generan lenguajes
                             contextuales.
                            Tipo 0: gramáticas libres que generan lenguajes sin ningún tipo de restricción.

                  Cuanto menor es el tipo,
                  mayor es el poder expresivo
                  del lenguaje generado y más
                  complejidad tiene su
                  tratamiento por parte de una
                  máquina.

                  La clasificación completa
                  asociada a los problemas y
                  lenguajes.
   35   36   37   38   39   40   41   42   43   44   45