TEoria de autómatas y lenguajes
formales II
INDICE:
-TEMA 1-
MÁQUINAS, LENGUAJES Y
ALGORITMOS
- TEMA 2 -
LENGUAJES FORMALES
- TEMA 3 -
GRAMÁTICAS FORMALES
- TEMA 4-
SISTEMAS, MODELOS Y VISTAS
- TEMA 5 -
DESCRIPCIÓN DE LA
ESTRUCTURA : BASES
- TEMA 6-
DESCRIPCIÓN DE LA
ESTRUCTURA : AÑADIENDO MÁS DETALLE
- TEMA 7 -
DESCRIPCIÓN DEL COMPORTAMIENTO
-TEMA 1-
1.- Conceptos prévios.
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 de que
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 remontan 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órmula ló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 Mathison Turing
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, que pretende 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 ideal de máquina capaz de adoptar una infinidad
de estados posibles, resulta obvio pensar que su realización está fuera del
alcance práctico. Sin embargo, debido a la gran capacidad de los ordenadores
actuales, la máquina de Turing resulta ser un modelo adecuado de su
funcionamiento.
· En 1938, se
produce una importante aportación a la Informática Teórica, en el terreno de la
Ingeniería Eléctrica. Publica su artículo “A
Symbolic Analysis of Relay and Switching Circuits” el matemático Claude Elwood Shannon. En él se
establecen las bases para la aplicación de la lógica matemática a los circuitos
electrónicos. En las décadas siguientes las ideas de Shannon se desarrollaron
ampliamente, dando lugar a la formalización de una teoría sobre máquinas
secuenciales y autómatas finitos.
Desde su
nacimiento, la teoría de autómatas ha encontrado aplicación en muy diversos
campos. Esto se debe a que resulta muy natural considerar, tanto los autómatas
como las máquinas secuenciales, sistemas capaces de transmitir (procesar)
información. En definitiva, esto es equiparable a cualquier sistema existente
en la naturaleza, que recibe señales de su entorno, reacciona ante ellas y
emite así nuevas señales al ambiente que le rodea.
Algunos de los
campos donde ha encontrado aplicación la teoría de autómatas son :
· Teoría de la
Comunicación
· Teoría de
Control
· Lógica de los
circuitos secuenciales
· Ordenadores
· Teoría lógica
de los sistemas evolutivos y auto-reproductivos
· Reconocimiento
de patrones
· Fisiología del
sistema nervioso
· Traducción
automática de lenguajes
· etc
· En 1950 se
vincula la Informática Teórica con otro terreno con el que habitualmente ni se
había relacionado (ni siquiera se consideraba como científico) : la
Lingüística. En este año el lingüista Avram Noam Chomsky publica su “Teoría de
las Gramáticas Transformacionales”, que establece las bases de la lingüística
matemática. Proporcionó una herramienta de inestimable ayuda, no sólo en el
estudio de los lenguajes naturales, sino también en la formalización de los
lenguajes de ordenador, que comenzaban a aparecer en estos años.
La teoría de
Lenguajes Formales resultó tener una sorprendente relación con la Teoría de las
Máquinas Abstractas. Los mismos fenómenos aparecían en ambas disciplinas y era
posible establecer correspondencias muy claras entre ellas (isomorfismos).
Chomsky
clasificará los lenguajes formales de acuerdo a una jerarquía de cuatro
niveles, conteniendo cada uno de todos los siguientes. El lenguaje más general
será, pues, de tipo 0, y no posee restricción alguna. Este conjunto engloba el
conjunto de todos los lenguajes posibles.
En el segundo
nivel aparecen los lenguajes de tipo 1, también llamados lenguajes “sensibles
al contexto”, al permitir que el “papel” de las palabras dependa de la posición
en que aparezcan (es decir, del contexto). La mayor parte de los lenguajes de
ordenador pertenecen a este tipo.
En tercer lugar
aparecen los lenguajes de tipo 2, o lenguajes “independientes del contexto”. En
ellas el significado de una palabra es independiente del lugar que ocupa en la
frase.
Finalmente, los
lenguajes de tipo 3, o lenguajes regulares, son los que presentan una
estructura más sencilla.
Resulta curioso
observar como paralelamente a la jerarquía de lenguajes aparece otra de
máquinas abstractas equivalentes, como se observa en el esquema
siguiente :
Cada uno de
estos tipos de máquinas es capaz de resolver problemas cada vez más
complicados, hasta llegar a las máquinas de Turing. Como descubrió Turing,
existen una serie de problemas que no son computacionalmente abordables y que
reciben el nombre de “problemas no enumerables”.
1.-
Alfabetos
Se llama alfabeto a un conjunto finito, no
vacío, cuyos elementos se denominan “letras” o “símbolos”. Se definen los alfabetos por la enumeración de los
símbolos que contiene. Veamos algunos ejemplos :
A1={A, B, C, D,
E, F , G, ..., Z}
A2={0,1}
A3={0, 1, 2, 3,
4, 5, 6, 7, 8, 9, .}
A4={\, /}
2.-Palabras
Se denomina palabra, formada con los símbolos de un
alfabeto, a toda secuencia finita de
letras de ese alfabeto.
Palabras sobre A1 :
JUAN, PEDRO, LUIS, DASDSADA
Palabras sobre A2 :
0 1 11001100 1111
Palabras sobre A3 :
2 304 126.34
Palabras sobre A4 :
\\\\/// /\//
Se usarán letras minúsculas
para representar las palabras de un alfabeto :
x = JUAN (sobre A1)
y = //\/ (sobre
A4)
z = 123.56 (sobre
A3)
La longitud de una palabra
viene determinada por el número de símbolos (letras) que la componen :
| x | = 4
| y | = 4
| z | = 6
Se define la palabra vacía como aquella cuya longitud
es cero. Se representa mediante la letra l. Cualquiera
que sea el alfabeto considerado, siempre puede formarse con sus símbolos la
palabra vacía (bastaría formar una palabra sin seleccionar a ninguno de ellos).
El conjunto de
palabras que se pueden formar con las letras de un alfabeto recibe el nombre de
“universo del discurso” o “lenguaje
universal” de ese alfabeto. Sobre el alfabeto A, el lenguaje universal se
representa por W(A). Evidentemente
W(A) es un conjunto infinito.
Supongamos el
alfabeto con el menor número posible de letras (1).
A = { p }
En este caso,
W(A) = { l, p, pp, ppp,
pppp, ppppp, ...}, y contiene un número infinito de elementos.
La palabra
vacía pertenece a todos los lenguajes universales de todos los alfabetos
posibles.
3.- Operaciones con palabras
· Concatenación de palabras
Sean dos
palabras x, y tales que
x Î W(A), y Î W(A)
Supongamos que
| x | = i y que | y | = j. Así x será Am1Am2Am3
... Ami e y será An1An2An3 ... Anj.
Se llama concatenación de las palabras x e y (y se representa por xy) a otra
palabra (z) obtenida poniendo las letras de y a continuación de las de x :
z= {Am1Am2Am3
... Ami An1An2An3 ... Anj}
|--------------------------------|-----------------------|
x y
Otra notación
habitual para la operación de concatenación de las palabras x e y es x.y.
Consideramos a
continuación las propiedades de la
concatenación :
· Operación cerrada. Es decir, la concatenación
de dos palabras de W(A) es otra palabra de W(A). Si x Î W(A) e y Î W(A), entonces xy Î W(A).
· Propiedad asociativa : x(yz)=(xy)z
Por cumplir
estas propiedades, la operación de concatenación de palabras de un alfabeto es
un semigrupo.
· Existencia de elemento neutro. El elemento
neutro de esta operación es la palabra vacía l, tanto por la derecha como
por la izquierda. Siendo x una palabra cualquiera, se cumple :
xl = lx = x
Al cumplir las
tres propiedades anteriores, se trata de una operación con estructura de monoide (semigrupo con elemento neutro).
Sin embargo, la concatenación no cumple la propiedad
conmutativa. Esto se observa mediante cualquier contraejemplo. Sean las
palabras x= ABC e y = CDE. Tenemos que
xy = ABCCDE
yx = CDEABC
Si z está formada
por la concatenación de las palabras x e y (es decir, z = xy), se dice que x es
cabeza de z y que y es cola de z. Además, x será cabeza propia siempre que y no sea la
palabra vacía. De igual manera, y será cola
propia de z siempre que x no sea la palabra vacía.
Si x = ABC, las
siguientes palabras son cabeza de x : l, A, AB, ABC. Todas ellas
son propias excepto ABC. Colas de x serán : l, C, BC y ABC. Todas ellas
propias excepto ABC.
La función
longitud de una palabra tiene, respecto a la concatenación, propiedades
semejantes a las de la función logaritmo respecto de la multiplicación :
| xy | = | x |
+ | y |
Sea un alfabeto
S. Cada una de
sus letras puede considerarse como una palabra de longitud 1, perteneciente a
W(S). Si a estas
palabras elementales se les aplica la concatenación, puede formarse cualquier
palabra de W(S), excepto la
palabra vacía. Se dice entonces que S es un conjunto
de generadores de W(S) - l.
Este conjunto,
junto con la operación de concatenación, es un semigrupo, pero no un monoide,
ya que carece de elemento neutro.
Si se añade la
palabra vacía a W(S), entonces se
convierte en monoide libre generado por S.
Todo monoide libre cumple la
ley de “cancelación izquierda”, ya que para todo a,b,c Î W(S) se cumple que
ab = ac Þ b = c
·
También se cumple en este caso la ley de “cancelación derecha” :
ac = bc Þ a = b
· Potencia de una palabra
Se trata de una
nueva notación para reducir algunos casos de la operación anterior. Se denomina
potencia i-ésima de una palabra a la concatenación consigo misma i veces. Al
poseer la concatenación la operación asociativa, no es necesario especificar el
orden en que efectuar las concatenaciones.
xi =
xxx...xx
|----------|
i
Evidentemente x1
= x
También resulta
evidente que se cumplen las siguientes relaciones
xi+1
= xix = x xi (i
> 0)
xi xj
= xi+j (i, j > 0)
Para que ambas
relaciones se cumplan también para i, j = 0, basta con definir x0 = l, cualquiera que sea x.
Supongamos que
x = CHJK, entonces
x2 =
xx = CHJKCHJK
____ ____
x3 =
xxx = CHJKCHJKCHJK
____ ____ ____
Monografías
