Principios fundamentales de autómatas y gramáticas

Trabajo profesional que para obtener el
titulo de

Ingeniero en Sistemas
Computacionales

2. Autómatas finitos y
   lenguajes regulares
3. Autómatas de
   pila y lenguajes libres de contexto
4. Autómatas lineales
   y lenguajes sensibles al contexto
5. Máquinas de turing y
   lenguajes recursivos enumerables
6. Aplicaciones a
   lenguajes
7. Bibliografía
8. Glosario
9. Anexos

CAPÍTULO I

INTRODUCCIÓN

Objetivo:

El alumno recordará y aplicará las
operaciones
básicas de conjuntos
así como definirá los elementos de un lenguaje.
Además conocerá la clasificación de las
gramáticas.

1.1. CONJUNTOS.

Un conjunto es una colección de objetos llamados
elementos del conjunto. Si A es un conjunto y a es
un elemento de A utilizaremos la notación
a Î
A (se lee "a es un elemento de A"). Se
usa la notación bÏ A cuando b
no es un elemento de A.

Si A contiene exactamente los elementos
a1, a2, …, an, lo
indicamos escribiendo A= {a1, a2,
…, an}.

Un conjunto sólo se caracteriza por sus elementos
y no por el orden en el cual se listan.

Los conjunto A y B son iguales si
contienen los mismos elementos. Por lo tanto si, A={1,2,3}
y B={2,1,3} se puede escribir que A =
B.

Algunas veces es conveniente describir el contenido
de un conjunto en términos de una propiedad que sea
característica de todos los elementos del conjunto.
Sea P(x) una proposición sobre x. La
notación {x| P(x)}, que se interpreta como "el
conjunto de todas las x tales que P(x)", denota el
conjunto de todos los x para los cuales P(x) es una
proposición verdadera. (Todas las x tienen la propiedad
P).

1.2. OPERACIONES CON CONJUNTOS.

Las operaciones habituales que se definen sobre los
conjuntos son:

El conjunto Æ llamado conjunto vacío
o nulo, no tiene elementos. El conjunto vacío es un
subconjunto de todos los conjuntos.

La unión de conjuntos A y B
se denota por A È B y es un conjunto
formado por los elementos que aparecen en A, en B o
en ambos.

Por lo tanto A È B
={x|xÎ
A ó x Î B}.

Por ejemplo, si A={1, 2, 3} y B= {a, b},
entonces A È B={1, 2, 3, a, b}.

La intersección de A y B es
el conjunto de todos los elementos que aparecen
simultáneamente en A y también en
B.

Por lo tanto A Ç B ={x|xÎ A y x
Î
B}.

Por ejemplo, si A={1, 4, 5, 7} y B= {2, 4,
7, 8}, entonces A Ç B={4, 7}.

El complemento relativo si A y B
son dos conjuntos cualesquiera, el complemento de B con
respecto a A es el conjunto:
A–B={x|xÎ A y xÏ B}.

Por lo tanto, A–B esta compuesto por todos
los elementos de A que no están también en
B. Por ejemplo, si A={0, 2, 4, 6, 8, 10} y
B={0,1, 2, 3, 4}, entonces A–B={6, 8, 10},
mientras que B–A={1, 3}.

2A , el conjunto potencia de A,
es el conjunto formado por todos los subconjuntos de A.
Por ejemplo, sea A={a, b, c} . Entonces 2A
={Æ , {a},
{b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Dados dos conjuntos A y B, su producto
cartesiano, AxB, es el conjunto de todos los
pares ordenados de los que el primer elemento proviene de
A y el segundo de B. Así que,
AxB ={(a, b)|aÎ A y bÎ B}. Por ejemplo, sí
A={1,2,3} y B={5,6} entonces: AxB
={(1,5),(2,5),(3,5),(1,6),(2,6),(3,6)}.

Si A y B son conjuntos y todos los
elementos de A son también elementos de B,
se escribe A Í B y se dice que
A es un subconjunto de B. Por ejemplo
A={1,2,3} y B={0,1,2,3,4,5} , se tiene
A Í
B. Por otro lado, B no es un
subconjunto de A, porque los elementos 0, 4 y 5 de
B no lo son de A.

La Inclusión cuando cualquier elemento de
A que este en B, o cualquier elemento de B que este en A,
ó que sean iguales. Por ejemplo si A={2, 4, 5, 7,
8} y B={2, 4}, entonces AÌ B={2,
4}.

La cardinalidad de un conjunto es el
número de elementos de ese conjunto. Por ejemplo si
A={a, b} entonces |A|=2. La cardinalidad del
conjunto vacío es 0 porque no tiene ningún
elemento.

Para ver el gráfico seleccione la
opción "Descargar" del menú superior

Todos los conjuntos aquí tratados se
consideran subconjuntos de un conjunto universal U. Los
complementos pueden ser formados con respecto a este conjunto
universal. Si A es un conjunto, entonces U- A es el
conjunto de todos los elementos que no están en A.
Conviene denotar tales complementos mediante A, de forma
que U- A = A. Obsérvese que
Æ =U y U =
Æ .

1.3. ALFABETOS.

Un alfabeto es un conjunto no vacío y finito de
símbolos. En el caso del alfabeto inglés,
la colección finita es el conjunto de las letras del
alfabeto junto con los símbolos que se usan para construir
palabras en inglés (tales como el guión, el
apóstrofe y otros por el estilo).

Cada símbolo de un alfabeto es una cadena sobre
dicho alfabeto. La cadena vacía, la cual se denota por el
símbolo e
, es una palabra sobre cualquier alfabeto.

1.4. PROPIEDADES DE LAS CADENAS O
"STRINGS".

Una cadena (ó palabra) es una secuencia finita de
símbolos. Por ejemplo: a, b y c son
símbolos y abcb es una cadena.

1.4.1. Cadena Vacía.

La cadena vacía, denotada por e es la cadena que consiste en
cero símbolos. Por tanto, tiene longitud
|e
|=0.

1.4.2. Longitud.

Si w es una cadena sobre cualquier alfabeto, su
longitud se denota como |w |. La longitud de w es
el número de símbolos que tiene la cadena. Por
ejemplo: abcb tiene longitud |w | =4.

1.4.3. Concatenación.

La concatenación de dos cadenas es la cadena que
se forma al escribir la primera seguida de la segunda, sin que
haya espacio entre ellas. Por ejemplo: si w= "banana" y
z= "rama", la concatenación de w con
z es la cadena "bananarama". La concatenación de
las cadenas w y z se denota como wz ó
w.z. La cadena vacía es la identidad para
el operador de concatenación. Es decir, e w=
we
=w para cada cadena w.

1.4.4. Potencia de
Cadenas.

La noción de potencia de una cadena sobre un
alfabeto es dada por la notación wk que denota
la concatenación de k copias de la cadena w.

Por tanto, si w=122 sobre el alfabeto S ={1, 2}, se tiene

w0 = e

w1 = 122

w2 = 122122

w3 = 122122122

1.4.5. Igualdad de
Cadenas.

Si w y z son cadenas, se dice que w es igual a z, si
tienen la misma longitud y los mismos símbolos en la misma
posición. Se denota mediante w =z.

1.4.6. Prefijo.

Los prefijos de una cadena están formados por los
primeros símbolos de ésta. Por ejemplo, la cadena
121 sus prefijos son: e , 1, 12 y 121, con lo que toda palabra puede
considerarse prefijo de sí misma. Un prefijo de una cadena
que no sea la misma cadena es un prefijo propio.

1.4.7. Sufijo.

Los sufijos de una cadena están formados por los
últimos símbolos de está. Por ejemplo, la
cadena abc sus prefijos son: e , c, bc y abc. Un sufijo de una cadena que no
sea la misma cadena es un sufijo propio.

1.4.8. Subcadena.

Una cadena w es una subcadena o subpalabra de otra
cadena z si existen las cadena x e y para las cuales z=
xwy.

1.4.9. Transpuesta.

La inversa o transpuesta de una cadena w es la imagen refleja de
w. Por ejemplo, si w = "able" entonces su inversa es "elba". Para
denotar la inversa de w se usa wI.

1.5. REPRESENTACIÓN FINITA DEL
LENGUAJE.

Un alfabeto es un conjunto finito de
símbolos.

Un lenguaje (formal) es un conjunto de cadenas de
símbolos tomados de algún alfabeto. El conjunto
vacío, Æ
y el conjunto formado por la cadena vacía
{e } son
lenguajes. Nótese que son diferentes: el último
tiene un elemento, mientras que el primero no. El conjunto de
Palíndromos (cadenas que se leen igual de izquierda a
derecha y viceversa) sobre el alfabeto {0,1} es un lenguaje
infinito. Algunos elementos de este lenguaje son
e , 0, 1, 00, 11, 010 y
1101011.

Otro lenguaje es el conjunto de cadenas sobre un
alfabeto fijo S
. Denotamos a este lenguaje como S * llamado como la cerradura de Kleene o
cerradura de estrella de un lenguaje. Las cadenas de la cerradura
de Kleene se forman al realizar cero o más concatenaciones
de las cadenas del alfabeto, mientras que la cerradura positiva
se forma al realizar una o más concatenaciones. Por
ejemplo si S
={a}, entonces tenemos que S 0= {e }, S 1={a}, S 2= {aa} y así
sucesivamente. Por tanto S *= {e , a, aa, aaa,…}. Por otro lado,
S += {a, aa,
aaa,…}.

1.6. CLASIFICACIÓN DE LAS
GRAMÁTICAS.

En 1959, Noam Chomsky clasificó las
gramáticas en cuatro tipos de lenguajes y esta
clasificación es conocida como la jerarquía de
Chomsky, en la cual cada lenguaje es descrito por el tipo de
gramática generado. Estos lenguajes sirven
como base para la clasificación de lenguajes de
programación. Los cuatro tipos son: lenguajes
recursivamente enumerables, lenguajes sensibles al contesto,
lenguajes libres de contexto y lenguajes regulares. Dichos
lenguajes también se identifican como lenguajes de tipo o,
1, 2 y 3.

Existe una exacta correspondencia entre cada uno de
estos tipos de lenguajes y particulares arqitecturas de máquinas
en el sentido que por cada lenguaje de tipo T hay una
arquitectura
de máquina A que reconoce el lenguaje de
tipo T y por cada arquitectura A hay un tipo
T tal que todos los lenguajes reconocidos por A son
de tipo T. La correspondencia entre lenguajes y
arquitectura son mostrados en la siguiente tabla, la cual
también indica el capítulo de donde se explican
más a fondo, figura 1.1.

Figura 1.1. Los cuatro tipos de
Gramáticas.

La relación entre los lenguajes es descrita a
continuación:

Sobre un alfabeto dado, el conjunto de los lenguajes
recursivamente enumerables contiene propiamente al conjunto de
los lenguajes recursivos que contiene propiamente al conjunto de
los lenguajes sensibles al contexto que contiene propiamente al
conjunto de lenguajes libres de contexto, que a su vez contiene
propiamente a los lenguajes regulares.

EJERCICIOS.

* Ejercicio resuelto.

*1.1. Sean A y B dos lenguajes sobre S . Probar las siguientes
afirmaciones:

a) A – B = A Ç B.

b) (A È B) = A Ç B.

a) A – B = A Ç B.

Un elemento x satisface

xÎ
A – B Û
xÎ A
y xÏ
B

Û
xÎ A
y x Î
B

Û
xÎ
A Ç
B

Por lo tanto A – B = A Ç B.

b) (A È B) = A Ç B.

Un elemento x satisface

xÎ
A È
B Û
xÏ
AÈ
B

Û
xÎ A
y xÏ
B

Û
xÎ A
y xÎ
B

Û
xÎ
A Ç
B

Por lo tanto (A È B) = A Ç B.

1.2. Probar o refutar las siguientes
afirmaciones:

a) Si A È B = A È C, entonces B = C

b) Si A Ç B = A Ç C, entonces B = C

1.3. Demostrar las siguientes igualdades:

A È
(B È
C) = (A È
B) È
C.

A È
(B Ç
C) = (A È
B) Ç
(A È
C).

*1.4. Si A={rojo, verde, azul}, B={verde, violeta} y
C={rojo, amarillo, azul, verde}. Determine los elementos en
(A Ç C) x
(B – C).

A Ç
C = {rojo, verde, azul}

B – C = {violeta}

(A Ç
C) x (B – C) = {(rojo, violeta), (verde, violeta), (azul,
violeta)}

*1.5. Demuestre la siguiente igualdad A – B = A –
(B Ç A),
utilizando los siguientes conjuntos: A={a, d, e. f, g} y B={d, g,
h, j}

B Ç
A = {d, g}

A – (B Ç A) = {a, e, f}

A – B = {a, e, f}

Por lo tanto A – B = A – (B Ç A)

1.6. Demuestre la siguiente igualdad (A – B) – C = (A –
C) – (B – C) = A – (B È C), utilizando conjuntos a su libre
albedrio.

*1.7. ¿De qué conjunto de símbolos
se derivan las frases inglesas?

Las frases inglesas se derivan del alfabeto
inglés, que esta formado por veintiseis
símbolos.

*1.8. ¿Por qué el lenguaje
vacío Æ
no es el mismo que {e }?

Dado que el lenguaje es un conjunto de cadenas, se puede
tener el lenguaje compuesto por ninguna cadena (el lenguaje
vacío). Este no es el mismo lenguaje que el que consta de
la cadena vacía {e }.

1.9. Obtener todos los prefijos y sufijos de la palabra
w="bar" sobre el alfabeto inglés.

1.10. Sea A={la, mi} y B={calza, caballo, casa}. Obtener
A.B, A.A y A.B.B.

1.11. ¿Bajo qué condiciones
A*=A+?

*1.12. Probar que {e }*={e }={e }+.

Si S
={e
}

Las cadenas de la cerradura de Kleene S *=S n donde n³ 0 entonces tenemos que S 0={e }, S 1={e }, S 2={e e } y
así sucesivamente.

Por lo tanto S *= {e , e
, e e , e e
e , …}, sigue siendo
{e }.

Por otro lado, la cerradura positiva S +=S n donde
n³ 1,
entonces tenemos S
+= {e
, e e , e e
e , …}, que sigue
siendo {e
}.

Por lo tanto {e }*={e }={e }+.

*1.13. En terminos de la cerradura de kleene y la
cerradura positiva, describa que cadenas se obtienen a partir del
siguiente lenguaje: 0(0*10*)+.

Conjunto de cadenas binarias que empiezan con 0 y que
contienen al menos un 1.

1.14. En terminos de la cerradura de kleene y la
concatenación de cadenas, describa los lenguajes que
contengan los siguientes enunciados:

a) Cadenas sobre {0, 1} que empiecen con 01.

b) Cadenas que comiencen con 0, alternando entre 0 y
1.

AUTÓMATAS FINITOS Y

LENGUAJES REGULARES

Objetivo:

