Los Autómatas Finitos Deterministicos (Parte I)

Este post pretendo mostrar el material que estoy diseñando para un curso de adiestramiento para una empresa que desarrolla software, y que se interesaron en un tema, que desde hace años siempre quise desarrollar y estudiar los detalles formales. El tema en cuestión es Redes de Petrí. Pero para llegar hasta allá, tenemos que pasar por un camino largo pero muy bonito, hablando de lenguajes, grafos, autómatas, y muchos aspectos técnicos adicionales. Y los cuales pretendo ir mostrando en mis post los cuales colgare de manera ínter--diaria. Así que comenzaremos con una pequeña introducción y luego ir hablando de algunos términos definiendo de poco a poco. Comencemos...

Introducción

Fundamental para la ciencia de la computación es la noción de un proceso computacional, también llamado algoritmo o proceso algorítmico. Al ejecutar estos procesos, las computadoras son capaces de resolver problemas; por el contrario, un computador no puede resolver un problema que no tenga una solución algorítmica. Por lo tanto, cualquier limitación en las capacidades de los procesos computacionales también es una limitación en las capacidades de las máquinas computacionales.

Al explorar el alcance de algunos procesos utilizando métodos rigurosos y matemáticos, y al mismo tiempo relacionar los resultados teóricos con las preocupaciones prácticas, se debe comenzar con un estudio teórico de técnicas de reconocimiento de patrones que relacionamos con los problemas prácticos del procesamiento del lenguaje en general. Es de hacer notar que esto nos lleva a aparentes límites en los poderes de los procesos computacionales y, por lo tanto, a un estudio teórico de computabilidad, ya que hay muchos problemas teóricamente solucionables mediante algoritmos, pero no tienen soluciones algorítmicas prácticas. Así en primer lugar se debe estudiar lo que respecta a los problemas relacionados con el procesamiento del lenguaje. Comenzando por revisar algunos de los conceptos y la terminología asociados con el proceso de traducción de lenguajes.

Lenguaje

Un lenguaje es un sistema de comunicación estructurado para el que existe un contexto de uso y ciertos principios combinatorios formales. Desde un punto de vista amplio, el lenguaje indica una característica que es común a los humanos y a otros animales para expresar sus experiencias y comunicarlas a otros mediante el uso de símbolos, señales y sonidos registrados por los órganos de los sentidos.

Podemos iniciar como primer punto aclarar los términos lenguaje formal y lenguaje natural. Los dos se pueden diferenciar con la pregunta: Qué fue primero, el lenguaje o sus reglas gramaticales?. En general, un lenguaje natural es uno que ha evolucionado con el tiempo con el propósito de la comunicación humana. Los idiomas continúan evolucionando sin tener en cuenta las reglas gramaticales formales. Los lenguajes naturales rara vez se ajustan a reglas gramaticales simples u obvias. A diferencia de los lenguajes naturales, los lenguajes formales están definidos por reglas preestablecidas, y por lo tanto se ajustan rigurosamente a ellas.

En el campo de las matemáticas, la lógica y las ciencias de la computación, un lenguaje formal es un lenguaje cuyos símbolos primitivos y reglas para unir esos símbolos están formalmente especificadas. Al conjunto de los símbolos primitivos se le llama el alfabeto del lenguaje, y al conjunto de las reglas se lo llama la gramática formal (o sintaxis).

A una cadena de símbolos formada de acuerdo a la gramática se la llama una fórmula bien formada o palabra del lenguaje. Estrictamente hablando, un lenguaje formal es idéntico al conjunto de todas sus fórmulas bien formadas. A diferencia de lo que ocurre con el alfabeto y con cada palabra bien formada, un lenguaje formal puede estar compuesto por un número infinito de palabras bien formadas. Algunas características podríamos nombrar:

1. Las palabras se escriben usualmente colocando las letras una a continuación de otra, sin separadores de ningún tipo. Por ejemplo, si a y b son símbolos del alfabeto entonces abbabbba es una fórmula o una palabra del lenguaje.
2. La palabra vacía la denotaremos con el símbolo lambda.
3. El conjunto de todas las palabras con alfabeto A se denota A*.
4. Un lenguaje (formal) con alfabeto A es cualquier subconjunto L de A*.

Expresiones regulares

En la teoría de lenguajes formales un término muy importante son las expresiones regulares, la cual no es otra cosa que una sucesión de caracteres que forma un patrón de búsqueda, principalmente utilizada para la búsqueda de patrones de cadenas de caracteres u operaciones de sustituciones. La mayoría de las formalizaciones proporcionan los siguientes constructores: una expresión regular es una forma de representar los lenguajes regulares y se construye utilizando caracteres del alfabeto sobre el cual se define el lenguaje. Las expresiones regulares se construyen utilizando los operadores unión, concatenación y clausura de Kleene.

Hay varias formas de especificar un lenguaje, entre ellas las gramáticas formales y las expresiones regulares, las cuales se definen recursivamente del modo siguiente:

Definición 1. Dado un alfabeto A entonces:

1. lambda y cualquier elemento x de A son expresiones regulares.
2. Si p y q son expresiones regulares entonces la unión y la concatenación también son expresiones regulares.
3. Si p es una expresión regular entonces también lo es p*.

A cada expresión regular p se le puede asociar un lenguaje L(p) del siguiente modo:

1. L(lambda)={lambda} y L(x)={x} para cualquier elemento x del alfabeto A.
2. Si p y q son expresiones regulares, entonces, el lenguaje de la unión es la unión de los lenguajes asociados, y el lenguaje generado por la concatenación es igual a la concatenación de los lenguajes asociados.
3. Si p es una expresión regular entonces el lenguaje asociado a p* es la familia de los lenguajes L(p).

Espero que esta pequeña parte, les haya gustado, los espero en mi próximo post, el cual publicare el viernes. Saludos y voten si les gusto, y compartan con sus amigos y seguidores.

Abdul Abner Lugo Jiménez
Twitter: @abdulmath
Instagram: @abdulmath
Facebook: https://www.facebook.com/alugo1978
Telefono: +58-414-9719116
email: [email protected]