Jerarquía de Chomsky

Jerarquía de Chomsky

Es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Consta de 4 niveles o tipos de gramáticas.

Nivel 0: 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. No tienen ninguna restricción.

Nivel 1: Son las gramáticas sensibles al contexto, las cuales son reconocidos por las máquinas autómatas lineales limitadas. Estas gramáticas tienen reglas de la forma con un no terminal y , y cadenas de terminales y no terminales. Las cadenas y pueden ser vacías, pero no puede serlo.

Nivel 2: Son los lenguajes libres de contexto o independientes y legibles por máquinas autómatas de pila. Tiene la regla -> . A pertenece a los no terminales mientras que S pertenece a (N U T)+.

Nivel 3: Son los lenguajes regulares, los cuales son reconocidos por maquinas autómatas de estado finito. 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.

...