El alumno conocerá la fundamentación de
los autómatas finitos, aprenderá a construir
autómatas finitos determinísticos, autómatas
no determinísticos y autómatas no
determinísticos con movimiento e y relacionará dichos autómatas
con expresiones regulares.

2.1. AUTÓMATAS FINITOS DETERMINÍSTICOS
(DFA’S).

Las características de los autómatas finitos
determinísticos son:

1. Un conjunto finito de estados y un conjunto de
   transiciones de estado a
   estado, que se dan sobre símbolos de entrada tomados de
   un alfabeto S
   .
2. Para cada símbolo de entrada existe
   exactamente una transición a partir de cada estado
   (posiblemente de regreso al mismo estado).
3. Un estado, por lo general denotado como q0
   es el estado
   inicial, en el que el autómata comienza.
4. Algunos estados (tal vez ninguno) están
   designados como final o de aceptación.

Un autómata finito determinístico es
una quinta tupla (Q, S , d
, q0, F) donde:

Q es un conjunto finito de
estados.

S un alfabeto
de entrada finito.

q0 elemento de Q , el estado
inicial.

FÍ Q el conjunto de estados finales o
de aceptación.

d es la
función d : Q x S ® Q
que determina el único estado siguiente para el par
(q1, s
) correspondiente al estado actual q1 y la
entrada s
.

Generalmente el término autómata finito
determinístico se abrevia como DFA de sus siglas en
inglés Deterministic Finite Automaton. Usaremos M =
(Q, S ,
q0, F, d
) para indicar el conjunto de estados, el alfabeto, el
estado inicial, el conjunto de estados finales y la
función asociadas con el DFA M.

Se puede construir un diagrama para
que ayude a determinar los distintos miembros o cadenas del
lenguaje. Tal diagrama tiene la forma de un grafo dirigido con
información añadida, y se llama
diagrama de transición. Los nodos del grafo corresponden a
los estados del DFA y se usan para señalar, en ese
momento, hasta qué lugar se analizó la cadena. Por
lo general q0 es el estado inicial, marcando con una
flecha (® ),
el comienzo del autómata; algunos estados están
designados como final o aceptación indicados por un doble
círculo. Los símbolos del alfabeto son las
etiquetas de los arcos del grafo. Si cuando ha sido tratada la
cadena en su totalidad se termina en un estado de
aceptación entonces la cadena es aceptada por el lenguaje.
Si M es un AFD, entonces el lenguaje aceptado por M es
L(M)={w Î
S *½ w es aceptada por M}. Por
tanto, L(M) es el conjunto de cadenas que hacen que M pase de su
estado inicial a un estado de aceptación.

Ejemplo: El lenguaje que acepta el DFA esta formado por
todas las cadenas sobre el alfabeto S = {a, b}, siempre y cuando terminen con
a.

Figura 2.1.

Q = {q0, q1}, S = {a, b}, q0 =
q0 , F = {q1} y d se define mediante la tabla de la figura
2.1.

Se puede utilizar también la siguiente lista para
definir la función d

(q0, a) = q1(q0, b) =
q0

(q1, a) = q1(q1 ,b) =
q0

El diagrama de transición se muestra en la
figura 2.2.

Para ver el gráfico seleccione la
opción "Descargar" del menú superior

Consideremos otro ejemplo. El DFA M= {Q,
S , q0,
F, d } acepta el
lenguaje L(M)={w Î {a, b}* que no contiene tres b’s
consecutivas} y esta representada por:

Q={q0, q1, q2,
q3}

S ={a, b}

q0=q0

F={q0, q1,
q2}

y d
dada por la tabla de la figura 2.3.

Figura 2.3.

El diagrama de transición correspondiente se
muestra en la figura 2.4.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

2.2. AUTÓMATAS FINITOS NO
DETERMINÍSTICOS (NFA’S).

Un autómata finito no determinístico es una
quinta tupla ( Q, S
, q0, d , F) en donde Q, S , q0 y F (estados, entradas,
estado inicial y estados finales) poseen el mismo significado que
para un DFA, pero en este caso d es una transformación de Q x
S a 2Q.
(Recuérdese que 2Q es el conjunto de potencias
de Q, el conjunto de todos los subconjuntos de Q).
Obsérvese que puesto que d es una relación para todo
par (q, s )
compuesto por el estado actual y el símbolo de la
entrada, d
(q, s ),
es una colección de cero o más estados [es
decir, d
(q, s
)Í
Q]. Esto indica que, para todo estado q1 se
pueden tener cero o más alternativas a elegir como estado
siguiente, todas para el mismo símbolo de
entrada.

Generalmente el término autómata finito no
determinístico se abrevia como NFA de sus siglas en
inglés Nondeterministic Finite Automaton. Si M es un NFA,
definiremos el lenguaje acepatdo por M por medio de
L(M)={w ½
w es una cadena aceptada por M} donde una cadena w es
aceptada por M, si M pasa de su estado inicial a su estado de
aceptación o final al recorrer w (w es consumida en su
totalidad).

Observe ahora el diagrama de transición de la
figura 2.5

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

El NFA descrito anteriormente acepta el lenguaje formado
por cualquier número (incluyendo el cero) de a’s,
concatenadas a una "b" ó una "a" concatenada a cualquier
numero (incluyendo el cero) de b’s . Se representa de la
siguiente forma:

Q={q0, q1, q2,
q3, q4}

F={q2, q3,
q4}

q0=q0

S ={a, b}

Y d
dada por la tabla de la figura 2.6.

Figura 2.6.

Obsérvese que en el contenido de las celdas de la
tabla de transición de la figura 2.6 son conjuntos. El
hecho de que existan celdas con Æ , indica que no existe ninguna
transición desde el estado actual mediante la entrada
correspondiente. Que para un par (estado actual, entrada)
exista más de un posible estado siguiente indica que se
puede elegir entre las distintas posibilidades. En el modelo no
existe nada que determine la elección. Por esta
razón, se dice que el comportamiento
del autómata es no determinista.

Veamos otro ejemplo. Consideremos el NFA M={ Q,
S , q0,
F, d } que
acepta el lenguaje formado por cadenas que tienen cero o
más ocurrencias de "ab" ó "aba" y esta dado
por:

Q={q0, q1,
q2} S
={a, b}

q0=q0F={q0}

Figura 2.7.

Y d
dada por la tabla de la figura 2.7. Este NFA tiene el
correspondiente diagrama de transición que se muestra en
la figura 2.8.

Para ver el gráfico seleccione la
opción "Descargar" del menú superior

Figura 2.8.

2.3. AUTÓMATAS FINITOS NO
DETERMINÍSTICOS CON MOVIMIENTO e (NFA- e ).

Un autómata finito no determinístico con
movimiento e
(entrada vacía) es como la quinta tupla ( Q,
S , d , q0, F) con todos
sus componentes igual que a un NFA, con excepción
de d , la
función de transición, que ahora transforma Q x
(S È {e }) a 2Q; para incluir transiciones
de un estado a otro que no dependan de ninguna entrada. Se puede
añadir una columna en la tabla de d para colocar los pares de la
forma (qi, e ). Cuando hay e -transiciones en un NFA es conveniente suponer
que cada estado tiene una e -transición que cicla en ese
estado.

Observe el ejemplo del diagrama de transición de
la figura 2.9, que acepta el lenguaje consistente en cualquier
número (incluyendo el cero) de 0’s seguidos por
cualquier número de 1’s seguido, a su vez, por
cualquier número de 2’s y cuya tabla de
transición es mostrada por la figura 2.10.

  Para ver el gráfico
seleccione la opción "Descargar" del menú
superior

Figura 2.9.

Figura 2.10.

Veamos otro ejemplo con el diagrama de transición
de la figura 2.11 que acepta el lenguaje formado por cadenas que
tienen cero o más ocurrencias de "ab" ó
"aba".

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 La figura 2.11 tendría la tabla de
transición de la figura 2.12

Figura 2.12.

2.4. EXPRESIONES REGULARES.

Los lenguajes aceptados por un autómata finito se
describen con facilidad mediante expresiones simples llamadas
expresiones regulares.

Sea S
un alfabeto. La expresión regular sobre
S y los conjuntos que
denotan se definen de manera recursiva como sigue:

1. Æ es una
   expresión regular y denota al conjunto
   vacío.
1. e es
   una expresión regular y denota al conjunto
   {e
   }.
1. Para cada a Î S
   , a es una expresión regular y denota al conjunto
   {a}.
1. Si r y s son expresiones regulares que
   denotan a los lenguajes R y S.; respectivamente, entonces
   tenemos lo siguiente:

r+s es una expresión regular que denota a los
conjuntos R È
S.

(r) es una expresión regular que denota al
conjunto R.

rs es una expresión regular que denota a los
conjuntos RS.

r* es una expresión regular que denota al
conjunto R*.

r+ es una expresión regular que denota
al conjunto R+.

ri es una expresión regular que
denota al conjunto Ri.

Ejemplo de Autómatas con sus expresiones
regulares

El lenguaje del autómata de la figura 2.13. esta
formado por cualquier cadena de 1’s, incluyendo
e .

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 Figura 2.13. La expresión regular del
autómata es: 1*

El lenguaje del autómata de la figura 2.14. esta
formado por todas las cadenas de a’s de longitud par,
incluyendo e
.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 Figura 2.14. La expresión regular del
autómata es: (aa)*

El lenguaje del autómata de la figura 2.15. esta
formado por cadenas de cero ó más a’s
seguidas de cero ó más b’s.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 Figura 2.15. La expresión
regular del autómata es: a*b*.

Existen muchas equivalencias con respecto a expresiones
regulares basadas en las correspondientes igualdades de
lenguajes. Por ejemplo sean r, s y t expresiones regulares sobre
el mismo alfabeto S
. Entonces:

1. r + s = s + r
2. (rs)t = r(st)
3. (r + s)t = rt + st
4. (r*)* = r*
5. r(s + t) = rs + rt

2.5. LENGUAJES REGULARES.

Los lenguajes regulares pueden ser usados en la construcción de analizadores léxicos
– programas que
analizan un texto y
extraen los lexemas ( o unidades léxicas) que hay en el
mismo -.

El conjunto de los lenguajes regulares sobre un
alfabeto S esta
formado por el lenguaje vacío, los lenguajes unitarios
incluido {e } y
todos los lenguajes obtenidos a partir de la
concatenación, unión y cerradura de estrella de
lenguajes.

Ejemplo de lenguajes regulares:

Cuando sea necesario distinguir entre una
expresión regular r y el lenguaje denotado por la misma,
usaremos L(r) para denotar el lenguaje. En cualquier caso, si se
afirma que w Î
r, ello equivale a decir que w Î (r). Si r y s son expresiones
regulares sobre el mismo alfabeto y si L(r)= L(s), entonces se
dice que r y s son equivalentes. En el caso de que r y s sean
equivalentes se puede escribir r= s. También se puede usar
rÍ s en
el caso de que L(r) Í L(s).

2.6. FUNCIONES
RECURSIVAS.

Una definición recursiva esta caracterizada por
un proceso de
tres pasos:

1. Declaración de los objetos básicos que
   pertenecen al lenguaje (caso base).
2. Otorgar las reglas para construir más objetos
   a partir de los existentes (caso recursivo).
3. Declarar que ningún otro objeto fuera de las
   dos reglas anteriores forman parte del lenguaje "Requisito de
   formalidad".

Ejemplo: Encontrar una definición recursiva para
el lenguaje de todos los números enteros divisibles a
través de 2, es decir, EVEN= {2, 4, 6, 8, …}.

1. 2 Î
   EVEN.
2. x Î
   EVEN entonces x+2 Î EVEN.
3. Ningún otro número que no sea obtenido
   por la regla 1 y la regla 2 Î EVEN.

Para explicar está definición se recorre
la función recursiva, para demostrar que el número
14 Î
EVEN:

Por la regla 1 2Î EVEN

Por la regla 2 2+2=4 Î EVEN

Por la regla 2 4+2=6 Î EVEN

Por la regla 2 6+2=8 Î EVEN

Por la regla 2 8+2=10 Î EVEN

Por la regla 2 10+2=12 Î EVEN

Por la regla 2 12+2=14 Î EVEN

El anterior recorrido queda más claro mediante
figura 2.16.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 Figura 2.16. Recorrido de la función
recursiva, para demostrar que el número 14
Î
EVEN.

Sin embargo, la anterior definición recursiva no
es la única, pueden adaptarse otras, por
ejemplo:

1. 2 Î
   EVEN.
2. X,Y Î EVEN entonces X+Y Î EVEN.
3. Ningún otro número Î EVEN.

El recorrido de la función recursiva para el
número 14 quedaría de la siguiente
forma:

Por la regla 1 2Î EVEN

Por la regla 2 x=2, y=2 entonces 2+2=4
Î EVEN

Por la regla 2 x=2, y=4 entonces 2+4=6
Î EVEN

Por la regla 2 x=4, y=4 entonces 4+4=8
Î EVEN

Por la regla 2 x=6, y=8 entonces 6+8=14
Î EVEN

Esta segunda definición recursiva es mejor que la
primera porque se obtiene el resultado en un menor número
de pasos como se observa en la figura 2.17.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 Figura 2.17. Recorrido de la segunda
función recursiva, para demostrar que el número
14 Î
EVEN.

La definición recursiva que se obtenga
dependerá de dos casos:

1. Que tan fácil de entender es la
   definición recursiva.
2. Los tipos de teoremas que se desean
   demostrar.

2.7. PUMPING LEMMA O LEMA DE BOMBEO PARA LENGUAJES
REGULARES.

Si L es un lenguaje finito, es regular y se podrá
construir un autómata finito o una expresión
regular para ellos de forma sencilla. También, si L
es especificado ya sea por medio de un autómata finito o
una expresión regular, la respuesta es obvia. Por
desgracia, hay relativamente pocos lenguajes que sean regulares
y, en el caso de un lenguaje infinito, la búsqueda
exhaustiva de una expresión regular o un autómata
finito puede resultar inútil. En este caso, se necesita
obtener algunas propiedades que compartan todos los lenguajes
regulares infinitos y que no estén presentes en los
lenguajes regulares.

Supongamos que un lenguaje es regular y que, por tanto,
es aceptado por un DFA M=(Q, S , q0, d , F), donde Q contiene n estados.
Si L(M) es infinito, podremos encontrar cadenas cuya
longitud sea mayor que n. Supongamos que w=
a1, a2,
…,an+1 es una de las cadenas de
longitud n+1 que pertenecen a L(M).

Si tuviéramos

q1= d (q0, a1)

q2= d (q1, a2)

y así sucesivamente, obtendríamos los
n+1 estados, q1, q2 ,…,
qn+1. Puesto que Q contiene
sólo n estados , los qi no
serán todos distintos. En consecuencia, para
algunos índices j y k, con
1£
j £ n+1, se obtendrá
que qj= qk. Por lo tanto,
tendremos un ciclo en el camino que parte de q0 hasta
un estado de aceptación según se muestra en la
figura 2.18.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 Figura 2.18.

