Resumen de Las limitaciones de los modelos finitos de gramáticas para la definición de lenguajes

Esteban di Tada

• español

  El uso de reglas de reescritura para el estudio de lenguajes fue introducido por Axel Thue1 y posteriormente profundizado por Avram Noam Chomsky2 que creó el concepto de gramática generativa y estableció las cuatro jerarquías conocidas como Jerarquías de Chomsky en base a su capacidad de generación de lenguajes. El problema que planteamos aquí es el de demostrar que el modelo de gramática finita solo puede representar una cantidad muy reducida de lenguajes.

• English

  The use of rewritten rules in the study of languages was used for the first time by Axel Thue and then formalized by Noam Chomsky who introduced the concept of generative grammars. He defined also the 4 hierarchies known as Chomsky Hierarchies based on the power to generate languages. The problem we will study here is to answer the question if with finite models defined over a given alphabet it is possible to represent all the possible languages that exist on this alphabet.