Clasificación de Gramática y Lenguajes de Chomsky

Clasificación de Gramática y Lenguajes de Chomsky

1. Llamada también Jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales.

2. Esta jerarquía fue descrita por Noam Chomsky en 1956

3. La jerarquía de Chomsky consta de 4 niveles

   • Gramáticas de tipo 0
     • que incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes capaces de ser reconocidos por una máquina de Turing. Los lenguajes son conocidos como lenguajes recursivamente enumerables. Nótese que esta categoría es diferente de la de los lenguajes recursivos, cuya decisión puede ser realizada por una máquina de Turing que se detenga.
   • Gramáticas de tipo 1
     • Generan los lenguajes sensibles al contexto. Los lenguajes descritos por estas gramáticas son exactamente todos aquellos lenguajes reconocidos por una máquina de Turing determinista cuya cinta de memoria está acotada por un cierto número entero de veces sobre la longitud de entrada, también conocidas como autómatas linealmente acotados.
   • Gramáticas de tipo 2
     • Generan los lenguajes independientes del contexto. Estos lenguajes son aquellos que pueden ser reconocidos por un autómata con pila.
   • Gramáticas de tipo 3
     • Generan los lenguajes regulares. Estas gramáticas se restringen a aquellas reglas que tienen en la parte izquierda un no terminal, y en la parte derecha un solo terminal, posiblemente seguido de un no terminal. Estos lenguajes son aquellos que pueden ser aceptados por un autómata finito. También esta familia de lenguajes pueden ser obtenidas por medio de expresiones regulares.
   • Cada lenguaje regular es a su vez libre del contexto, asimismo un lenguaje libre del contexto es también dependiente del contexto, este es recursivo y a su vez, recursivamente enumerable. Las inclusiones son, sin embargo, propias, es decir, existen en cada nivel lenguajes que no están en niveles anteriores.
     • Gramáticas Tipo 0
       • Recursivamente Enumerable
         • Autómata Turing
     • Gramáticas Tipo 1
       • Dependiente del Contexto
         • Autómata Linealmente Acotado
     • Gramáticas Tipo 2
       • Independiente del Contexto
         • Autómata con Pila
     • Gramáticas Tipo 3
       • Regular
         • Autómata Finito

Bilder und Dateien der Mindmap