Puesto que j< k, se tiene que la "parte
central", es decir,
aj+1…ak, tiene
al menos longitud 1. Obsérvese además que la cadena
w’= a1… aj
ak+1…an+1
debe pertenecer también a L(M). Por esto, se puede
dar vueltas en el ciclo tantas veces como se quiera, de forma que
a1… aj
(aj+1…ak)m
ak+1…an+1
estará en L(M) para todo m³ 0. Es decir, se puede
"bombear" cero o más veces la parte central y seguir
teniendo una cadena que sea aceptada por el
autómata.

El lema de bombeo se define de la siguiente
forma:

Sea L un lenguaje regular infinito. Entonces hay
una constante n de forma que, sí w es una
cadena de L cuya longitud es ³ n, se tiene que w=uvx,
siendo uvixÎ L para todo
i ³
0, con |v| ³ 1 y |uv| £ n.

El lema de bombeo facilita una forma de determinar si un
lenguaje es regular; de esta forma se podrá decir si es
finito y por ello se podrá construir un autómata
finito o una expresión regular dada la conexión que
existe entre ambos. Recordemos que un lenguaje regular es
generado por una expresión regular (para mayor
comprensión del tema ver la sección de lenguajes
regulares de este capítulo). Para demostrar que un
lenguaje no es regular, se mostrará que, cualquier
valor n
lo bastante grande, se tendrá al menos una cadena de
longitud n o mayor que falle al ser "bombeada".

• Por ejemplo: Considérese el lenguaje
  L={a i | i
  ³
  1}
• Toda cadena L debe tener una longitud que sea
  un cuadrado perfecto. Supongamos que L es regular y sea
  n la constante dada en el lema de bombeo.
  Obsérvese que an Î L y que, por el
  lema de bombeo, tenemos an = uvx de
  forma que 1£
  |v| £ n y
  uvix Î L para todo i
  ³ 1. Entonces se
  obtiene que:

n2 = |uvx|

< |uv2x|

£
n2 + n

< (n+1)2

Es decir, la longitud de uv2x
se encuentra, estrictamente, entre cuadrados perfectos
consecutivos y, por tanto, no es un cuadrado perfecto. Luego
uv2x no puede pertenecer a L. Es
decir, L no puede ser regular.

EJERCICIOS.

* Ejercicio resuelto.

*2.1. Describa el lenguaje aceptado por el DFA
representado por el diagrama de transición de la figura
2.19

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 Figura 2.19.

El lenguaje esta formado por cadenas que tienen cero o
más ocurrencias de "ab" y su expresión regular es
(ab)*.

2.2. Construya el diagrama de transición y
describa el lenguaje que acepta el siguiente autómata
finito determinístico: Sea M={Q, S , q0, F, d } dado por:

Q =
{q0,q1,q2,q3} S = {0,1}

F = {q0} q0 =
q0

y d
dada por la tabla de la figura 2.20.

Figura 2.20.

2.3. Proporcione los DFA’S que acepten los
siguientes lenguajes sobre el alfabeto {0,1}:

a) El conjunto de todas las cadenas que terminen en
00

b) El conjunto de todas las cadena que posean tres
0’s consecutivos.

*2.4. Dado S
={0, 1} construya el diagrama (ver figura 2.21.) y tabla de
transición (ver figura 2.22) para el NFA que acepte el
lenguaje formado por todas las cadenas que contengan dos ceros
ó dos unos consecutivos.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 Figura 2.21.

Figura 2.22.

2.5. Sea M el NFA dado por Q = {q0,
q1}, S ={a,b},
q0= q0, F={q1} y
d dada en la figura
2.23. Determinar si la cadena "ba" estan en L(M). Dibujar el
diagrama de transición para M.

Figura 2.23.

*2.6. Construya los diagramas de
transición para los NFA con movimiento e y describa su
lenguaje.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

2.7. Construya la tabla de transición y describa
el lenguaje que acepta el NFA con movimiento e , dado el diagrama de
transición de la figura 2.24.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 *2.8. Encontrar las expresiones regulares
correspondientes a las figuras 2.25, 2.26, 2.27 y 2.28

  Para ver el gráfico
seleccione la opción "Descargar" del menú
superior

Figura 2.25.

 Para ver el gráfico
seleccione la opción "Descargar" del menú
superior

Figura 2.26.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Figura 2.27.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Figura 2.28.

*2.9. Describa los lenguajes de las siguientes
expresiones regulares:

2.10. Representar por medio de diagramas de
transición los DFA’s que acepten las expresiones
regulares del ejercicio 2.9.

2.11. Obtener la expresión regular que representa
al lenguaje formado por todas las cadenas sobre
S ={a, b} que tienen un
número par de b’s y construya por medio de un
diagrama de transición su DFA.

2.12. Demuestre por medio de un recorrido, que la
siguiente definición recursiva pertenece también al
conjunto EVEN = {2, 4 ,6 ,8 , …}.

1. 2 y 4 Î EVEN.
2. Si x Î EVEN, entonces también
   x+4 Î
   EVEN.

*2.13. Encontrar una función recursiva para el
lenguaje generado por una o mas x, es decir, L= x+ =
{x, xx, xxx, …}

1. X Î
   L.
2. Q Î
   EVEN entonces XQ Î L.
3. Ninguna otra cadena que no sea obtenida por la regla
   1 y la regla 2 Î L.

*2.14. Encontrar una función recursiva para el
lenguaje palíndrome sobre {0,1}, es decir, PAL =
{e , 0, 1, 11,
00, 111, 000, 101, 010, …}.

1. e , 0, 1
   Î
   PAL.
2. X Î
   PAL entonces 1X1 Î PAL.
3. X Î
   PAL entonces 0X0 Î PAL.
4. Ninguna otra cadena Î PAL.

2.15. Encontrar una función recursiva para el
lenguaje generado por una o mas x, es decir, L= x* =
{e , x, xx, xxx,
…}

CAPÍTULO III

AUTÓMATAS DE PILA Y

LENGUAJES LIBRES DE CONTEXTO

Objetivo:

El alumno entenderá la fundamentación
de lenguajes libres de contexto. Aprenderá a construir
gramáticas libres de contexto que definan un lenguaje y su
notación BNF, además de aprender a utilizar los
autómatas de pila.

3.1. AUTÓMATAS DE PILA O PUSH -DOWN
(PDA).

Un autómata de pila o Push-Down es un
autómata que cuenta con un mecanismo que permita almacenamiento
ilimitado y opera como una pila.

El autómata de pila (se abrevia PDA de sus siglas
en inglés Push-Down Autómata) tiene una cinta de
entrada, un control finito y
una pila. La pila es una cadena de símbolos de
algún alfabeto. El símbolo que se encuentra
más a la izquierda se considera como que está en la
"cima". El dispositivo será no determinístico y
tendrá un número finito de alternativas de
movimiento en cada situación ver figura 3.1.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Figura 3.1 Autómata de
pila.

 Los movimientos serán de dos tipos. En el
primer tipo de movimiento se utiliza un símbolo de
entrada. Dependiendo del símbolo de entrada, del
símbolo de la cima y el estado de control finito, es
posible un número de alternativas.

Cada alternativa consiste en un estado posterior para el
control finito y una cadena (posiblemente vacía) de
símbolos, para sustituir al símbolo que se
encuentra en la cima de la pila. Después de seleccionar
una alternativa, la cabeza de entrada avanza un símbolo
como se ilustra en la figura 3.2.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior  

Figura 3.2 Avance de un símbolo de
entrada (q1, c, B), a un estado posterior

y sustitución de la cima de la
pila {(q2, B)}.

El segundo tipo de movimiento conocido como
movimiento e es
parecido al primero, excepto que el símbolo de entrada no
se utiliza y la cabeza de la entrada no avanza después del
movimiento. Este tipo de movimiento permite al PDA manipular la
pila sin leer símbolos de entrada como se muestra en la
figura 3.3.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Figura 3.3 Manipulación de la pila
sin leer símbolo de entrada.

Existen dos modos de aceptar un lenguaje por un
autómata de apilamiento. El primero consiste en definir el
lenguaje aceptado como el conjunto de todas las entradas para las
cuales una sucesión de movimientos ocasiona que el
autómata de pila vacíe su pila.

La segunda manera es designando algunos estados como
estados finales y definimos el lenguaje aceptado como el conjunto
de todas las entradas para las cuales alguna selección
de movimiento ocasiona que el autómata de pila accese un
estado final.

Un autómata de pila M es un sistema
(Q, S
, G
, d ,
q0, Z0, F), en donde:

Q es un conjunto finito de
estados.

S es el
alfabeto llamado alfabeto de entrada.

G es el
alfabeto, conocido como alfabeto de pila.

q0 Î Q, es el estado
inicial.

Z0 Î G ,
es el símbolo llamado símbolo inicial.

F Í Q es el conjunto de estados
finales.

d es una
transformación de Q x (S È
a {e }) x G en los subconjuntos finitos Q x
G *.

Sea M=(Q, S
, G
, d ,
q0, Z0, F) un autómata de pila. El
lenguaje aceptado por M se denota por L(M) y es el conjunto L(M)
= {wÎ
S *½ ( q0, w,
Z0) * (p, e
, u ) para pÎ F y uÎ G
*}.

Nota: * se usa para denotar los movimientos con un
número arbitrario de pasos, donde * indica "cero o
más pasos".

Obsérvese que la aceptación requiere que M
se mueva a un estado final cuando la cadena w se agote. M puede
terminar o no con la pila vacía. (Sin embargo,
obsérvese que cuando la pila se vacía el PDA debe
parar, ya que todas las transiciones requieren un símbolo
de pila).

El siguiente ejemplo representa un autómata de
pila que acepta a {wcwR|wÎ (0+1)*} mediante un agotamiento de
pila M=(Q, S
, G
, d ,
q0, Z0, F). Donde:

Q = {q1, q2} q0 =
q1

S = {0, 1,
C} Z0 = R

G = {R, B, G} F
= Æ

y d
está definida por:

1. d (q1,
   0, R) = {(q1, BR)}
2. d (q1,
   0, B) = {(q1, BB)}
3. d (q1,
   0, G) = {(q1, BG)}
4. d (q1,
   c, R) = {(q2, R)}
5. d (q1,
   c, B) = {(q2, B)}
6. d (q1,
   c, G) = {(q2, G)}
7. d (q2,
   0, B) = {(q2, e )}
8. d
   (q2, e , R) = {(q2, e )}
9. d (q1,
   1, R) = {(q1, GR)}

10. d (q1,
    1, B) = {(q1, GB)}
11. d (q1,
    1, G) = {(q1, GG)}
12. d (q2,
    1, G) = {(q2, e )}

Analizando la cadena 01C10 usando el PDA anterior se
obtiene lo siguiente:

(q1, 01C10, R) por la regla 1
® (q1,
1C10, BR) por la regla 10 ® (q1, C10, GBR) por la regla
6 ®
(q2, 10, GBR) por la regla 12 ® (q2, 0, BR) por
la regla 7 ®
(q2, e , R) por la regla 8 ® (q2, e , e ) y se agota la pila.

Consideremos el siguiente ejemplo de autómata de
pila definido por:

Q = {q1, q2, q3,
q4}

S = {a,
b}

G = {A,B}

Z0 = A

F = {q4}

q0=q1

y d
dado por la siguiente tabla:

Ya que d
depende del estado actual, el símbolo de entrada
actual y el símbolo actual de la cima de la pila, la tabla
tiene filas que corresponden a los estados y columnas que
corresponden a los pares de símbolos de entrada y de la
pila.

Obsérvese que no hay transiciones para todas las
ternas posibles de estado, símbolo de entrada y
símbolo de pila. Por lo tanto, si el PDA pasa a un estado
para el cual no se especifica un estado siguiente y una acción
de la pila para los símbolos actuales de la pila y la
entrada, el PDA no puede volver a realizar ningún
movimiento. En particular, cuando el autómata está
en el estado q4, que es el estado de
aceptación, no hay ninguna transición sea cual sea
el símbolo de la cima y de la entrada.

Si el PDA se mueve al estado q2, entonces
obsérvese que cada vez que a aparece en la entrada
se apila una B en la pila. El PDA permanece en el estado
q2 hasta que se encuentra la primera b y
entonces se mueve al estado q3, ninguna b puede
preceder a una a. Finalmente, en el estado q3
sólo se consideran las b’s y, cuando se
encuentra cualquier b, se desapila B de la pila.
(Sólo pueden desapilarse las B’s que fueron
apiladas, debido a encontrarse una a en la
entrada).

Las únicas cadenas que acepta el PDA pertenecen
al lenguaje {an bn | n³ 0}È {a}, puesto que son las
únicas cadenas de entrada que, una vez que han sido
consumidas, causan que el PDA termine en el estado final
q4.

3.2. GRAMÁTICAS LIBRES DE CONTEXTO
(CFG’S).

Las gramáticas libres de contexto amplían
la capacidad para especificar lenguajes al incluir algunos
lenguajes que no son reconocidos por un autómata
finito.

Las gramáticas libres de contexto son
útiles para describir expresiones aritméticas que
tengan una anidación arbitraria de paréntesis
balanceados y estructuras de
bloque en los lenguajes de programación.

Las características de las gramáticas
libres de contexto son:

1. Un alfabeto S de caracteres llamados símbolos
   terminales con los cuales se obtienen cadenas que forman las
   palabras de un lenguaje.
2. Un conjunto de símbolos no terminales, uno de
   los cuales es el símbolo S conocido como símbolo
   inicial.

3. Un conjunto finito de producciones de la
   forma

Un no terminal ® cadenas finitas de terminales y/o no
terminales.

Donde las cadenas de terminales y/o no terminales pueden
tener solo terminales, solo no terminales, o cualquier
combinación de terminales y no terminales o incluso a la
cadena vacía. Se requiere al menos una producción que tenga el no terminal S del
lado izquierdo.

Por lo general los no terminales se representan por
letras mayúsculas mientras que los terminales se designan
por letras minúsculas y símbolos
especiales.

Una gramática libre de contexto (se abrevia
CFG de sus siglas en inglés Context-Free Grammar) es una
4-tupla G=(V, T, P, S) donde:

V es una colección finita de
símbolos no terminales

T es un alfabeto (también conocido como
conjunto de símbolos terminales)

VÇ T=Æ no tienen símbolos
comunes.

P es un conjunto finito de producciones, cada
producción es de la forma A ® a
, en donde A es una variable y a es una cadena de símbolos tomados
de (VÈ
T)*.

S es una variable conocida como símbolo
inicial.

El lenguaje generado por la gramática libre de
contexto G se denota por L(G) y se llama lenguaje libre de
contexto (se abrevia CFL de sus siglas en inglés
Context-Free Language).

Por ejemplo la siguiente gramática genera el
lenguaje a n donde n ³ 1.

S ®
a

S ®
aS

Donde:

V= {S}, T= {a}, S= S y P= {S ® a, S ® aS}

Otro ejemplo: Diseñe una CFG que genere el
lenguaje 0n12n | n ³ 1.

