Clasificación de las gramáticas

Pre-requisisto: Gramáticas
Según Chomsky los tipos de gramáticas son:

GRÁMATICAS TIPO 0

Son no restringidas
Reconocidas por la máquina de Turing.
Solo cumplen la definición de gramática.
Sus reglas de producción tiene la forma:

α → ꞵ , α y ꞵ ∈ (N U Z) *

Tanto el lado derecho como izquierdo pueden contener símbolos terminales como no terminales.

GRAMATICAS TIPO 1

Sensitivas al contexto.

Son reconocidos por el autómata linealmente acotado.

α → ꞵ , |ꞵ| >= |α|

En la regla de producción la longitud del lado izquierdo es mayor o igual que la longitud del lado derecho.

GRAMÁTICAS TIPO 2

Libre de contexto.

Reconocidas por el autómata de pila.

Usado en los lenguajes de programación para definir su estructura sintáctica.

A → ꞵ, A ∈ N , ꞵ ∈ (N U Z) *

En el lado izquierdo de la producción solo existe un símbolo no terminal y en el lado izquierdo puede existir una combinación de símbolos terminales como no terminales.

GRAMÁTICAS TIPO 3

Gramáticas regulares.

Reconocidas por el autómata finito.

Los lenguajes que son representados por éste tipo de gramática se denominan: lenguajes regulares.

A → aB | B | a | λ

En el lado izquierdo de la producción solo puede estar un símbolo no terminal.

En el lado derecho sólo puede estar un símbolo terminal o no terminal, puede existir una combinación de uno de cada uno, como también ninguno (λ).