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

• di Tada, Esteban ^[1]
  1. [1] Universidad de Palermo
• Localización: Ciencia y tecnología, ISSN 1850-0870, ISSN-e 2344-9217, Nº. 12, 2012, págs. 93-103
• Idioma: español
• DOI: 10.18682/cyt.v1i12.650
• Enlaces
  • Texto completo
• Resumen
  • 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.

• Referencias bibliográficas
  • K. R. Chowdhari: “Fundamental of Discrete Mathematical”, Second Edition, Structures PHI Learning Private Limited, January 2012
  • Philip Edward Bertrand Jourdain, “Selected essays on the History of Set Theory and Logics”, CLUEB 1991
  • Joseph Warren Dauben, “Georg Cantor His Mathematics and Philosophy of the infinity, Princeton University Press 1979
  • John E. Hopcroft, “Introduction To Automata Theory, Languages, And Computation”, Pearson Education, 2008
  • Rebecca Goldstein, “Gödel Paradoja y vida” , Antoni Bosh Editor España, 2005
  • Ernest Nagel, James R. Newman, “Gödel’s Proof”, New York University Press, 2001
  • Georg Cantor, “Contribution to the Founding of the theory of transfinite Numbers, Cosimo Inc. 2007