S ®
011

S ®
0S11

El lenguaje generado por una gramática se
demuestra con el siguiente ejemplo:

V= {S}, T= {a, b}, P= {S ® aSb, S ® ab} y S= S

Usaremos la notación Þ para indicar el acto de generar
(como opuesto a ®
, el cual es parte de una regla de producción).
Cuando derivamos una cadena, los no terminales representan la
parte de la cadena que todavía no se ha generado, puede
haber más de un trozo no generado y pueden aparecer en
cualquier lugar de la cadena. Cuando la derivación se
completa, todos los trozos no generados habrán sido
sustituidos por cadenas (posiblemente vacías) de
símbolos terminales.

Así pues tenemos S Þ aSb Þ aaSbb Þ a3Sb3
Þ …
Þ
an-1Sbn-1 Þ anbn su
lenguaje es L(G) = {anbn | n
³ 1}

Todas las cadenas que no tengan símbolos no
terminales pertenecen al lenguaje definido por G que puede ser
producido por el símbolo inicial S usando las producciones
como sustituciones.

3.3. PUMPING LEMMA PARA LENGUAJES LIBRES DE
CONTEXTO.

El planteamiento formal del lema de bombeo (Pumping
Lemma en inglés) para CFL’s es el
siguiente:

Sea L un lenguaje libre de contexto que no
contiene e .
Entonces existe un entero k para el cual, si
z Î
L y ½ z½ >k , entonces
z se puede volver a escribir como z = uvwxy
con las propiedades siguientes:

1. ½
   vwx½ £
   k.
2. Al menos v o x no es e .
3. uvi wxi y
   Î L para todo
   i ³
   0.

Al igual que el lema de bombeo para lenguajes regulares,
el lema de bombeo para lenguajes libres de contexto nos
proporciona la posibilidad de probar si ciertos lenguajes no son
libres de contexto, por tanto, utilizaremos el mismo
planteamiento que en el caso de los lenguajes
regulares.

Supongamos que L ={ ai bj
| j=
i2} es libre de contexto, entonces se puede
aplicar el lema de bombeo y por tanto habrá un k
que satisfaga las condiciones del lema. Consideremos z=
ak bk2.

Desde luego, z Î L y ½ z½ >k. Por
tanto, z se puede descomponer en z=uvwxy y
se puede asegurar que uvi wxi
y Î
L para todo i ³ 0, tal que ½
vxz½ >1 y ½ vwx½ £ k. Obsérvese
que, si v= ar bs para
algún r y s, entonces vi=
(ar bs) i y, por
tanto, uvi wxi y tiene
b’s antes de a’s con lo que no puede
pertenecer a L. De forma similar, si x=
ar bs, tampoco pueden ser bombeados.
Por lo que debemos obtener que:

v= ar y x=
as o

v= br y x=
bs o también

v= ar y x=
bs

para algún valor de r y s. En el
primer caso se tiene uv2 wx2
y= ak+r+sbk2

En el segundo caso tenemos uv2
wx2 y=
akbk2+r+s

En ambos casos, cuando al menos uno de los dos r
o s, son ³
1 (como se requiere en el lema de bombeo), la cadena
resultante no puede pertenecer a L. En el tercer caso, se
obtendrá uvi wxi y=
ak+(i-1)rbk2+(i-1)s
el cual no pertenece a L para toda i a excepción de
un número finito. Por tanto, L no puede ser libre
de contexto puesto que para él no se cumple el lema de
bombeo.

3.4. NOTACIÓN BNF.

Todo lenguaje de
programación tiene reglas que prescriben la estructura
sintáctica de programas bien formados. Se puede describir
la sintaxis de las construcciones de los lenguajes de
programación por medio de gramáticas libres de
contexto o notación BFN (de sus siglas en inglés
Backus-Naur Form que significa Forma de Backus-Naur ), utilizando
la siguiente simbología:

< > significa no terminal

: : = significa produce

Þ significa
deriva

Ejemplo: El siguiente lenguaje genera cadenas de acuerdo
con la expresión regular (a+b)*c

< S > : : = a < S >

< S > : : = b < S >

< S > : : = c

El ejemplo anterior da cómo resultado:

< S >Þ a < S >

a < S >Þ ab < S >

ab < S > Þ abc

Ejemplo. Describir el lenguaje generado por la
gramática

< P > : : = Procedure Id Begin < Inst >
End.

< Inst > : : = instrucción

< Inst > : : = instrucción ; <
Inst>

Lo anterior genera programas con una estructura muy
general, similar a los programas en Pascal.
Ejemplo:

< P >Þ Procedure Id Begin < Inst >
End.

< Inst >Þ Procedure Id Begin instrucción;
< Inst > End.

< Inst >Þ Procedure Id Begin instrucción;
instrucción; < Inst > End.

< Inst >Þ Procedure Id Begin instrucción;
instrucción; instrucción End.

Lo anterior se logra apreciar mejor como se muestra a
continuación:

Procedure Id

Begin

Instrucción;

Instrucción;

Instrucción

End.

3.5. ARBOLES
SINTACTICOS.

Cuando una cadena se deriva mediante una
gramática libre de contexto, el símbolo inicial es
sustituido por alguna cadena. Los símbolos no terminales
de esta cadena son sustituidos uno tras otro por otra cadena, y
así sucesivamente, hasta que se llega a una cadena formada
sólo por símbolos terminales. A veces, es
útil realizar un gráfico de la derivación,
que indique de qué manera ha contribuido cada no terminal
a formar la cadena final de símbolos terminales. Tal
gráfico tiene forma de árbol y se llama
árbol sintáctico.

Un árbol sintáctico para una
derivación dada se construye creando un nodo raíz
que se etiqueta con el símbolo inicial. El nodo
raíz tiene un nodo hijo para cada símbolo que
aparezca en el lado derecho de la producción usada para
reemplazar el símbolo inicial. Todo nodo etiquetado con un
no terminal también tiene nodos hijos etiquetados con los
símbolos del lado derecho de la producción usada
para sustituir ese no terminal. Los nodos que no tienen hijos
deben ser etiquetados con símbolos terminales.

Consideremos la CFG cuyo lenguaje es:
{ambn | m ³ 1 y n ³ 1}

S ®
AB

A ®
aA |
a

B ®
bB |
b

La cadena aabbb puede ser derivada para la anterior CFG
mediante.

S Þ
AB Þ
AbB Þ
AbbB Þ
Abbb Þ
aAbbb Þ
aabbb

En la figura 3.4 se presenta un árbol
sintáctico para esta derivación.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Figura 3.4.

 Finalmente, puede verse que hay muchas
derivaciones posibles para la cadena aabbb, las cuales
también tienen el árbol de derivación
anterior. Por ejemplo:

S Þ
AB Þ
aAB Þ
aaB Þ
aabB Þ
aabbB Þ
aabbb.

y S Þ
AB Þ
aAB Þ
aAbB Þ
aAbbB Þ
aAbbbÞ
aabbb.

Para esta cadena y esta gramática, todas las
derivaciones de aabbb tienen el mismo árbol de
derivación. Sin embargo, esto no tiene porque cumplirse
siempre. Para verlo, considérese la siguiente
gramática que genera expresiones aritméticas
simples con los operadores: +, -, *, /, ­ , ( ).

S ®
id

S ®
S+S |
S-S

S ®
S*S |
S/S

S ®
S­
S |
-S

S ®
(S)S

Podemos derivar la expresión id+id*id de dos
formas distintas como sigue:

1. S Þ
   S+SÞ
   S+S*S Þ
   S+S*id Þ
   S+id*id Þ id+id*id
2. SÞ
   S*SÞ
   S+S*SÞ
   id+S*SÞ
   id+id*SÞ
   id+id*id

El árbol sintáctico para la
derivación uno es

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Mientras que el árbol para la derivación
dos es:

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 Observe que los dos árboles
anteriores son distintos, aunque las cadenas producidas son las
mismas.

Una gramática se dice que es ambigua si hay dos o
más árboles sintácticos
distintos.

La ambigüedad puede ser un problema para ciertos
lenguajes en los que su significado depende en parte de su
estructura, como ocurre con los lenguajes naturales y los
lenguajes de programación. Si la estructura de un lenguaje
tiene más de una descomposición y si la
construcción parcial determina su significado, entonces el
significado es ambiguo.

Por convención, si dos formas de generar una
cadena tienen una única salida. En una derivación
por la izquierda, el no terminal que se expande es siempre el del
extremo izquierdo.

Una derivación por la derecha es aquella en la
cual el no terminal que se expande es el del extremo
derecho.

Una gramática ambigua se caracteriza por tener
dos o más derivaciones por la izquierda para la misma
cadena.

EJERCICIOS.

* Ejercicio resuelto.

*3.1. Obtener el autómata de pila para el
siguiente lenguaje {an | n ³ 1}.

Q=
{q1, q2}, S = {a}, G = {Zo}, el símbolo inicial de la pila,
q0= q1, F= {q2} y
d viene dado por la
siguiente tabla:

*3.2. Dado el siguiente autómata de pila
M=(Q, S ,
G , d , q0, Z0,
F) describir el lenguaje aceptado.

Q= {q1, q2}, S = {a, b}

G = {A, B, Z},
q0= q1

Z0= Z, F= {q2}

y d
viene dado por la lista siguiente:

1. d (q1,
   e , Z)= {(q2,
   Z)}
2. d (q1, a, Z)=
   {(q1, AZ)}
3. d (q1, b, Z)=
   {(q1, BZ)}
4. d (q1, a, A)=
   {(q1, AA)}
5. d (q1, b, A)=
   {(q1, e
   )}
6. d (q1, a, B)=
   {(q1, e
   )}
7. d (q1, b, B)=
   {(q1, BB)}

L= {w Î
{a, b}*| w contiene la misma cantidad de a’s que de
b’s}.

Cuenta el número de ocurrencias de a’s y
b’s. Esto puede realizarse introduciendo símbolos en
la pila cuando se lee algún carácter de entrada y extrayéndolo
cuando se lee otro.

3.3. Dado que en un PDA los símbolos pueden ser
recuperados de la pila en orden inverso a como fueron
introducidos. Consideremos el lenguaje L= {wcwI | w Î {a, b}*}. Este PDA debe introducir
los caracteres de entrada en la pila hasta que se encuentra una c
y, entonces, compara los caracteres de la entrada con la cima de
la pila, desapilando la pila si concuerda. Describir el proceso
que realiza dicho autómata de pila M=(Q,
S , G , d , q0, z0, F) sobre
las cadenas: abcba, abcab, y babbcbbab.

Q= {q1, q2, q3},
S = {a,
b}

G = {a, b, z},
q0= q1

Z0= símbolo inicial de la
pila

F= {q3}, y d viene dado por la lista siguiente:

1. d (q1, a,
   z)={(q1, az)}
2. d (q1, a,
   a)={(q1, aa)}
3. d (q1, a,
   b)={(q1, ab)}
4. d (q1, b,
   z)={(q1, bz)}
5. d (q1, b,
   a)={(q1, ba)}
6. d (q1, b,
   b)={(q1, bb)}
7. d (q1, c, z)=
   {(q2, z)}
8. d (q1, c, a)=
   {(q2, a)}
9. d (q1, c, b)=
   {(q2, b)}
10. d (q2, a, a)=
    {(q2, e
    )}
11. d (q2, b, b)=
    {(q2, e
    )}
12. d (q2,
    e , z)= {(q3,
    z)}

3.4. Describa el lenguaje que será aceptado por
el autómata de pila M=(Q, S , G
, d ,
q0, z0, F) dado a
continuación:

Q= {q1, q2,
q3}

S = {a,
b}

G =
S È {Z0}, donde Z0 es
el símbolo inicial de la pila

q0= q1

F= {q3}

y d
viene dado por la siguiente tabla:

*3.5. Determinar la expresión regular equivalente
a la siguiente CFG.

S ®
aS

S ®
bS

S ®
a

S ®
b

S ®
e

La expresión regular es (a+b)*

*3.6. Diseñar una CFG equivalente a la
expresión regular :

(a+b)*aa(a+b)*.

S ®
XaaX

X ®
aX

X ®
bX

X ®
e

3.7. Encontrar una CFG para cada uno de los lenguajes
definidos por las siguientes expresiones regulares.

1. ab*
2. a*b*
3. (baa + abb)*

*3.8. Diseñe una CFG que genere los siguientes
lenguajes:

2. 0n1n | n ³ 0
3. ai+3
   b2i+2 | i ³ 0

c) 0i 1j
0k | j>i+k

a) S ®
e b) S
® aaabb c)
S ®
ABC

S ®
0S1 S ®
aSbb A ®
0A1| e

B ®
1B|1

C ®
1C0| e

3.9. En cada caso, diga que lenguaje es generado por las
CFG’s indicadas en las siguientes producciones:

a) S ®
aSa | bSb | e

b) S ®
aSa | bSb | a | b

c) S ®
aS | aSbS | e

d) S ®
aS | bS | a

3.10. Probar que los siguientes lenguajes son libres de
contexto, utilizando el lema de bombeo.

a) {ai bi
ci | i ³ 1 }

b) {ai bj
ci dj | i
³ 1
y j ³
1 }

*3.11. Diseñar una CFG que genere cadenas de
paréntesis balanceados. Ejemplos: ( ( ( ) ) ), ( ( ( ) ( )
) ).

S ®
e

S ®
(S)S

*3.12. Diseñar un CFG (en notación BNF)
que genere nombres de identificadores.

< Ident > : : = < Letra > <
Más_símbolos >

< Más_símbolos > : : =
e | < Letra >
< Más_símbolos > |

| < Dígito > <
Más_símbolos >

< Letra > : : = A | B | … | Z | a | b | …
|z

< Dígito > : : = 0 | 1 | … | 9

3.13. Diseñar un CFG (en notación BNF) que
genere cadenas de listas de identificadores.

*3.14. Considerando la gramática del ejercicio
3.11. encontrar los árboles sintácticos para las
cadenas: a) ( ) ( ) ( ), b) ( ( ) ( ) ) y c) ( ( ) ) (
)

 Para ver el gráfico
seleccione la opción "Descargar" del menú
superior 

CAPÍTULO IV

AUTÓMATAS LINEALES Y

LENGUAJES SENSIBLES AL CONTEXTO

Objetivo:

El alumno aprenderá a utilizar los
autómatas lineales acotados, construirá
gramáticas sensibles al contexto y entenderá su
aplicación en los lenguajes naturales.

4.1. AUTÓMATAS LINEALES (LBA).

Un autómata lineal acotado (LBA de sus siglas en
inglés Linear-Bounded Autómata) es una
máquina de Turing no determinística (para mayor
comprensión del tema vea el capítulo V de
Máquinas de Turing) que satisface las siguientes dos
condiciones:

1. El alfabeto de entrada de cinta incluye dos
   símbolos: < y >, los señaladores de extremo
   izquierdo y derecho, respectivamente.
