INTRODUCCIÓN A LA TEORIA DE LENJUAGES FORMALES

Clasificación de las gramáticas (lenguajes) según Chomsky

 

Tipo 0: Es el tipo más general. Definen lenguajes con estructura de frases. Las máquinas de Turing reconocen lenguajes de este tipo

.

Tipo 1: Gramáticas sensibles al contexto. Los autómatas lineales acotados reconocen lenguajes de este tipo.

 

Tipo 2: Gramáticas libres de contexto. Los autómatas a pila reconocen los lenguajes generados por estas gramáticas.

 

Tipo 3: Gramáticas regulares. Los lenguajes reconocidos por estas gramáticas se denominan lenguajes regulares, y son reconocidos por autómatas finitos.