Relaciones entre Lenguajes Regulares, Expresiones Regulares, Autómatas Finitos y Gramáticas Lineales

Computabilidad

En Teoría de la Computación lo importante no es buscar la mejor manera de hacer las cosas, sino estudiar qué puede o no puede hacerse con una computadora, a esto se le llama Computabilidad.

Teorema de Incompletitud:

Todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de axiomas sea recursivo no es completo.

Una versión posterior y más general del teorema de Gödel elimina la posibilidad de considerar sistemas deductivos más potentes que los sistemas de primer orden, demostrando que no pueden ser consistentes y completos a la vez.

Los resultados de este científico prueban que no solo no existe un algoritmo que pueda demostrar todos los teoremas en matemáticas, sino que además, no todos los resultados son demostrables.

La primera computadora electrónica de propósito general fue el ENIAC, que se desarrolló a partir del año 1943, diez años después del origen de los modelos abstractos de cálculo.

Turing

Los primeros trabajos de los científicos referidos han tenido una profunda influencia tanto en el desarrollo teórico de las Ciencias de la Computación, como en muchos aspectos prácticos de la Informática.

La existencia de ordenadores de propósito general;
La posibilidad de interpretar programas;
La dualidad entre software y hardware;
La representación de lenguajes por estructuras formales basados en reglas de producción.

Algunas de las grandes aportaciones de estos investigadores fueron:

Alonzo Church

Alonzo Church propuso la noción de función λ-definible como función efectivamente calculable. La demostración de teoremas se convierte en una transformación de una cadena de símbolos en otra, según un conjunto de reglas formales, que se conocen como lambda cálculo. Church hace un esquema de la demostración de la equivalencia entre las funciones λ-definibles y las funciones recursivas, éstas iban a ser las únicas funciones calculables por medio de un algoritmo a través de su tesis, llamada Tesis de Church.

Kleene

Kleene, por su parte, pocos meses después, demuestra de forma independiente la equivalencia entre funciones λ-definibles y funciones recursivas de Herbrand-Gödel, a través del concepto de función recursiva.

Alan Turing

Una tercera noción de función calculable proviene del matemático inglés Alan Turing. Este señaló que había tenido éxito en caracterizar de un modo matemáticamente preciso, por medio de sus máquinas, la clase de las funciones calculables mediante un algoritmo, identificado como funciones Turing-computables, es lo que se conoce hoy como Tesis de Turing.

Además, utilizó su concepto de máquina para demostrar que existen problemas que no son calculables por un método definido y, en particular, que el Entscheidungsproblem era uno de esos problemas.

Cuando Turing conoció los trabajos de Church y Kleene, demostró que los conceptos de función λ-definible y función calculable por medio de una máquina de Turing coinciden.

Complejidad Algorítmica

Después de que la Teoría de la Computabilidad fuera desarrollada, era natural preguntarse acerca de la dificultad computacional de las funciones computables.

Se conoce como Complejidad Algorítmica.

¿Qué quiere decir que una función f() sea más difícil de computar que otra función g()?

Con lo que Rabin sugirió un axioma.

Una segunda aportación fue “On the Complexity of Algorithms”. En él se introduce la noción fundamental de medida de complejidad definida como el tiempo de computación sobre una máquina de Turing multicinta.

Un tercer hito en los comienzos de la Complejidad Algorítmica fue el “The Intrinsic Computational Difficulty of Functions”, donde se enfatizaba el término “intrínseco”. Esto nos conduce a un concepto importante desarrollado por entonces, que es: la identificación de la clase de problemas que se pueden resolver en tiempo acotado por un polinomio sobre la longitud de la entrada.

La distinción entre algoritmos de tiempo polinomial y algoritmos de tiempo exponencial había sido hecha por primera vez por [JVonNeumann].

La notación de P para la clase de los problemas resolubles en tiempo polinomial fue introducida posteriormente por RMKarp.

La teoría de la NP-completitud es seguramente el desarrollo más importante de la Complejidad Algorítmica. La clase NP consta de todos los problemas decidibles en tiempo polinomial por una máquina de Turing no determinista.

[SCook] introduce posteriormente la noción de problema NP-completo y demuestra que el problema de la satisfacibilidad booleana es NP-completo.

Demostrar que un problema es NP-completo equivale a demostrar que no tiene una solución determinista en tiempo polinomial, salvo que todos los problemas de NP estén en P, cuestión que aún no está demostrada.

Criptografía

Criptografía, se encarga actualmente del estudio de los algoritmos, protocolos y sistemas que se utilizan para proteger la información y dotar de seguridad a las comunicaciones y a las entidades que comunica.

Mediante la criptografía podemos conseguir el manejo de información confidencial en el ordenador de forma más o menos segura.

Teoría de Autómatas

En el campo de los procesadores de lenguaje lo fundamental es la simulación de procesos para tratar información, estas tareas las realiza un autómata de modo que sirve para comprobar si una sentencia o instrucción pertenece o no a un determinado lenguaje.

El autómata recibe los símbolos de entrada, uno detrás de otro, es decir secuencialmente. Hemos estudiado que el símbolo de salida que en un instante determinado produce un autómata, no solo depende del último símbolo recibido a la entrada, sino de toda la secuencia o cadena de símbolos recibida hasta ese instante.

El estado de un autómata es toda la información necesaria en un momento dado, para poder deducir, dado un símbolo de entrada en ese momento, cuál será el símbolo de salida. El autómata tendrá un determinado número de estados (pudiendo ser infinitos), y se encontrará en uno u otro según sea la historia de símbolos que le han llegado.

[CEShannon] estableció las bases para la aplicación de la Lógica Matemática a los circuitos combinatorios.

Posteriormente [DAHuffman] los extendió a los circuitos secuenciales, estos circuitos utilizan conceptos como estado de un autómata y las tablas de transición.

El concepto de autómata finito surge del artículo presentado por [WSMCulloch] y [WPitts] titulado “A Logical Calculus of the Ideas Immanent in Nervous Activity” donde describen los cálculos lógicos inmersos en una neurona artificial, ideada para simular la actividad de una neurona biológica.

[SCKleene] realiza un informe sobre los trabajos de McCulloch – Pitts. En este trabajo Kleene demuestra la equivalencia entre lo que él llama “dos formas de definir una misma cosa”:

Los conjuntos regulares → los cuales pueden ser descritos a partir de sucesos bases.
Y los operadores unión, concatenación y clausura → mediante expresiones regulares y los lenguajes reconocidos por un autómata finito.

Los autómatas finitos son capaces de reconocer solamente un determinado tipo de lenguajes, llamados lenguajes regulares.

Una forma adicional de caracterizar este tipo de lenguajes es mediante operadores sobre el alfabeto del lenguaje y otras expresiones regulares, incluyendo el lenguaje vacío.

Para un alfabeto concreto, no todos los lenguajes que se pueden construir son regulares.

La Teoría de Autómatas ha encontrado su aplicación en varios campos, algunos de ellos son los siguientes:

Teoría de la Comunicación;
Teoría de Control;
Lógica de Circuitos Secuenciales;
Reconocimiento de Patrones;
Fisiología del Sistema Nervioso;
Estructura y Análisis de los Lenguajes de Programación;
Traducción Automática de Lenguajes;
Teoría Algebraica de Lenguajes.

Cuando un autómata se usa para modelar la construcción de hardware o software es muy importante examinar o encontrar el autómata mínimo equivalente a uno dado. Tanto Huffman como Moore se ocuparon de este problema y encontraron algoritmos prácticos para minimizar un autómata de estados finitos.

Para un autómata de