2. El LBA no tiene movimientos a la izquierda de < o a
   la derecha de >, ni puede sustituir los símbolos <
   y >.

Definiremos un autómata linealmente acotado como una
máquina de Turing no determinista M=(Q, S , G , d , q0, B, F), en la cual el
alfabeto de cinta contenga dos símbolos especiales < y
>. M comienza con la configuración (q1 ,
£ w>) (donde
q1 es el estado inicial de M). No se permite que M
reemplace los símbolos < o >, ni que mueva su cabeza
a la izquierda de < o a la derecha de >, con lo cual, el
LBA tiene que realizar su computación en las únicas celdas de
la cinta que estaban originalmente ocupadas por la cadena de
entrada.

Por ejemplo, consideremos el LBA definido
por:

Q ={q1, q2}, S ={a, b}, G ={a, b, <, >}, F
={q2}, q0 =q1 y
d dado por:

d (q1,
<) = (q1, <, R)

d (q1, a)
= (q1, b, R)

d (q1, b)
= (q1, a, R)

d (q1,
>) = (q1, >, S), donde S significa "permanecer",
es decir no mover la cabeza de lectura/escritura.
Este LBA complementa sus cadenas de entrada convirtiendo las
a’s en b’s y viceversa. Obsérvese que, aunque
puede reconocer y trabajar sobre los símbolos < y >,
no puede reemplazarlos o moverse más allá de ellos.
Supongamos que un LBA comienza siempre con su cabeza situada
sobre el símbolo <.

4.2. LENGUAJE NATURAL O SENSIBLE AL
CONTEXTO.

Para entender que es un lenguaje natural tenemos que ver
antes que es la Inteligencia
Artificial (AI, de sus siglas en inglés Artificial
Intelligence).

La Inteligencia
Artificial, es un área de las ciencias
computacionales que nació con el objetivo de
estudiar actividades humanas, es decir, se basa en estudiar la
forma en que los seres humanos piensan cuando tratan de tomar
decisiones y resolver problemas.
Estos procesos de
pensamiento se descomponen en sus pasos básicos, que
después se usan para diseñar programas de computadora
que resuelvan esos mismos problemas a través de un proceso
similar.

Algunos de los trabajos que se han desarrollado en
Inteligencia Artificial abarcan diversas áreas de investigación, tales como la simulación
de capacidades perceptuales y habilidades psicomotoras (Robótica), la comprensión del
lenguaje natural y la construcción de sistemas
informáticos capaces de emular la pericia de un experto
humano en un ámbito de conocimiento
determinado (Sistemas
Expertos).

El lenguaje es la forma en que nos comunicamos
cotidianamente con el mundo, es decir como el hombre
sé interrelaciona con su medio. La mayor parte de la
comunicación se lleva a cabo en forma de voz. El
lenguaje escrito juega un papel no tan central como el lenguaje
hablado en muchas actividades. Pero el procesamiento del lenguaje
escrito (suponiendo que está escrito con caracteres no
ambiguos) es menos complejo que la comprensión del habla.
Por ejemplo, para construir un programa que
comprenda el lenguaje oral, es necesario disponer de todas las
características de uno que entienda el lenguaje escrito
junto el
conocimiento adicional que es necesario para poder
manipular todos los ruidos y las ambigüedades de la
señal de audio.

Para el procesamiento del lenguaje escrito, usualmente
denominado lenguaje natural se requieren conocimientos
léxico, sintáctico y semántico sobre el
lenguaje, además de la información que se necesita
sobre el mundo real. El procesamiento del lenguaje natural
incluye tanto comprensión como
generación.

Por último, para analizar el entendimiento entre
las personas (que hablan el mismo idioma) muchas veces resulta
difícil la interpretación del mensaje, ya sea por los
modismos, la entonación, etc., por lo que para lograr la
comprensión del lenguaje natural, se requiere de amplios
conocimientos lingüísticos, así como del
manejo de lenguajes de programación de muy alto nivel, por
ejemplo: Prolog y Lisp.

Ahora ya con una visión global de los inicios del
lenguaje natural, es necesario tener en cuenta que al comenzar a
construir programas informáticos que lo comprendan, se
debe conocer a detalle los distintos componentes que se
involucran en el proceso de su comprensión. Dicho proceso
se divide en las siguientes partes [Knight Rich]:

1. Análisis morfológico: Se analizan los
   componentes de las palabras individuales y se separan de ellas
   los constituyentes que no forman parte de ellas, como los
   símbolos de puntuación.
2. Análisis sintáctico: Se transforman las
   secuencias lineales de palabras en ciertas estructuras que
   muestran la forma en que se relacionan entre sí. Se
   pueden rechazar algunas secuencias si infringen las reglas del
   lenguaje sobre la forma de combinarse. Por ejemplo: un
   analizador sintáctico de castellano
   rechazaría la frase "Chico el va almacén
   al".
3. Análisis semántico: Se les asigna
   significados a las estructuras creadas por el analizador
   sintáctico. En otras palabras, se hace una
   correspondencia entre las estructuras sintácticas y los
   objetos del dominio de la
   tarea. Las estructuras en las que no se puede hacer esta
   correspondencia se rechazan. Por ejemplo: en la mayoría
   de los universos "las ideas verdes incoloras duermen"
   serían rechazadas por ser semántica anómala.
4. Integración del discurso: El
   significado de una frase individual puede depender de las
   precedentes e influenciar el significado de otras posteriores.
   Por ejemplo: la palabra "lo" en "Juan lo quiso" depende del
   contexto del discurso, mientras que la palabra "Juan" puede
   influenciar el significado de frases posteriores como
   "Él siempre lo tuvo".
5. Análisis de la pragmática: La
   estructura que representa se reinterpreta para determinar su
   significado actual. Por ejemplo, la frase ¿sabe usted
   qué hora es? debería interpretarse como una
   petición de la hora.

Además se debe considerar que el lenguaje natural
no reconoce declaraciones que estén fuera de su campo de
acción, de su forma de análisis gramatical o de su contexto de
interpretación de declaraciones por lo que algunos grandes
problemas del lenguaje natural son la ambigüedad y las
declaraciones con más de un significado.

En este último aspecto es necesario analizar
algunos tipos de ambigüedades:

1. 1. armadura para cubrir la cabeza
   2. las uñas de las patas de los
      caballos
   3. cuerpos de los barcos, etc.
2. Ambigüedad léxica: Una palabra puede tener
   varios significados. Por ejemplo, la frase "Tenía los
   cascos sin herrar", la palabra "cascos" puede
   significar:
   1. Debes comprar peras y manzanas o debes comprar
      duraznos
   2. Debes comprar peras y debes comprar manzanas o
      duraznos.
3. Ambigüedad estructural: Una frase puede tener dos
   o más estructuras sintácticas. Por ejemplo: la
   frase "Debes de comprar peras y manzanas ó duraznos"
   se puede interpretar como:
   1. Del verbo cocinar
   2. Del sustantivo cocina.
4. Ambigüedad de clase: Una
   palabra puede ser tomada como verbo o como nombre. Ejemplo:
   "Mamá está en la cocina", aquí la
   palabra cocina proviene de:
   2. Que la vio a través de los lentes del
      telescopio

   3. Que la vio que llevaba un telescopio.
5. Ambigüedad global: La frase es completamente
   ambigua. Ejemplo: "Juan vio a la muchacha con telescopio", esta
   oración puede interpretarse como:
6. Significado de la frase: También es conocida
   como representación objetivo, la cual se refiere que una
   frase se puede interpretar de diferentes formas, como por
   ejemplo: ¿Sabes que hora es?. La interpretación
   sería: si sabes la hora, dímela.
7. Metáforas: Figuras que trasladan las palabras
   reales a un sentido figurado. Por ejemplo: "Son tus ojos como
   dos esmeraldas". Esto nos dice: Que sus ojos son verdes y
   hermosos.
8. Modismos: Son expresiones propias y privadas de la
   lengua. Cada
   región tiene la propia. Por ejemplo: "A la chita
   callando", lo cual significa: Callarse la voz de
   ya.

Podemos especificar un lenguaje por medio de dos
técnicas. La primera es describiendo un
procedimiento
para reconocer sus cadenas, es decir, a través de
autómatas de varios tipos y la segunda forma es por medio
de una técnica que genere sus cadenas, esto es con la
utilización de gramáticas. Para tener una mejor
idea sobre este último método
veremos la siguiente gramática simple para un
lenguaje.

Oración ® Sujeto + Predicado

Sujeto ®
Artículo + Sustantivo

Sujeto ®
Sustantivo

Predicado ® Verbo + Sujeto2

Sujeto 2 ® Artículo + Sustantivo

Sujeto 2 ® Artículo + Sustantivo +
Adjetivo

La primera producción establece que una
oración esta compuesta de un sujeto y un predicado, el
sujeto puede ser un artículo seguido de un sustantivo o un
sustantivo únicamente. El predicado consta de un verbo y
un sujeto que es ligeramente diferente al primer sujeto, esta
frase puede tener ya sea en un artículo más un
sustantivo o un artículo seguido por un sustantivo y
después un adjetivo. El árbol para esta
gramática se muestra en la figura 4.1.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Figura 4.1. Árbol para una
gramática simple de un lenguaje.

Utilizando la gramática y un vocabulario formado
por artículos, adjetivos, verbos y sustantivos se pueden
crear oraciones significativas en español.

La forma en que se va a realizar el almacenamiento del
vocabulario depende del lenguaje de programación que se
use los más utilizados son: Prolog o Lisp o incluso
lenguaje "C". Los dos primeros nos permiten de una manera
fácil y abundante el manejo de gráficos y de base de datos,
en cuanto se refiere al tercero facilita el manejo de
gráficos pero no muy sencillo en el manejo de base de
datos.

Ahora bien existe una gramática más
útil para el desarrollo de
lenguajes naturales y se conoce como gramática sensible al
contexto.

Las gramáticas sensibles al contexto (CSG de sus
siglas en inglés Context-Sensitive Grammar) producen una
clase de lenguajes que está estrictamente situada entre
los lenguajes libres de contexto y los lenguajes recursivos y se
conocen como lenguajes sensibles al contexto (CSL de sus siglas
en inglés Context-Sensitive Language).

Una gramática G=(N, S , S, P) es una gramática
sensible al contexto si todas las producciones
son de la forma a
® b , donde a , b
, Î
(N È
S )+ y
|a |
£
|b |.
Donde:

N es un alfabeto de símbolos no
terminales.

S es un
alfabeto de símbolos terminales con NÇ S =Æ .

SÎ N es el símbolo
inicial.

P es un conjunto finito de producciones de la
forma a ® b , donde a , b
, Î
(N È
S
)+.

Por ejemplo, la gramática dada por:

S ®
abc|aAbc

Ab ®
bA

Ac ®
Bbcc

bB ®
Bb

aB ®
aa|aaA

es una gramática sensible al contexto. Esta
gramática genera el lenguaje sensible al contexto
{an bn cn| n³ 1}, con lo que tenemos un
ejemplo de un lenguaje sensible al contexto que no es libre de
contexto.

Toda gramática libre de contexto se puede poner
en forma normal de Chomsky, en la cual las producciones son de la
forma A®
a o también
AÞ BC.
Puesto que las producciones de esta forma satisfacen la
definición de gramáticas sensibles al contexto, se
deduce que toda gramática libre del contexto es
también una gramática sensible al contexto. Por
tanto el conjunto de los lenguajes sensibles al contexto contiene
el conjunto de los lenguajes libres de contexto.

La restricción de que el lado derecho de las
producciones en una gramática sensible al contexto sea al
menos tan largo como el lado izquierdo hace que la
gramática sea no contráctil. Puesto que la cadena
vacía tiene longitud 0, podemos definir que
e Ï L(G), para cualquier gramática G
sensible al contexto.

Los lenguajes sensibles al contexto son exactamente los
lenguajes aceptados por los autómatas lineales acotados,
máquinas de Turing no determinísticas en donde la
cabeza de la cinta visita un número de celdas que son una
constante múltiple de la longitud de una cadena de
entrada.

Los lenguajes sensibles al contexto contienen,
propiamente, a los lenguajes libres de contexto. A su vez, los
lenguajes recursivos contienen propiamente a los lenguajes
sensibles al contexto, como se vio en la clasificación de
las gramáticas (ver capítulo 1).

4.3. APLICACIONES.

Existe un gran número de problemas de diseño
de software que se
simplifican mediante la conversión automática de
las expresiones regulares a una instrumentación eficiente de computadora
del autómata finito correspondiente.

Los autómatas finitos se usan frecuentemente en
los problemas que implican el análisis de cadenas de
caracteres. Tales problemas incluyen problemas de búsqueda
e identificación, tales como la búsqueda de la
existencia de una cadena en un archivo o el
reconocimiento de cadenas de entrada que satisfagan ciertos
criterios. Un autómata finito es, él mismo, un
modelo de un procedimiento para reconocimiento de cadenas por
medio de la expresión regular asociada. Por tanto, en la
búsqueda de una cadena en un archivo, podemos aplicar el
autómata finito de forma sistemática a las cadenas
del archivo hasta que se acepta la cadena o se termina el
archivo.

Un problema común en la programación de
computadoras
es el de tener la seguridad de que
los datos de entrada de un programa son correctos. La
programación cuidadosa pretende construir un programa que
analice la información introducida por el usuario y, de
alguna forma, prevenir que se aplique información
incorrecta al programa. Si pudiéramos construir un
autómata finito que aceptara solamente las cadenas que
representan información correcta, entonces
tendríamos un modelo para dicha rutina de entrada. Puesto
que los autómatas finitos se corresponden con las
expresiones regulares, el problema se reduce a especificar la
información correcta por medio de expresiones
regulares.

Por ejemplo, en el caso de que la entrada a un programa
esté formado por enteros sin signo, el lenguaje
vendrá dado por L={1, 2, 3, 4, 5, 6, 7, 8, 9}.{0, 1, 2, 3,
4, 5, 6, 7, 8, 9}*. Es fácil construir un autómata
finito que acepte L (ver Figura 4.2.).

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Figura 4.2.

También es sencillo traducir el autómata
finito a un código
en un lenguaje de programación; sólo se necesita
seguir el rastro de la posición actual en la cadena y del
estado actual. A la vez que se recorre la cadena, se comprueba a
qué estado se ha llegado y, según eso, se acepta o
se rechaza la cadena.

Las expresiones regulares se pueden usar para
especificar las unidades léxicas presentes en un lenguaje
de programación. Los autómatas finitos asociados se
usan para reconocer dichas unidades (llamados componentes
léxicos). Dicho análisis es una etapa importante en
la compilación de programas de computadoras.

En la etapa de análisis léxico de un
compilador, hay un aspecto que no estaba presente en el ejemplo
de los enteros como entrada y es el hecho de que al tratar de
reconocer un lexema se tienen distintas posibilidades. Por
ejemplo, si es un comentario, un identificador, etc.
Generalmente, en un compilador, el autómata finito que
reconoce todos los componentes léxicos está
ordenado de alguna manera y, sistemáticamente, se aplica a
la cadena hasta que se tiene éxito o
falla en todo. Si falla, la cadena no puede formar parte de un
programa.

