Estructura de lenguajes

REVISIÓN HISTÓRICA Y CRONOLÓGICA DE LA APARICION DE LOS TEMAS
MÁS IMPORTANTES DEL CUROS Estructuras de Lenguajes.

RESUMEN
Es artículo contiene una revisión histórica y cronológica de los temas que son desarrollados en la materia Estructuras de Lenguajes los cuales son (Alfabetos, Palabras y Lenguajes) como Primer Modulo del Curso; (Lenguajes Regulares, Autómatas FinitosDeterministas “AFD”, Autómatas Finitos No Deterministas “AFND” y relación de los AFD con Expresiones Regulares) Segundo Modulo del Curso; (Maquinas Secuenciales, Gramáticas Independientes del Contexto, Gramáticas de Estructura de Frase, Forma de Chomsky) Tercer Modulo del Curso; (Autómatas Probabilísticos, Autómatas de Mc Culloch y Pitts) Cuarto Modulo del Curso; (Autómatas de Pila Deterministico “APD”,Autómatas den Pila No Deterministico “APND”) Quinto Modulo del Curso; (Maquinas de TURING “MT”) Sexto Modulo del Curso. Siendo el fundamento teóricas sobre Ciencias de la Computación que servirán para el Ingeniero de Sistemas y Computación.

PALABRAS CLAVES: Lenguajes Regulares, “AFD”, “AFND”, expresiones regulares, Gramáticas, “APD”, “APND”, “MT”.

ABSTRACT: It’s article contains ahistorical and chronological review of the issues that are developed in the field structures languages which are (Alphabets, Words and Languages) as the First Module of the Curse; (Regular Languages, Deterministic Finite Automata “AFD”, Finite Automata No Deterministic “AFND” and relationship of the AFD whit Regular Expressions) Second Course Module; (Sequential Machines, Context-Free Grammar, PhraseStructure Grammar, Chomsky Form) Third Course Module; (Probabilistic Automata, Automata of Mc Culloch and Pitts) Fourth Course Module; (Deterministic Stack Automata “APD” den Stack Nondeterministic Automata “APND”) Fifth Course Module; (TURIN Machines “MT”) Sixth Course Module. As the theoretical foundation of computer science will serve for systems and computer Engineering.

KEYWORDS: RegularLanguages, “AFD”, “AFND”, Regular Expressions, Grammar, “APD”, “APND”, “MT”.




CRISTIAN SOTO RAMIRES
Ingeniero sistemas
Universidad Tecnológica de Pereira
cristian_dav_-n-@hotmail.com

1. INTRODUCCIÓN:
Informática Teórica: confluencia de investigaciones sobre los fundamentos de las matemáticas, teoría de máquinas, lingüística, etc. Ciencia multidisciplinar, apoyada en la observación deque los mismos fenómenos pueden aparecer y explicar áreas completamente distintas y en apariencia sin conexión.
La aparición de estudios sobre Informática Teórica se remonta a primeros de siglo. Dentro de los hitos más importantes se pueden citar los siguientes:

En 1900 David Hilbert propone “el problema de la decisión”, que trata de descubrir un método general para decidir si una fórmulalógica es verdadera o falsa.
 
Aparición del artículo de Kurt Gödel, publicado en 1931, “On Formally Undecidible Propositions in Principia Mathematica and Relates Systems”. Este trabajo puede considerarse como la mayor realización matemática del siglo XX. El teorema de Gödel sostiene que cualquier teoría matemática contendrá afirmaciones “indecidibles”.
En 1937, el matemático inglés Alan MathisonTuring publica un famoso artículo que desarrolla el teorema de Gödel, y que puede considerarse como el origen oficial de la Informática Teórica. En este artículo se introduce el concepto de máquina de Turing, una entidad matemática abstracta que formaliza por primera vez el concepto de algoritmo.

Paradójicamente, la máquina de Turing, mecanismo que formaliza el concepto de algoritmo, quepretende ser lo suficientemente general como para resolver cualquier problema posible (siempre que sea computacionalmente abordable), se introduce para demostrar la validez de los postulados de Gödel. Es decir, Turing demuestra que existen problemas irresolubles, inasequibles para cualquier máquina de Turing, y por ende, actualmente, para cualquier ordenador.
Al ser la máquina de Turing un modelo...