Llamamos "clase de lenguajes" a conjuntos de lenguajes que comparten una cierta propiedad dada. Esta noción es abstracta, ya que los lenguajes son en sí conjuntos de secuencias símbolos.

La clasificación de lenguajes en clases de lenguajes es debida a Noam Chomsky, quien propuso una jerarquía de lenguajes, donde están los lenguajes más simples.


teo-chomsky.png



Nosotros estudiaremos las clases propuestas en la figura, que son:

  • Lenguajes Regulares , es la clase más pequeña, e incluye a los lenguajes más simples. Un ejemplo es el de los números binarios.
  • Lenguajes Libres de Contexto, que incluyen a los Lenguajes Regulares. Por ejemplo la mayoría de los lenguajes de programación.
  • Lenguajes Recursivamente Enumerables, incluyen a los Libres de Contexto y a los los Lenguajes Regulares.

En capítulos posteriores veremos que cada clase de lenguajes está asociada a un tipo de "autómata" capaz de procesar cada uno de los lenguajes.