Otro ejemplo de aplicaciones son los editores de texto.
Ciertos editores de texto y programas similares permiten la
sustitución de una cadena por cualquier cadena que
concuerde con una expresión regular. Por ejemplo, el
editor de texto UNIX permite
que un comando como s/bbb*/b/ sustituya por un solo espacio en
blanco la primera cadena de dos o más espacios en blanco
que se encuentran en una línea dada. La expresión
"cualquier" que se representa por el * denota
a1+a2+…+an, en la que las
ai son todos los caracteres de una computadora excepto
al carácter "nueva línea". Podemos convertir una
expresión regular r a un autómata finito
determinístico (DFA) que acepte cualquier *r.
Nótese que la presencia de la operación cualquier*
nos permite reconocer un miembro de L(r) que comience en
cualquier lugar de la línea. Sin embargo, la
conversión de una expresión regular a un DFA toma
mucho más tiempo que el
que toma barrer una sola línea corta utilizando el DFA, y
el DFA podría tener cierto número de estados que
son una función exponencial de la longitud de la
expresión regular.

Lo que realmente sucede en el editor de textos de UNIX
es que la expresión regular cualquier *r es convertida a
un autómata finito no determinístico (NFA) con
transiciones e ,
y el NFA se simula directamente. Sin embargo, una vez que se ha
construido una columna, listando todos los estados en los que
puede estar el NFA sobre un prefijo determinado de la salida, la
columna inmediata anterior ya no es necesaria y se elimina con el
fin de ahorrar espacio.

EJERCICIOS:

* Ejercicio resuelto.

*4.1. Obtener un LBA que acepte el lenguaje
{an| n ³ 0}.

Q ={q1, q2,
q3} S
={a, b}

G ={a, b, <,
>} F ={q3}

q0 =q1 y d dado por:

1. d (q1,
   <) = (q1, <, R)
2. d (q1,
   a) = (q1, a, R)
3. d (q1,
   b) = (q2, b, R)
4. d (q2,
   a) = (q2, a, R)
5. d (q2,
   b) = (q2, b, R)
6. d (q1,
   >) = (q3, >, S)

*4.2. Obtener un LBA que acepte el lenguaje
{an bn | n ³ 1}.

Q ={q1, q2, q3,
q4, q5} S ={a, b}

G ={a, b, c, d,
<, >} F ={q5}

q0 =q1 y d dado por:

1. d (q1,
   <) = (q1, <, R)
2. d (q1,
   a) = (q2, c, R)
3. d (q2,
   a) = (q2, a, R)
4. d (q2,
   d) = (q2, d, R)
5. d (q2,
   b) = (q3, d, L)
6. d (q3,
   d) = (q3, d, L)
7. d (q3,
   a) = (q3, a, L)
8. d (q3,
   c) = (q1, c, R)
9. d (q1,
   d) = (q4, d, R)
10. d (q4,
    d) = (q4, d, R)
11. d (q4,
    >) = (q5, >, S)

4.3. Obtener un LBA que acepte el lenguaje
{an bn cn | n ³ 1}.

4.4. Obtener un LBA que determine si sus cadenas de
entrada tienen longitud impar. Suponga que las cadenas de entrada
pertenecen a {a, b}*.

*4.5. Si una gramática sensible al contexto puede
contener la producción S® e ,
¿Por qué se requiere que S nunca aparezca en el
lado derecho de una producción?.

Por que las gramáticas sensibles al contexto
tienen la restricción de no ser contráctil. Puesto
que la cadena vacía tiene longitud 0 se tiene entonces
que e Ï L(G) a cualquier
gramática sensible al contexto.

*4.6. Describa el lenguaje generado por la siguiente
gramática sensible al contexto:

S ®
Xb

Xb ®
bA

El lenguaje es {b2 | i
³ 1
}.

Ejemplos de la derivación:

b2 b2 b2

S Þ
Xb S Þ
Xb S Þ
Xb

Þ bb
Þ bXbb
Þ bXbb

Þ
bbbb Þ
bbXbbb

Þ
bbbbbb

*4.7. Construya la gramática sensible al contexto
que genere el lenguaje {an bm cm
dn | m,n³ 1}.

S ®
aSd | aAdd

Ad ®
bAdc | bc

Ejemplos de la derivación:

a1 b1 c1 d1
a2 b1 c1
d2 a2 b2 c2
d2

S Þ
aAdd S Þ
aSd S Þ
aSd

Þ abcd
Þ aaAddd
Þ
aaAddd

Þ
aabcdd Þ
aabAdcdd

Þ
aabbccdd

*4.8. Construya la gramática sensible al contexto
que genere el lenguaje {a2i| i³ 1}.

1. S ®
   [AcaB]
2. [Ca]a ® aa[Ca]

[Ca] [aB] ® aa[CaB]

[ACa]a ®
[Aa]a[Ca]

[ACa] [aB] ® [Aa]a[CaB]

[ACaB] ®
[Aa][aCB]

[CaB] ®
a[aCB]

3. [aCB] ® [aDB]
4. [aCB] ® [aE]

   [aDB] ® [DaB]

   [Aa] [Da] ® [ADa]a

   a[DaB] ® [Da] [aB]

   [Aa] [DaB] ® [ADa] [aB]

5. a[Da] ® [Da]a
6. [ADa] ® [ACa]

   [aE] ® [Ea]

   [Aa] [Ea] ® [AEa]a

7. a[Ea] ® [Ea]a
8. [AEa] ® a

Nota: A, B, C, etc. no son más que
señaladores, que a fin de cuentas,
desaparecerán. En lugar de utilizar símbolos
separados para los señaladores, se pueden incorporar estos
señaladores a las a’s mediante la creación de
variables
"compuestas" como [CaB], que son un solo símbolo que
aparece en lugar de la cadena.

4.9. ¿El conjunto de los lenguajes sensibles al
contexto es cerrado con respecto a la unión, la
concatenación o la cerradura de estrella? ¿Por
qué?.

4.10 Construya la gramática sensible al contexto
que genere los siguientes lenguajes:

1. {an | n³ 1 }
2. {ww | w Î {a, b}+}.
3. {w | w Î {a, b, c}* y el número de
   a’s en w es igual al número de b’s y
   c’s}.
4. {am bn am
   bn | m,n³ 1}.

 CAPÍTULO
V

MÁQUINAS DE TURING Y

LENGUAJES RECURSIVOS ENUMERABLES

Objetivo:

El alumno conocerá la fundamentación de
las máquinas de Turing, sus funciones, los lenguajes que
aceptan, su clasificación e Identificará aquellos
problemas que no tienen solución
computable.

5.1. DEFINICIÓN DE UNA MÁQUINA DE
TURING.

El modelo básico, ilustrado en la figura 5.1, tiene
un control finito, una cinta de entrada que está dividida
en celdas y una cabeza de cinta que barre una celda de la cinta a
la vez. La cinta tiene una celda que está más a la
izquierda, pero se extiende de manera infinita hacia la derecha.
Cada celda de la cinta puede contener exactamente un
símbolo de un número infinito de símbolos de
la cinta. Inicialmente, las n celdas que están más
a la izquierda, para alguna n³ 0 finita, sujetan la entrada, que es una
cadena de símbolos escogidos de un subconjunto de los
símbolos de la cinta, llamados símbolos de entrada.
Cada una del número infinito de celdas restantes sujetan
el espacio en blanco, que es un tipo especial de símbolo
que no es de entrada.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Figura 5.1 Máquina de
Turing.

En un movimiento, dependiendo del símbolo barrido
por la cabeza de la cinta y del estado de control finito, la
máquina de Turing:

1. Cambia de estado,
2. Imprime un símbolo en la celda de la cinta que
   está siendo barrida, sustituyendo lo que se encontraba
   ahí escrito y
3. Mueve su cabeza una celda hacia la izquierda o la
   derecha.

De manera formal, una máquina de Turing (TM de
sus siglas en inglés Turing Machine) se representa por:
M=(Q, S
, G
, d ,
q0, B, F) en donde:

Q es un conjunto finito de
estados.

G es el
conjunto finito de símbolos de cinta
admisibles.

B símbolo de G , es el espacio en blanco.

S
subconjunto de G que no incluye a B, es el conjunto de los
símbolos de entrada.

d es la
función de movimientos siguiente, una
transformación de Q x G a Q x G x {L, R} ( d puede sin embargo, permanecer indefinida por
algunos argumentos).

q0 en Q es el estado
inicial.

F Í Q es el conjunto de estados
finales.

En esta definición se supone que el valor inicial
de todas las celdas de la cinta es el símbolo B. La
definición requiere que B Ï S .
Generalmente permitimos que S Í
G – {B}. La
función de transición d transforma pares (q, s ) formados por el estado actual
y los símbolos de la cinta en ternas de la forma (p, t,
x), donde p es el estado siguiente, t es el símbolo
escrito en la cinta y x es un movimiento de lectura/escritura de
la cabeza, que puede ser L o R, según que el movimiento
sea hacia la izquierda o hacia la derecha (nos imaginamos que la
cinta se extiende de izquierda a derecha).

Por ejemplo, la transición d (q1,
a)=(q5, b, R) provoca que la TM pase de una
configuración figura 5.2. A la configuración de la
figura 5.3.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Figura. 5.2 Estado interno
q1.Figura. 5.3 Estado interno
q1.

Usaremos una descripción instantánea (ID) de la
máquina de Turing, para su notación denotando el
paso de una configuración a otra por medio del
símbolo .

Ejemplo: consideremos la máquina de Turing que
acepta el lenguaje regular a*, definida mediante

Q ={q1, q2}

S ={a, b}

G ={a, b,
B}

F ={q2}

q0 =q1

y d
dada por la siguiente tabla::

los datos de d también se pueden listar de la
siguiente manera:

1. d (q1,
   a) = (q1, a, R)
2. d (q1,
   B) = (q2, B,R)

Por lo tanto, la ejecución de la máquina
de Turing para la cadena "aaa" es la siguiente
configuración:

q1aaa por la regla 1 aq1aa, por
la regla 1 aaq1a, por la regla 1

aaaq1B, por regla 2
aaaBq2

Esta máquina de Turing para en el estado
q2, sólo si se analiza una cadena de
cero o más a’s.

Las notaciones * y + tienen el significado
usual "cero o más" o "una o más",
respectivamente.

Cuando d
(q, a) está indefinido y la configuración de
la máquina de Turing es imposible que pase a otra se dice
que la máquina de Turing está parada. La
secuencia de todos los movimientos que conducen a una
configuración de parada se llama
computación. Para los casos donde la máquina de
Turing nunca parará se dice, que la máquina
se encuentra en un bucle infinito.

5.2. FUNCIONES DE UNA MÁQUINA DE
TURING.

La máquina de Turing puede considerarse como una
computadora de funciones que van de los enteros a los enteros. El
planteamiento tradicional consiste en representar a los enteros
como números unitarios; el entero
i³
0 se representa mediante la cadena
0i. Si una función tiene k argumentos,
i1, i2, …, ik, entonces estos
enteros se colocan inicialmente en la cinta separados por 1s:
0i1 10i2 …
10ik.

Si la TM se detiene (esté o no en un estado de
aceptación) con una cinta que consiste en 0m
para alguna m, entonces decimos que
ƒ(i1,i2,…,ik)=m, en donde
ƒ es la función de k argumentos calculada por esta
máquina de Turing.

Adviértase que una TM puede calcular una
función de un argumento, una función diferente de
dos argumentos y así sucesivamente. Si la TM M calcula la
función ƒ de k argumentos, entonces ƒ no
necesariamente tiene un valor para cada conjunto diferente de k
tuplas de enteros i1,…,ik.

Si ƒ (i1,…,ik) se define
para toda i1,…,ik, entonces decimos que
ƒ es una función totalmente recursiva. La
función ƒ (i1,…,ik) calculada
por una máquina de Turing se conoce como función
parcialmente recursiva. Las funciones parcialmente recursivas
pueden detenerse o no en una entrada dada. Las funciones
totalmente recursivas corresponden a los lenguajes recursivos, ya
que son calculadas por TMs que siempre se detienen. Todas las
funciones aritméticas corrientes sobre los enteros, como
la multiplicación, n!, [log2nn] y
22n, son funciones totalmente recursivas.

Ejemplo:
La sustracción propia, m n se define como m-n para
m³ n y cero
para m< n. La TM M=({q0, q1, …,
q6}, {0, 1}, {0, 1, B}, d , q0, B, Æ )

que se
define más adelante, y que comienza con
0m10n en su cinta, se detiene con 0m
n en su cinta. M sustituye de manera repetida su 0 del
frente por un espacio en blanco, entonces busca hacia la derecha
un 1 seguido por un 0 y cambia el 0 por 1. En seguida M se mueve
hacia la izquierda hasta que encuentra un espacio en blanco y
entonces repite el ciclo. La repetición termina
si:

a) Buscando hacia la derecha un 0, M encuentra un
espacio en blanco. Entonces los n 0’s, que están en
0m10n han sido todos cambiados a 1s y n+1
de los m 0’s se han cambiado a B. M sustituye a los n+1
1’s por un 0 y n B’s, dejando m – n 0’s en su
cinta.

b) Comenzando el ciclo, M no puede encontrar un 0 que
sea cambiado a un espacio en blanco, debido a que los primeros m
0’s ya han sido cambiados. Entonces n ³ m, de modo que m n=0. M
sustituye todos los 1’s y 0’s restantes por
B.

La
función d
se descubre a continuación:

Nota: Recuerde que un movimiento de lectura/escritura de
la cabeza, puede ser L o R, según que el movimiento sea
hacia la izquierda o hacia la derecha, vista en la
definición de TM.

1. Comienza. Sustituye el 0 del frente por
   B.

2. d (q0,0)
   = (q1,B,R)

   d
   (q1,1) = (q2,1,R)

   Estructura hacia la derecha, buscando el primer
   1.

3. d (q1,0)
   = (q1,0,R)

   d
   (q2,0) = (q3,1,L)

   Estructura hacia la derecha saltándose los1s
   hasta que se encuentra un 0. Cambia ese 0 por 1.

4. d (q2,1)
   = (q2,1,R)

   d
   (q3,1) = (q3,1,L)

   d
   (q3,B) = (q0,B,R)

   Se mueve hacia la izquierda a un espacio en blanco.
   Accesa el estado q0 para repetir el
   ciclo.

5. d (q3,0)
   = (q3,0,L)

   d
   (q4,1) = (q4,B,L)

   d
   (q4,0) = (q4,0,L)

   d
   (q4,B) = (q6,0,R)

   Si en el estado q2 se encuentra una B
   antes que un 0, tenemos la situación del inciso (a)
   descrita más arriba. Se accesa el estado q4
   y se mueve hacia la izquierda, cambiando todos los 1 por Bs
   hasta encontrar una B. Esta B se cambia de nuevo a 0, el
   estado q6 es accesado y M se detiene.

6. d
   (q2,B) = (q4,B,L)
7. d
   (q0,1) = (q5,B,R)

d
(q5,0) = (q5,B,R)

d
(q5,1) = (q5,B,R)

d
(q5,B) = (q6,B,R)

Si en el estado q0 se encuentra un 1 en lugar
de un 0, el primer bloque de 0s ha sido agotado, como en la
situación (b) anterior. M accesa el estado q5
para borrar el resto de la cinta, entonces accesa el estado
q6 y se detiene. Una muestra del cálculo de
M sobre la entrada 0010 es:

q00010 Bq1010 B0q110 B01q20 B0q311
Bq3011
q3B011 Bq0011 BBq111 BB1q21 BB11q2
BB1q41 BBq41 Bq4
B0q6

Sobre la entrada 0100, M se comporta de la manera
siguiente:

q00100 Bq1100 B1q200 Bq3110 q3B110
Bq0110

BBq510 BBBq50 BBBBq5 BBBBBq6

 5.3. LENGUAJES ACEPTADOS POR LAS
MÁQUINAS DE TURING.

Una máquina de Turing se puede comportar como un
aceptador de un lenguaje. Si colocamos una cadena w en la cinta,
situamos la cabeza de lectura/escritura sobre el símbolo
del extremo izquierdo de la cadena w y ponemos en marcha la
máquina a partir de su estado inicial. Entonces w es
aceptada si, después de una secuencia de movimientos, la
máquina de Turing llega a un estado final y para.
Por tanto w es aceptada. Si qw *
w1pw2 para algún estado final p y
unas cadenas w1 y w2. Entonces, se obtiene
la siguiente definición:

Sea M = (Q, S
, G ,
q0=q1, B, F, d ) una máquina de Turing. Entonces
el lenguaje aceptado por M es: L(M) = {wÎ S *½ q1w *
w1pw2 para pÎ F y
wiÎ G
*}.

Ejemplo. Diseñar una TM que acepte el lenguaje
regular a* sobre S
={a, b}. Comenzando con el símbolo que
está más a la izquierda en una cadena, realizaremos
un análisis hacia la derecha, leyendo cada símbolo
y comprobando que es una a; si lo es, realizaremos un
desplazamiento hacia la derecha. Si encontramos un blanco (B) sin
que se haya leído ningún símbolo que no
fuera a, paramos y aceptamos la cadena. Si por el otro lado,
encontramos un símbolo que no es ni a ni B, podemos
parar en un estado que no es de aceptación.

Sea Q = {q1,q2},
q0=q1 y F={q2}, y sea
d definida
por:

d (q1,a)
= (q1,a,R)

d (q1,B)
= (q2,B,R)

Esta máquina de Turing para en el estado
q2, sólo si se analiza una cadena de 0 ó
más a’s.

Para rechazar una cadena que no es aceptable, lo
único que hay que hacer es evitar que se llegue a un
estado final. En este ejemplo las cadenas que no son aceptables,
provocan que la máquina pare en un estado que no es final.
Otra alternativa para rechazar una cadena es entrar en un bucle
infinito.

Un lenguaje que es aceptado por una máquina de
Turing se conoce como lenguaje recursivamente enumerable (r.e.).
El término enumerable proviene de que dichos lenguajes son
aquellos cuyas cadenas pueden ser listadas (enumeradas) por una
máquina de Turing. Esta clase de lenguajes es bastante
grande, incluyendo los lenguajes libres de contexto.

Hay lenguajes r.e. para los cuales ninguna
máquina de Turing que los acepte para con todas las
entradas (naturalmente, cualquier máquina de Turing para
dichos lenguajes debe parar para toda cadena que pertenezca
realmente al lenguaje). La subclase de los lenguajes
recursivamente enumerables que son aceptados por al menos una
máquina de Turing que para con toda cadena de entrada
(dependiendo de si la cadena es aceptada o no), se conoce por la
clase de los lenguajes recursivos.

Puesto que las máquinas de Turing pueden leer y
escribir sobre su cinta pueden convertir la entrada en salida. La
transformación de la entrada en salida es el primer
propósito de las computadoras digitales; por tanto, una
máquina de Turing se considera como un modelo abstracto de
una computadora. Se supone que la entrada para la máquina
de Turing está formada por todos los símbolos de la
cinta que no son blancos. La salida está formada por
cualquiera de los símbolos que queden en la cinta cuando
la computación termina.

Las máquinas de Turing pueden ser consideradas
como la implementación de una función de cadena
f definida mediante f(w) = u cuando se cumple
qsw * q f u, donde qs es
el estado inicial y q f es un estado final, por
lo que se requiere que la cabeza de lectura/escritura empiece y
termine, respectivamente, sobre el símbolo de las cadenas
de entrada y salida que está situado más a la
izquierda.

Definiendo lo anterior se dice que una función de
cadena f es Turing computable si existe una
máquina de Turing M = (Q, S , G
, q1,B,F,d ) para la cual q1w * q
f u para algún q
f Î F, cuando f(w) = u.

Se puede extender la anterior definición de
funciones integrales,
como se muestra en el siguiente ejemplo.

Ejemplo. Supongamos que tenemos S ={a,b} y que representamos los
enteros positivos mediante cadenas de a’s. Así, el
entero positivo n estaría representado por an.
La función suma f(n,m) = n + m podría ser
implementada mediante la transformación de
anbam en an+mb. Podríamos
obtener una máquina de Turing para la suma, que
estaría representada por M = (Q, S , G , q0, B,F,d ), donde

Q = {q1, q2, q3,
q4, q5}

q0 = {q5}

y d
dada por las siguientes transformaciones:

1. d
   (q1,a) = (q1,a,R)
2. d
   (q1,b) = (q2,a,R)
3. d
   (q2,a) = (q2,a,R)
4. d
   (q2,B) = (q3,B,L)
5. d
   (q3,a) = (q4,b,L)
6. d
   (q4,a) = (q4,a,L)
7. d
   (q4,B) = (q5,B,R)

Esta máquina de Turing desplaza la b hacia
el final, a la derecha de an+m. Para ello se crea una
a extra. La máquina de Turing
"recordará" que se ha creado una a al pasar
al estado q2 una vez que se ha encontrado la b,
y entonces se escribirá una b sobre la a que
está al final de la cadena. Cuando termina la
máquina de Turing la cabeza de lectura/escritura
está sobre la a que encuentra más a la
izquierda.

5.4. EXTENSIONES DE LAS MÁQUINAS DE
TURING

Hay otras definiciones de las máquinas de Turing
que son equivalentes. Algunos de esos modelos
alternativos son mucho más complicados aunque todos tienen
la misma potencia computacional (o de cálculo). Muchas de
ellas dotan de mayor flexibilidad al diseño de una
máquina de Turing que resuelva un problema en particular.
Ejemplos [Kelley Dean]:

Máquina de Turing con Directiva de
Permanecer

Recuérdese que la máquina de Turing
sencilla sitúa la cabeza de lectura/escritura sobre el
primer B que haya a la izquierda de la posición actual.
Para hacerlo, busca fuera de la celda actual y retrocede. Esto es
debido a la definición original que requiere que por cada
transición se mueva la cabeza de la cinta.

La función de transición estaba definida
como: d : Q
x G ® Q x G x {R, L}

y puede ser modificada como: d : Q x G ® Q
x G x {R, L, S}
donde S significa "permanecer", es decir no mover la cabeza de
lectura/escritura.

Por tanto d
(q, s
)=(p, s
’, S) significa que se pasa del estado q al p, se
escribe s
’ en la celda actual y la cabeza se queda sobre la
celda actual.

Máquina de Turing Multipista

Es aquella mediante la cual cada celda de la cinta se
divide en subceldas. Cada subcelda es capaz de contener
símbolos de la cinta. La cinta tiene cada celda
subdividida en tres subceldas. Se dice que esta cinta tiene
múltiples pistas. Puesto que cada celda de esta
máquina de Turing contiene múltiples caracteres, el
contenido de las celdas de la cinta puede ser representado
mediante n-tuplas ordenadas. En el ejemplo anterior, las celdas
de la cinta contienen (B, a, a), (b, a, a) y (b, b, B). Por
tanto, los movimientos que realice está máquina
dependerán de su estado actual y de la n-tupla que
represente el contenido de la celda actual.

Una máquina de Turing multipista no tiene
más potencia que la máquina de Turing original. Sin
embargo, hace que sea más fácil la
construcción de máquinas de Turing que resuelvan
ciertos problemas.

Ejemplo: Para una máquina de Turing que sume dos
números binarios. Primero se construye una máquina
de Turing de tres pistas. La entrada serán dos
números binarios que ocupen las dos pistas superiores de
la cinta. Suponiendo que sus dígitos se alinean por la
derecha, que sus representaciones binarias son de la misma
longitud (lo que se puede conseguir rellenándolas con
tantos ceros como sea necesario) y que la cabeza de
lectura/escritura se sitúa sobre la celda del extremo
izquierdo de la cadena. Por tanto, si tuvieran que sumar 101 y
10, la cinta debería contener

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Cabeza

 La máquina de Turing realizará la
suma en la tercera pista. Por tanto, el alfabeto de cinta
estará formado por las ternas:

(B, B, B) (1, 1, B) (1, 1, 0) (1, 1, 1)

(0, 0, B) (0, 0, 0) (0, 0, 1) (B, B, 1)

(0, 1, B) (0, 1, 0) (0, 1, 1)

(1, 0, B) (1, 0, 0) (1, 0, 1)

Esta máquina de Turing buscará primero
hacia la derecha el extremo derecho de los números que van
a ser sumados. Entonces sumará pares de dígitos,
desde la derecha hacia la izquierda, llevando la cuenta de los
resultados que se obtengan y sumando a quienes corresponda. Por
tanto, se obtiene (suponiendo que q1 es el estado
inicial):

d
(q1, s ) = (q1, s , R), si s ¹ (B,
B, B) ó (q2, s , L), si s =(B, B, B)

d (q2,
(0, 0, B)) = (q2, (0, 0, 0), L) d (q3, (0, 0, B)) =
(q2, (0, 0, 1), L)

d (q2,
(0, 1, B)) = (q2, (0, 1, 1), L) d (q3, (0, 1, B)) =
(q3, (0, 1, 0), L)

d (q2,
(1, 0, B)) = (q2, (1, 0, 1), L) d (q3, (1, 0, B)) =
(q3, (1, 0, 0), L)

d (q2,
(1, 1, B)) = (q3, (1, 1, 0), L) d (q3, (1, 1, B)) =
(q3, (1, 1, 1), L)

d (q2,
(B, B, B)) = (q4, (B, B, B), S) d (q3, (B, B, B)) =
(q4, (B, B, B), S)

Obsérvese que se necesita que esta máquina
de Turing tenga la posibilidad de no moverse. La máquina
de Turing transformará

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 en:

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior

 Máquina de Turing de Cinta infinita en
una Dirección

Máquina de Turing que usa una cinta que se
extiende infinitamente en una única dirección. Generalmente, se tiene una cinta
que se extiende infinitamente hacia la derecha. No está
permitido realizar ningún movimiento hacia la izquierda a
partir de la celda del extremo izquierdo. Desde luego, cualquier
máquina de Turing de esta forma puede ser simulada por una
de las que responden a la definición original. Para cada
computación, simplemente se marca una de las
celdas de la cinta infinita por los dos lados, como la celda que
se encuentra en el límite izquierdo.

Máquina de Turing en Dos
Direcciones

Una máquina de Turing con una cinta infinita en
un sentido puede simular una máquina de Turing con la
cinta infinita en los dos sentidos pero con dos pistas. Sea
M una máquina de Turing con una cinta infinita en
los dos sentidos. La máquina de Turing M’,
que tiene una cinta infinita en un sentido, puede simular a
M si tiene una cinta con dos pistas. La cinta superior
contiene la información correspondiente a la parte derecha
de la cinta M, a partir de un punto de referencia dado. La
pista inferior contiene la parte izquierda de la cinta M
(en orden inverso). Por tanto, si la cinta de M
contenía

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Punto de referencia

la cinta de M’ podría ser como

  Para ver el gráfico
seleccione la opción "Descargar" del menú
superior

El símbolo especial * marca el límite
izquierdo de la cinta. Cuando M tuviera que pasar el punto
de referencia, M’ tendría que encontrarse con
la celda marcada con *. Si M está trabajando sobre
las celdas que están a la derecha del punto de referencia,
M’ está trabajando sobre la pista superior.
Cuando M trabaja sobre las celdas que están a la
izquierda del punto de referencia, M’ trabaja sobre
la pista inferior. Cuando M pasa al punto de referencia,
M’ se encuentra con los *, cambia de
dirección y cambia de pista sobre la que
trabaja.

Máquina de Turing Multicinta

La máquina de Turing multicinta tiene varias
cintas, cada una de las cuales tiene su propia cabeza de
lectura/escritura. Las cabezas de lectura/escritura se controlan
independientemente (es decir, al mismo tiempo, no tienen que
moverse en la misma dirección, ni realizar el mismo
número de movimientos, ni incluso, hacer nada a la vez).
En un solo movimiento, esta máquina de Turing

1. Cambia de estado dependiendo del estado actual y del
   contenido de las celdas de todas las cintas, que están
   analizando actualmente las cabezas de
   lectura/escritura.
2. Escriben un nuevo símbolo en cada una de las
   celdas barridas por sus cabezas de
   lectura/escritura.
3. Mueve cada una de sus cabezas hacia la izquierda o
   hacia la derecha (de forma independiente al resto de las
   cabezas).

Por tanto, la función de transición para
una máquina de Turing con n cintas, es de la forma
d : Q x
G n
® Q
x G n
x {R, L} n donde una transición de la
forma d (q,
(s
1, s
2,…, s n)) = (p,(t 1, t 2, …,
t
n), (X1, X2,
…, Xn)) significa que cambia del estado q a p,
reemplaza s
i por t i en la cinta i y
mueve la cabeza de la cinta i en la dirección
Xi.

Ejemplo: Reconocimiento del lenguaje
{anbn |n³ 1}. Éste es bastante laborioso en
una máquina de Turing con una única cinta. Es mucho
más fácil realizarlo con una máquina de
Turing de dos cintas. Suponiendo que, inicialmente, coloca la
cadena a analizar en la cinta 1 y que q1 es el estado
inicial. Si la cabeza de lectura/escritura de la cinta 1
está situada inicialmente sobre el carácter del
extremo izquierdo de la cadena, las cuatro posiciones siguientes
son fundamentales para el reconocimiento (cualquier otra
transición sería para cadenas mal formadas y se
puede suponer que llega a un estado que no es de
aceptación):

d (q1,
(a, B)) =(q1, (a, a), (R, R))

d (q1,
(b, B)) =( q2, (b, B), (S, L))

d ( q2,
(b, a)) =( q2, (b, a), (R, L))

d ( q2,
(B, B)) =( q3, (B, B), (R, L))

Aunque esta máquina de Turing multicinta parece
bastante distinta y posiblemente más potente que la
máquina de Turing definida originalmente, las dos son
equivalentes en el sentido de que cada una de ellas puede ser
simulada por la otra.

Máquina de Turing
Muldimensional.

La máquina de Turing multidimensional es aquella
que permite que la cinta tenga muchas dimensiones. Por ejemplo,
una cinta de dos dimensiones que se extienda hacia abajo y hacia
arriba, al igual que hacia la derecha y hacia la izquierda.
Dependiendo del estado actual de la máquina de Turing y
del símbolo analizado, cambia de estado, escribe un
símbolo en la celda actual y se mueve a la izquierda, al
derecha, hacia arriaba o hacia abajo. Por tanto, la
función de transición para esta máquina de
Turing será de la forma:

d : Q x
G ® Q x G x {R, L, U, D}

Una máquina de Turing multidimensional simula una
máquina de Turing estándar. Simplemente realizando
todas sus computaciones en una única dimensión. Una
máquina de Turing estándar también puede
simular una máquina de Turing multidimensional y, por
tanto, la complejidad y la flexibilidad adicional que se debe a
la múltiple dimensión, no es una capacidad real.
Para simular una máquina de Turing de dos dimensiones
mediante una máquina de Turing estándar, primero se
asociara una dirección a todas las celdas de la cinta. Una
forma de hacerlo es fijar, de forma arbitraria, un lugar en la
cinta a partir del cual se asignarán las coordenadas a las
celdas de la misma forma que se realiza en un plano de
coordenadas.

Entonces, se usara una cinta de dos pistas para simular
la máquina de Turing. Una pista se encargará de
almacenar el contenido de las celdas y la otra las coordenadas,
utilizando un símbolo (*) para separar los valores de
las coordenadas. Para simular un movimiento de una máquina
de Turing de dos dimensiones, está máquina calcula
la dirección de la celda a la que se moverá la
máquina de Turing dos dimensiones. Entonces, localiza la
pista inferior la celda con dicha dirección y cambia el
contenido de la celda en la pista superior.

Máquina de Turing No
determinista.

La máquina de Turing No determinista es aquella
que para un estado actual y el símbolo actual de la cinta,
puede haber un número finito de movimientos a elegir. Por
lo tanto, la regla de transición d de dicha máquina,
satisface

d (q,
s ) Í Q x G x {R, L}

Por ejemplo, si la máquina de Turing tiene una
transición

d (q1, a)
= {(q1, b, R), (q2, a, L)} entonces los
movimientos

abbq1ab abbbq1b y
abbq1ab abq2bab son posibles.

Ya que cualquier máquina de Turing determinista
es también no determinista, es lógico que una
máquina de Turing determinista se puede simular mediante
una no determinista. También una máquina de Turing
determinista puede simular una no determinista. Por tanto, no se
gana ninguna potencia adicional a causa del no
determinismo.

5.5. HALTING PROBLEM.

Se dice que un proceso es computable o tiene
solución algorítmica cuando puede ser representado
por medio de una máquina de Turing que llega, en
algún momento, a un estado final.

Si la máquina de Turing llega a un estado final
con un sí, se estará haciendo una correspondencia
entre ella y el módelo de decisión. Pero cuando la
máquina no llega a este estado final pueden suceder dos
cosas: que llega a un estado de trampa, de donde ya no salga, o
que sencillamente nunca se pueda saber si terminará o no
con la computación.

Para el primer caso bastará con hacer una
equivalencia entre este estado de trampa y el "no" del modelo de
decisión; pero para el segundo hay que decidir entre
seguir esperando o no el resultado. En 1936 Turing
demostró matemáticamente que existen procesos para
los cuales la máquina nunca terminará con un
sí y nunca terminará con un no. En este caso se
podría esperar toda la eternidad para ver si la
máquina se detiene o no, sin poder llegar a saber si se
detendrá en el siguiente instante. Se dice que el problema
no es computable, o bien, que no es posible decidir, en un tiempo
finito, si el proceso es representable
algorítmicamente.

Los problemas de este tipo reciben el nombre de
problemas indecibles o "problemas no solucionables en forma
algorítmica", y representan una prueba de las capacidades
del método matemático para explorar la realidad
formal del mundo, ya que se está hablando de problemas que
son posibles de describir, pero nunca representar por completo
para todos los casos.

Turing en la búsqueda de los problemas indecibles
generalizó el concepto de
máquina, como se explica a continuación:

La máquina universal de Turing es, el
módelo teórico de la computabilidad; basta con
codificar cualquier máquina particular de Turing en su
cinta para que sea entonces simulada y, por ende, pueda resolver
ese problema particular algorítmicamente. Y con esto es
cuando Turing establece el problema de parada (Halting Problem en
inglés) con la siguiente pregunta: ¿Podrá la
máquina universal determinar si la máquina –
particular – que está siendo simulada se va a
detener (en un estado final) o no?

Supóngase que sí puede: que existe una MT1
que determina si cualquier otra (que llamaremos MT0) se va a
detener o no; es decir, termina con un sí si MT0 se
detiene, y con un no si MT0 no se detiene (véase la figura
5.4). Entonces, también lo podrá hacer para la
codificación de sí misma (es decir,
podrá determinar si MT1 se detendrá para cualquier
caso particular o no).

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Figura 5.4. MT1 termina con un sí,
si MTO se detiene ó

termina con un no, si MT0 no se
detiene.

Ahora si se construye una nueva máquina, MT2, que
se detiene si MT0 no lo hace, y viceversa (véase la figura
5.5). Esto se puede lograr si se hace que MT2 entre en un ciclo
infinito cuando MT0 se detiene (mediante un par de estados de
trampa, que hacen que la operación de la máquina
oscile entre uno y otro).

¿Qué sucede si MT2 trabaja sobre la
codificación de sí misma? Pues que se
detendrá si MT2 no se detiene, y no se detendrá
sí, y sólo sí, se detiene. Esto es una
contradicción total. Lo que quiere decir que tal
máquina no puede existir; lo que a su vez equivale a decir
que el problema que estamos estudiando es indecible.

 Para ver el
gráfico seleccione la opción "Descargar" del
menú superior 

Figura 5.5. MT2 termina con un sí,
si MTO no se detiene

ó termina con un no, si MT0 se
detiene.

En resumen, los pasos fueron:

1. Se supone que se puede construir MT1, que determina
   si MT0 se detiene o no y que, por tanto, también puede
   determinar si ella misma lo hace, cuando trabaja sobre su
   propia codificación.
2. Se construye MT2, que termina con un sí, si
   MT0 no se detiene, y con no si MT0 se detiene mediante un par
   de estados especiales de atrampa que causan que entre en un
   ciclo infinito cuando MT0 llega a un estado final.
3. Cuando MT2 trabaja sobre su propia
   codificación se llega a una contradicción, lo
   cual significa que la suposición del punto 1 es
   inválida.

5.6. HIPÓTESIS DE
CHURCH.

La hipótesis de que el concepto intuitivo de
"función calculable" puede identificarse con la clase de
las funciones parcialmente recursivas se conoce como
hipótesis de Church. Mientras que no podemos esperar una
"demostración" de la hipótesis de Church, puesto
que el concepto informal de "calculable" sigue siendo un concepto
informal, podemos proporcionar evidencia de su carácter de
razonable. Ya que nuestra noción intuitiva de "calculable"
no pone un límite en el número de pasos o la
cantidad de almacenamiento, parecería que las funciones
parcialmente recursivas son intuitivamente calculables, aunque
alguien podría argumentar que una función no es
"calculable" a menos que podamos limitar el cálculo por
adelantado o al menos establecer si el cálculo termina o
no en algún momento.

Podemos concluir entonces que la hipótesis de
Church es el concepto intuitivo de "Función Calculable"
que puede identificarse con la clase de funciones parcialmente
recursivas que son las funciones que realiza una máquina
de Turing, sin embargo no podemos esperar una demostración
de dicha hipótesis, puesto que no se puede definir que es
una función calculable porque dejaría de ser
intuitiva.

EJERCICIOS.

* Ejercicio resuelto.

*5.1. Diseñe una máquina de Turing que
acepte el lenguaje regular a* sobre S ={a, b}, pero que rechace las cadenas que
no pertenecen al lenguaje por medio de un bucle
infinito.

Q ={q1, q2, q3},
S ={a, b},
G ={a, b, B}, F
={q3}, q0 =q1 y
d está definida
mediante la siguiente tabla:

Si encuentra una b, la máquina de Turing pasa al
estado q2, que se mueve siempre hacia la
derecha.

*5.2. Diseñe una máquina de Turing que
acepte el lenguaje {0n 1n | n
³ 1}

Q = (q0, q1, q2,
q3, q4), S ={0, 1}, G ={0,1,X,Y,B}, F ={q4},
q0 =q0 y donde d está definida mediante la
siguiente tabla:

*5.3. Mostrar la ejecución de la máquina
de Turing del ejercicio 5.2., cuando se parte de la siguiente
configuración: 011, partiendo del estado
inicial.

q00011 Xq1011 X0q111 Xq20Y1 q2X0Y1
Xq00Y1
XXq1Y1 XXYq11 XXq2YY Xq2XYY XXq0YY
XXYq3Y XXYYq3 XXYYBq4

*5.4. Diseñe una máquina de Turing que
complemente las cadenas sobre el alfabeto S ={a, b}.

Q ={q1, q2, q3},
S ={a, b},
G ={a, b, B}, F
={q3}, q0 =q1 y
d está definida
mediante la siguiente tabla:

*5.5. Diseñe una máquina de Turing que
acepte el lenguaje {XÎ {a, b}*½ X contiene la subcadena
aba}.

Q ={q1, q2, q3,
q4, q5}, S ={a, b}, G ={a, b, B}, F ={q5}, q0
=q1 y la función d , está definida por la siguiente
tabla:

*5.6. Diseñe una máquina de Turing que
acepte el lenguaje {XÎ {a, b}*½ X termina con aba}.

Q ={q1, q2, q3,
q4, q5, q6}, S ={a, b}, G ={a, b, B}, F ={q6},
q0 =q1 y la función
d , está
definida por la siguiente tabla:

*5.7. Diseñe una máquina de Turing sobre
el alfabeto S
={a, b} para la función suma ¦ (n, m) = n + m,
representando los enteros positivos mediante cadenas de a’s
. Así, el entero positivo n estaría representado
por an. La función se implementa mediante la
transformación de anbam en
an+mb.

Q ={q1, q2, q3,
q4, q5 }, S ={a, b}, G ={a, b, B}, F ={q5}, q0
=q1 y la función d , está definida por la siguiente
tabla:

Esta máquina de Turing desplaza la b hacia
el final a la derecha de an+m. Para ello, se crea una
a extra. La máquina de Turing "recordará"
que se ha creado una a al pasar al estado q2
una vez que se ha encontrado la b, y entonces se
escribirá una b sobre la a que está
al final de la cadena. Cuando termina, la máquina de
Turing sitúa su cabeza de lectura/escritura sobre la
a que se encuentra más a la izquierda.

5.8. Diseñe una máquina de Turing que pare
cuando se le presente una cadena del lenguaje
{anbm ½ n, m ³ 0 y los dos no son cero a la vez}.
Comenzar el procesamiento con la cabeza situada sobre el primer
símbolo (el que está más a la izquierda) de
la cadena.

9. Diseñar una máquina de Turing para cada
   uno de los siguientes lenguajes:

1. {a2n ½ n ³ 0} sobre S ={a, b}.
2. {an bn cn
   ½ n
   ³ 0}
   sobre S ={a,
   b, c}.

5.10. Diseñar una máquina de Turing que
acepte el lenguaje {anbn ½ n ³ 0}. Transformar la
máquina de Turing para que no pare si encuentra una cadena
no aceptable.

5.11. Mostrar la ejecución de la máquina
de Turing del ejercicio 5.7., cuando se parte de las siguientes
configuraciones: a2ba3 y a2b,
partiendo del estado inicial.

5.12. Construir una máquina de Turing de tres
pistas que reste el número binario de la segunda pista del
número binario de la primera pista y deje el resultado en
la tercera pista.

5.13. Diseñe una máquina de Turing para
calcular la función n2.

5.14. Construir una máquina de Turing de dos
cintas que reconozca el lenguaje {wwI ½
w Î
{a, b}+}. Supóngase que, inicialmente,
las cadenas a analizar están situadas en la cinta
1.

CAPÍTULO VI

APLICACIONES A LENGUAJES

Objetivo:

El alumno conocerá la relación que
existe entre los lenguajes y autómatas y como éstos
ayudan en el diseño e implementación de los
lenguajes de programación.

6.1. DISEÑO DE LENGUAJES DE
PROGRAMACIÓN.

6.2. IMPLEMENTACIÓN DEL COMPILADOR PARA EL
LENGUAJE

6.2.2. Implementación de una Gramática
Libre de Contexto.

Para ver
este capítulo seleccione la opción "Descargar" del
menú superior

BIBLIOGRAFÍA

GLOSARIO

ANEXO 1 ALFABETO GRIEGO

ANEXO 2
ABREVIATURAS TÉCNICAS

DEDICATORIAS

Gracias
Dios:

Por permitirme gozar el milagro de la
vida y darme la oportunidad de ver realizado otro de mis
sueños. Siempre albergaste en mí la esperanza de
que este día llegaría.

Mil gracias a mis padres Samuel y
Martha Laura.

Gracias por apoyarme siempre en todos
mis proyectos, por
ser un ejemplo de superación que siempre influye en
mí en todos los aspectos y sobre todo por compartir
conmigo su amor.

Gracias a Alberto, Arturo, Daniel,
Angela y Jessica.

Ustedes también contribuyeron
al logro de esta meta. Gracias por darme aparte de su amor su
apoyo incondicional.

A mis amigos del grupo byte Adriana,
Luz
María, Esther, Teodora, Aurelio, y Saúl, y
especialmente a Kitzya, Graciela, Leobardo y Alfredo por que
compartieron conmigo este hermoso sueño que espero no sea
el último. Gracias por brindarme su amistad y
apoyo.

A mi honorable
jurado:

Ing. José Enrique Torres
Montoya

M.C. José Hernández
Silva

M.E. Ofelia Gutiérrez
Giraldi

Lic. Martha Martínez
Moreno

Agradezco su colaboración
durante la revisión del trabajo.
Gracias por sus sugerencias y aportaciones.

A mi asesor, el Ing, José
Enrique Torres Montoya.

Siempre agradeceré todo el
apoyo que me brindo para hacer de este trabajo una meta
alcanzable y lograr mi sueño de ser Ing. En Sistemas
Computacionales.

Martha Elizabeth
Domínguez Olmos

SECRETARIA DE EDUCACION PUBLICA. DIRECCION GENERAL DE
INSTITUTOS TECNOLOGICOS

INSTITUTO TECNOLOGICO
DE VERACRUZ