Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

Ejemplo 3.6
Minimizar el AFD representado en el dígrafo de la Figura 3.11.
0
q s 0
0 r
1 0
p 1 1
1 1
1
u t
0
0

Figura 3.11: Dígrafo del AFD a ser minimizado.

La definición formal de este autómata es:
f: 0 1
AFD = ( Σ E , Q, q 0 , A, f )
→p q u
Σ E = {0, 1} q s t
Q = {p, q, r, s, t, u} r s t
q0 = p s r t
t u s
A = {u}
*u u q

Tabla 3.10: Definición y función de transición f del Ejemplo 3.6.

La primera partición del conjunto de estados separa al estado final del resto:
Q/E0 = {{p, q, r, s, t}, {u}}
y los sucesivos conjuntos cocientes son identificados a partir de la función de transición, verifican-
do el comportamiento común de los miembros de las clases de estados:
Q/E1 = {{p}, {q, r, s}, {t}, {u}}
Q/E2 = {{p}, {q, r, s}, {t}, {u}} = Q/E1 = Q/E = {c0, c1, c2, c3}
donde c0 = {p}, c1 = {q, r, s}, c2 = {t} y c3 = {u}
Una vez asignados los nuevos nombres a las clases de estados se representa a continuación
la definición formal y grafo del AFD mínimo:
AFD = (Σ E , Q, qo, A, f )
donde E = {0, 1}, Q = {c0, c1, c2, c3}, q0 = c0, A = { c3 }.
La función de transición f se muestra en la Tabla 3.11 y el grafo en la Figura 3.12.

f: 0 1
→ c0 c1 c3
c1 c1 c2
c2 c3 c1
* c3 c3 c1

Tabla 3.11: Función de transición.

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 1

 Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

0
1
0 c2
c0 c1
1 1

1 c3 0
0

Figura 3.12: Dígrafo del AFD minimizado.

Ejemplo 3.7
En la Tabla 3.12, se presenta la función de transición de un AFD y se pide realizar un análisis
completo que incluya:
f: a b
a) Completar la definición formal. → p1 p3 p4
b) Representar su dígrafo. p2 p8 p4
c) Verificar que el AFD sea conexo. p3 p6 p5
d) Minimizar el autómata.
p4 p5 p6
e) Presentar la definición formal y grafo del AFD equivalente mínimo.
f) Identificar el lenguaje reconocido. * p5 p1 p5
g) Mostrar la aceptación de una cadena de largo seis mediante el p6 p6 p2
árbol de configuraciones y plano de estados-entradas. p7 p5 p8
p8 p6 p5
Solución
Tabla 3.12: función de transi-
a) La definición formal queda completa con: ción del Ejercicio 3.7
AFD = ( Σ E , Q, q 0, A, f )
donde Σ E = {a, b}, Q = {p1, p2, p3, p4, p5, p6, p7, p8}, q 0 = p1 y A = {p5}
b) Su dígrafo se presenta en la Figura 3.13:

b
p5 a
b p7
a p3
a a b
p1
a b
a
b b a
p4 p6 p8

b a
b
p2

FiguraFigura
3.13: 3.13:
Dígrafo del del
Digrafo AFD de de
AFD la laTabla 3.12.
tabla 3.12.
c) A partir de la inspección de la función de transición de la Tabla 3.12, se deduce que el AFD no
es conexo, ya que el estado p7 no es accesible desde el estado inicial p1.

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 2

 Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

b
p5 a p7
b
a p3
a a b
p1
a b
a
b b a
p4 p6 p8

b a
b
p2

Figura 3.14: Dígrafo del AFD conexo de la Tabla 3.12.

En la Figura 3.14, se muestra con líneas de punto el estado inaccesible y las correspondientes
transiciones, que son eliminadas del autómata, ya que no modifican su comportamiento.
d) Para minimizar el autómata, se identifica el conjunto cociente inicial a partir de su definición
formal y luego, los sucesivos conjuntos cocientes a partir del conjunto cociente anterior y la
función de transición. Se prosigue hasta obtenerse dos conjuntos cocientes sucesivos idénticos
a partir del conjunto cociente inicial, que es:
Q/E0 = P10  P20, donde P10 = Q – A = {p1, p2, p3, p4, p6, p8} y P20 = A = {p5}
Q/E0 = {{p1, p2, p3, p4, p6, p8}, {p5}}
- A partir de Q/E0 y la función de transición se comprueba que:
f(p1,a) = p3  P10 y f(p1,b) = p4  P10 → p1  P11
f(p2,a) = p8  P10 y f(p2,b) = p4  P10 → p2  P11

f(p3,a) = p6  P10 y f(p3,b) = p5  P20 → p3  P21

f(p4,a) = p5  P20 y f(p4,b) = p6  P10 → p4  P31
f(p5,a) = p1  P10 y f(p5,b) = p5  P20 → p5  P41
f(p6,a) = p6  P10 y f(p6,b) = p2  P10 → p6  P11
f(p8,a) = p6  P10 y f(p8,b) = p5  P20 → p8  P21

luego P11 = {p1, p2, p6}, P21 = {p3, p8}, P31 = {p4}, P41 = {p5} es decir que:
Q/E1 = {{p1, p2, p6}, {p3, p8}, {p4}, {p5}}
- Se repite el procedimiento a partir de Q/E1 y de la función de transición:
f(p1,a) = p3  P21 y f(p1,b) = p4  P31 → p1  P12
f(p2,a) = p8  P21 y f(p2,b) = p4  P31 → p2  P12
f(p3,a) = p6  P11 y f(p3,b) = p5  P41 → p3  P22
f(p4,a) = p5  P41 y f(p4,b) = p6  P11 → p4  P32
f(p5,a) = p1  P11 y f(p5,b) = p5  P41 → p5  P42
f(p6,a) = p6  P11 y f(p6,b) = p2  P11 → p6  P52
f(p8,a) = p6  P11 y f(p8,b) = p5  P41 → p8  P22

luego P12 = {p1, p2}, P22 = {p3, p8}, P32 = {p4}, P42 = {p5}, P52 = {p6} es decir que:
Q/E2 = {{p1, p2}, {p3, p8}, {p4}, {p5}, {p6}}
- Se repite el procedimiento a partir de Q/E2 y de la función de transición:
f(p1,a) = p3  P22 y f(p1,b) = p4  P32 → p1  P13
f(p2,a) = p8  P22 y f(p2,b) = p4  P32 → p2  P13
f(p3,a) = p6  P52 y f(p3,b) = p5  P42 → p3  P23
f(p4,a) = p5  P42 y f(p4,b) = p6  P52 → p4  P33

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 3

 Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

f(p5,a) = p1  P12 y f(p5,b) = p5  P42 → p5  P43

f(p6,a) = p6  P52 y f(p6,b) = p2  P12 → p6  P53
f(p8,a) = p6  P52 y f(p8,b) = p5  P42 → p8  P23

luego P13 = {p1, p2}, P23 = {p3, p8}, P33 = {p4}, P43 = {p5}, P53 = {p6} es decir que:
Q/E3 = {{p1, p2}, {p3, p8}, {p4}, {p5}, {p6}} = Q/E2 = Q/E
Para completar el proceso, se asignan luego nuevos nombres a los conjuntos de esta-
dos indistinguibles:
c0 = {p1, p2}, c1 = {p3, p8}, c2 = {p4}, c3 = {p5}, c4 = {p6}
Se deja al lector comprobar que el mismo conjunto cociente puede también ser obtenido
con el procedimiento de los esquemas de agrupamiento de estados utilizado en el Ejemplo
3.5.
e) La definición formal y dígrafo del AFD equivalente mínimo se presentan a continuación en la
Tabla 3.13 y Figura 3.15:
AFD min = ( Σ E , Q, q 0 , A, f ) f: a b
Σ E = {a, b} → c0 c1 c2
c1 c4 c3
Q = {c0, c1, c2, c3, c4}
c2 c3 c4
q 0 = c0
* c3 c0 c3
A = {c3}
c4 c4 c0

Tabla 3.13: Definición formal del AFD mínimo y función de transición.

c3
b
a a b
a c1
c0
b c2 a
b
b c4
a

Figura 3.15: Dígrafo del AFD mínimo.

f) Para identificar el lenguaje que es reconocido por un AFD hay dos opciones: i) determinar las
reglas de producción de la gramática a partir de la función de transición del autómata y ii) indu-
cir el lenguaje a partir de inspeccionar el comportamiento del AFD. La primera opción es la más
recomendable por tratarse de un proceso sistemático, y una vez identificadas las reglas de
producción se deducen las formas que toman las sentencias del lenguaje. Como este tema se-
rá presentado en el próximo capítulo, por el momento se utilizará la segunda opción, que impli-
ca un proceso de inspección que, en algunos casos, puede ser muy laborioso y es susceptible
a errores y omisiones. Para facilitar la tarea, es siempre recomendable trabajar sobre el AFD
ya minimizado.
Estudiando el comportamiento del autómata, puede deducirse que reconoce cadenas que ter-
minen con los sufijos abbp o babp (para p0) y que inicien con cualquier concatenación de ca-
denas que lo restituyan al estado inicial:
β1 = (abbn1a)m1 β2 = (babn2a)m2 β3 = (aaan3b)m3 β4 = (bban4b)m4
donde ni, mj  0 para i, j=1, 2, 3, 4, con los mismos sufijos.
Es así que a partir de la identificación de estas cadenas se puede hacer una descripción alge-
braica del lenguaje que es reconocido por el AFD, que aquí es llamado M y toma la siguiente

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 4

 Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

forma:
L(M) = { /  = ((β 1 β 2 β 3 β 4 ) i abb j ) k ((β 1 β 2 β 3 β 4 ) l bab m ) n ó
((β 1 β 2 β 3 β 4 ) i bab j ) k ((β 1 β 2 β 3 β 4 ) l abb m ) n , con i, j, k, l, m  0; n  1}
Como ya fue anticipado, en el próximo capítulo, se presentará un procedimiento sistemático
para deducir las reglas de producción de la gramática que genera el lenguaje aceptado por un
AFD y que permitirá confirmar las formas generales propuestas, lo que se deja reservado al
lector.
g) Para mostrar el comportamiento del autómata de selecciona una cadena tal como
=bbbabbL(M), que responde a la forma general β4abbp. Con el fin de seguir su desempeño
en el proceso de aceptación de la cadena, se utilizan las representaciones del árbol de configu-
raciones o descripciones instantáneas y el plano estados-entradas, que son mostrados en las
Figuras 3.16 y 3.17.

(c0 , bbbabb) Configuración inicial

(c2 , bbabb)

(c4 , babb)

(c0 , abb)

(c1 , bb)

(c3 , b)

(c3 , λ) Configuración final

Figura 3.16: Árbol de descripciones instantáneas.

c0 b b b a b b

c1
c2
c3
c4

Figura 3.17: Representación del plano estados-entradas.

Ejemplo 3.8
Como se señaló en el Capítulo 1, la construcción de modelos es una actividad fundamental en el
desarrollo de software y, para ello, suelen utilizarse máquinas de estados. En este caso, se pro-
pone la definición del autómata finito que represente el funcionamiento de un reproductor de au-
dio; en la actualidad de música almacenada en tarjetas de memoria, CD o DVD y, anteriormente,
sobre cinta magnética. Debe notarse que cualquiera sea la tecnología de almacenamiento, el pro-
blema sigue siendo el mismo: reconocer los comandos ingresados al reproductor por el usuario.
Además, debe también reconocerse que se ha alcanzado el extremo inicial o final de la informa-
ción almacenada, en este caso, música (supondremos funcionamiento circular).
En necesario relacionar las señales externas a ser reconocidas por el autómata con el signifi-
cado de las mismas en el contexto del equipo representado y lo mismo ocurre con los estados
previstos, donde cada uno de ellos representa una condición de operación. Con este fin, las seña-
les de entrada son definidas en la Tabla 3.14 y los estados previstos son definidos en la Tabla
3.15:

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 5

 Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

Comandos reconocidos Condiciones del equipo

símbolo significado símbolo significado
a PLAY p OFF
b FORWARD q ON
c STOP r RETROCEDE
d PAUSA s AVANZA
e REWIND t PAUSA
f Marca de inicio/fin

Tabla 3.14: Señales reconocidas. Tabla 3.15: Estados propuestos.

a) Definición formal del autómata finito:

AFD = ( Σ E , Q, q 0, A, f )
Σ E = {a, b, c, d, e, f}
Q = {p, q, r, s, t}
q0 = p
A = {p}
Donde la función de transición f es presentada en la Tabla 3.16:
f: a b c d e f
→p * q s p p r p
q q s p t r q
r q s p r r r
s q s p s r s
t t t t q t t

Tabla 3.16: Función de transición del AF AF

Tabla 3.16: Función de transición del .
b) Dígrafo: A partir de la definición formal anterior se desarrolla el dígrafo del autómata finito
que cumple la función de un reproductor de audio, el cual se muestra en la Figura 3.18.
Nótese que, tal como fue definida esta máquina, el estado inicial es también su estado de
aceptación.
a f
a d
cdf c
p q t
c a
d
a abcef
c

e b
b
e
b
def r s bdf
e

Figura 3.18: AF para un reproductor de audio.

c) Minimización del autómata finito: el objeto es verificar la posible existencia de estados in-
b distinguibles. Se identifica el conjunto cociente inicial y luego los sucesivos conjuntos co-
cientes hasta alcanzar dos conjuntos cocientes sucesivos idénticos. Estos resultan ser:
Q/E0 = {{q, r, s, t}, {p}}
Q/E1 = {{q, r, s}, {t}, {p}}
Q/E2 = {{q}, {r, s}, {t}, {p}}
Q/E3 = {{q}, {r, s}, {t}, {p}}
El proceso de minimización muestra que los estados r y s son equivalentes o indistingui-
bles, ya que tienen idéntico comportamiento en cuanto a sus transiciones desde y hacia los

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 6

 Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

demás estados. Esto es así en el autómata finito del modelo. Sin embargo, en el equipo
reproductor de audio, el estado r corresponde a la acción de retroceder sobre el medio de
entrada, mientras que el estado s está asociado a un movimiento en sentido opuesto, es
decir, adelantar sobre el mismo medio. Esta aparente inconsistencia no es tal, ya que al
suponer el funcionamiento circular, al avanzar más allá del último tema de música se conti-
núa con el primero y al retroceder, en el primero, se continúa con el último.
Ejemplo 3.9
Una de las principales aplicaciones de los autómatas finitos es la identificación de los componen-
tes del texto de un documento, pudiendo estar inserto ya sea en un corrector ortográfico o en un
compilador, entre otros. En este último caso, el autómata finito es denominado analizador léxico
(en realidad, constituye la rutina de reconocimiento del módulo denominado con ese nombre) y
dentro de un compilador su misión es identificar las palabras reservadas, variables, constantes,
operadores y demás elementos que forman las sentencias del programa.
Debe tenerse presente que el analizador léxico recibe el programa fuente como una larga ca-
dena de caracteres, con espacios y caracteres especiales de control intercalados (<CR>, <LF>,
<TAB>, etcétera) y debe separar e identificar los componentes del lenguaje, llamados componen-
tes léxicos o tokens. Las posibles secuencias de caracteres que definen un token son verificadas,
ya que deben responder a ciertas expresiones regulares, y clasificadas. Luego se les asigna una
dirección en la tabla de símbolos y sirven de base a la siguiente etapa del proceso de compilación,
que es denominada de análisis sintáctico, tal como se describe en detalle en el Apéndice A.
En este ejemplo, se desea construir un analizador léxico que, en un programa escrito en len-
guaje Java, identifique los valores numéricos (constantes) en sus diferentes tipos (int, float, double)
y notaciones, cuya representación es resumida en la Tabla 3.17, mostrada a continuación.

Tipo Notación Representación Caracter (n)

Decimal [ ± ] nnn…n 0…9
Entero Octal [ ± ] 0nnn…n 0…7
Hexadecimal [ ± ] 0xnnn…n 0…F
Dec. s/ exp. [ ± ] n…n.n…n 0…9
Real
Dec. c/ exp. [ ± ] n.n…nE[ ± ]nn 0…9

Tabla 3.17: Representación de constantes numéricas en Java.

Se quiere entonces determinar: a) el grafo del autómata finito que cumple la función de anali-
zador léxico y b) su definición formal.
a) Definición de la simbología y definición formal
Para resolver el problema, se propone un AF que opere los símbolos especiales definidos
en la Tabla 3.18 y con tantos estados de aceptación como las diferentes formas numéricas que
deben ser identificadas, que en este caso son cinco (tres formas enteras y dos reales, Tabla
3.19).
Simbología especial Estados de aceptación
símbolo representa símbolo significado
b blanco, <cr>,<lf>,<tab> c0 entero decimal
; fin de sentencia c1 real sin exponente
. punto decimal c2 real con exponente
+,- signos de valor numérico c3 entero hexadecimal
β  0..9 , + , - c4 entero octal
Tabla 3.18: Señales reconocidas. Tabla 3.19: Estados de aceptación.

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 7

 Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

Simbología especial Estados de aceptación

símbolo representa símbolo significado
b blanco, <cr>,<lf>,<tab> c0 entero decimal
; fin de sentencia c1 real sin exponente
. punto decimal c2 real con exponente
+,- signos de valor numérico c3 entero hexadecimal
β  0..9 , + , - c4 entero octal
Tabla 3.18: Señales reconocidas. Tabla 3.19: Estados de aceptación.
Definición formal:
AFD = ( E, Q, q0, A, f ),
donde:
E = { 0, ..., F, +, - , b, ; , . , E, x }
Q = { p, q, r, s, t, u, v, w, x, y, z, c0, c1, c2, c3, c4}
q0 = p
A = {c0, c1, c2, c3, c4}

f: 0 1..7 8..9 A..F +,- x . E b,; β

->p r t t q p
q r t t
r z y s c0
s u u u
t t t t c0
u u u u v c1
v x x x w
w x x x
x x x x c2
y y y y y c3
z z z c4
*c0
*c1
*c2
*c3
*c4

TablaTabla
3.20: Función
3.20: Funciónde
detransición delanalizador
transición del analizador léxico.
léxico.
Nótese que el AFD llegará a uno de los estados finales cuando complete la identificación de
un componente numérico del código del programa. El estado alcanzado dependerá del tipo y no-
tación del elemento encontrado. Luego el AFD debe regresar al estado inicial para esperar la llega-
da de la próxima cadena y continuar operando hasta completar el análisis léxico, destinado a iden-
tificar los números presentes en todas las sentencias del programa.
También es necesario destacar que el símbolo β es genérico, representando cualquier carác-
ter inválido como inicio de una cadena que contenga un número. Es decir que ante la lectura de
cualquier símbolo a  { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 , + , - } el autómata permanecerá en el estado
inicial “p”.
b) Grafo del AFD (analizador léxico)

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 8

 Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

β
1..9 0..9
p
+, -
1..9 ;,b c0
q t
0 ;,b
0
. 0..9
r
. s 0..9 u ;,b c1

E
0..9
+, - 0..9 ;,b c2
v w x

0..9

0..F
x ;,b
y c3

0..7
1..7 ;,b c4
z

Figura 3.19: Autómata finito para un analizador léxico.

Autómatas finitos bidireccionales

Aspectos generales
Los autómatas finitos leen siempre la cadena de entrada de izquierda a derecha. Esto tiene varias
consecuencias: i) cada símbolo de la cadena es leído una única vez, ii) al completarse la lectura,
la cadena es aceptada o no, según se alcance un estado de aceptación, iii) puede anticiparse la
cantidad de intervalos de tiempo necesarios para evaluar la cadena, que será igual a su largo y iv)
en todo momento está claramente definida la subcadena pendiente de ser leída por el autómata.
Esto último soporta el concepto de configuración o descripción instantánea del AFD.
Otorgando a un AFD la capacidad de decidir el sentido del movimiento del cabezal en cada in-
tervalo de tiempo queda conceptualmente definido el AFDB (Autómata Finito Determinista Bidirec-
cional). Como es de esperar, en la definición del autómata se debe incorporar una función de mo-
vimiento, que defina el sentido del movimiento del cabezal en cada estado y ante cada símbolo de
entrada. Además, debe quedar claramente establecido el sector de la cinta en el que el autómata
puede operar. Para ello, se incorporan dos símbolos especiales que identifican el inicio y el final
del intervalo de cinta de entrada a ser analizado.
Con esto, se obtiene un autómata que cambia las condiciones antes señaladas, a saber: i)
Cada símbolo de entrada pueden ser leído varias veces, ii) no hay ninguna condición que indique
el fin de la lectura de la cadena, iii) no es posible anticipar la cantidad de intervalos de tiempo re-
queridos para evaluar la cadena y iv) el concepto de cadena que resta de ser leída desaparece.
Se suma aquí una consecuencia novedosa, que es la real posibilidad de que ciertas cadenas de
entrada lleven al AFDB a un ciclo cerrado que no conduzca a nada, es decir, un ciclo infinito.
Los AFDB son escasamente considerados en la literatura, a pesar de que presentan una for-
ma de introducir gradualmente la máquina de Turing y de que por sí mismos dan lugar a solucio-
nes muy interesantes. Hubo dos trabajos, debidos a Rubin y Scout (1959) y Shepherdson (1959),
que a través de enfoques diferentes se ocuparon de demostrar la equivalencia de los AFD y AFDB.
En la actualidad, los AFDB son principalmente utilizados en el análisis de la complejidad de algo-
ritmos.

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 9

 Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

Definición del AFDB

A partir de lo ya expuesto, el AFDB se define como:
AFDB = (Σ E , , Q, q 0, A, f)
donde:
ΣE : Alfabeto de símbolos de entrada
 : Alfabeto de cinta,  = ΣE U {├ , ┤}
Q : Conjunto finito, no vacío, de estados posibles.
q0 : Estado inicial de operación, q0  Q
A : Conjunto de estados de aceptación, A  Q
f : Función de transición, f: Q   → Q x {I, N, D}
Sobre la definición del AFDB nótese que:
a) El alfabeto de cinta  se forma con el alfabeto de entrada y dos símbolos auxiliares destina-
dos a marcar el inicio y fin de la cinta de entrada, normalmente denominados BOT (Beginning
Of Tape, ├) y EOT (End Of Tape, ┤); estos símbolos nunca son de entrada.
b) El AFDB tiene normalmente un único estado de aceptación, ya que al poder ser releída la ca-
dena siempre podrá ser definido con uno solo de estos estados, lo que no es obvio ni es de-
mostrado aquí.
c) La función de transición es definida usando el alfabeto ampliado , ya que el autómata debe reco-
nocer todos los símbolos que pueda contener la cinta de entrada y tomar decisiones a partir de
ellos.
d) La función de transición f reúne, tal como está definida, dos funciones claramente distingui-
bles: la de transición de estado a estado t:Q→Q y la del sentido del próximo movimiento
del cabezal de entrada m:Q→{I, N, D}.
e) El alfabeto de movimientos del cabezal contiene tres símbolos {I, N, D} que significan: iz-
quierda (I), neutro (N) y derecha (D). Podría incluso agregarse un símbolo de detención de
operaciones P; en el tratamiento de las máquinas de Turing en capítulos posteriores se efec-
tuará este agregado y se comentará su función.
f) Un AFDB que contemple en todos los casos el movimiento del cabezal hacia la derecha se convier-
te en un AFD convencional, por lo que puede reconocerse a este último como un caso particular del
primero.
Conceptos asociados a los AFDB
Aceptación de cadenas
Una cadena es aceptada por el AFDB cuando éste ha alcanzado un estado de aceptación y la ca-
dena ha sido leída por lo menos una vez. Esto último significa que la cantidad de intervalos de
tiempo demandados por la aceptación será igual o mayor al largo de la cadena en cinta. Nótese
que si la cantidad de intervalos de tiempo necesarios para aceptar una cadena es igual a su largo,
el AFDB se ha comportado como un AFD convencional.
Algunos autores como Cases Muñoz (2002) plantean la aceptación de una cadena cuando se
ha alcanzado un estado de aceptación y el cabezal de lectura está a la derecha de la cadena de
entrada (sobre el símbolo de fin de cinta, EOT), criterio que es compartido y adoptado en lo sucesi-
vo en este texto.
Configuración
Al haber desaparecido en el AFDB el concepto de cadena a ser leída, debe replantearse la defini-
ción de configuración o descripción instantánea, que había sido propuesta para los AFD conven-
cionales.
Luego, para la completa definición de la condición en la que se encuentra un AFDB en un ins-
tante dado se requieren tres componentes, que son: i) el estado actual, ii) el contenido de la cinta
de entrada y iii) la posición del cabezal. Para esto último, se adopta la convención de que el sím-

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 10

 Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

bolo de inicio de cinta (BOT) está en la posición 0 y el contador se incrementa hacia la derecha, lo
que implica que el primer carácter de la cadena de entrada está en la posición 1.
Según este criterio, la configuración Kt de un AFDB que opera sobre una cierta cadena de en-
trada , que en el instante t está en el estado q y con el cabezal en la posición k es:
K t = (q, ├┤, k)
Bajo esta definición, la configuración inicial toma la forma:
K 0 = (q 0 , ├┤, 0)
y la configuración final de aceptación, bajo el criterio adoptado es:
K A = (q A , ├┤, n), en donde q A A y n=+1
Una forma alternativa de representar la configuración de un AFDB es:
K t = qβ
Donde q es el estado actual del autómata,  el prefijo de la cadena de entrada  que antece-
de al cabezal y β el sufijo que sigue al cabezal (=β). Según este criterio, la configuración ini-
cial es K 0 =q 0  y la final K A =q A .
Lenguaje reconocido por el AFDB
Usando a la notación de movimientos entre configuraciones definida para los autómatas finitos, el
lenguaje L que es aceptado por un autómata finito bidireccional M puede definirse en símbolos
como:
L(M) = { / E* y q 0 ├─* q A , qAA}
El problema de la parada
Ya fue anticipado que el AFDB puede quedar atrapado en un ciclo cerrado y esto puede ser reco-
nocido, cuando al operar sobre una cadena de entrada, se repita una misma configuración. Siendo
finitos el conjunto de estados posibles y la cinta de entrada, aunque con cierto esfuerzo, esta si-
tuación puede determinarse entonces por un algoritmo.
Extensión al tratamiento de palabras
La extensión de la función de transición para describir lo que ocurre a partir de cada estado si se
recibe una secuencia concatenada de los símbolos de entrada en lugar de recibir símbolos aisla-
dos, es realizada al igual que en el AFD. Aunque no la explicitaremos aquí, es importante notar que
en este caso la extensión debe incluir también la función de movimiento, ya que esta última es
determinante en el comportamiento del AFDB.
Equivalencia entre AFDB y AFD
El movimiento del cabezal en dos sentidos no brinda ninguna capacidad adicional con respecto al
AFD, lo que implica que todo AFDB tiene un AFD equivalente, lo que aquí no es demostrado. El ra-
zonamiento inverso ya fue establecido al admitirse que los AFD son un caso particular del AFDB.
Ejemplo 3.10
Proponer un AFDB que resuelva el problema de aceptar las cadenas que responden a la forma
general =(a+b) * ba del Ejemplo 3.5.
En la solución que aquí se propone el autómata busca el final de la cadena y luego retrocede
para asegurarse de que los dos últimos símbolos corresponden al sufijo ba. De esta manera, el
problema se circunscribe a analizar este sufijo, prescindiendo totalmente del prefijo que lo antece-
de, que puede no existir. En caso de que el sufijo no cumpla la condición requerida el autómata
arriba a un estado de error que aquí es identificado como c4. El grafo del AFDB es el siguiente:

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 11

 Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

a,D ├,D
b,D a, I b,D
┤, I s
p q r
b,D a,D a,D
├,D ├,D ┤,N
t
a,D

Figura 3.20: Grafo del AFDB del Ejemplo 3.10.

La definición formal del AFDB es la que se plantea a continuación:
AFDB=(Σ E , , Q, q 0 , A, f) f: a b ├ ┤
Σ E = {a, b} →p p ,D p ,D p ,D q ,I
 = {a, b, ├, ┤} q r ,I t ,D t ,D
Q = {p, q, r, s, t} r t ,D s ,D t ,D
q0 = p *s s ,D s ,N
A = {s} t t ,D

Tabla 3.21: Función de transición.

Nótese que la función f ha sido definida como parcial, obviando establecer transiciones inne-
cesarias o para situaciones imposibles.
A efectos de estudiar el comportamiento del AFDB, se considera una cadena que responde a
la forma general ya definida , tal como =abbba y, para ello, se recurre al árbol de descripciones
instantáneas o árbol de configuraciones, que es representado en la Figura 3.21.
En el árbol, puede verse que habiendo terminado de leer la cadena y estando el cabezal so-
bre el símbolo de fin de cinta, el autómata queda en un estado de aceptación, por lo cual la cade-
na es aceptada.

(p, ├ a b b b a ┤ , 0) Configuración inicial

(p, ├ a b b b a ┤ , 1)

Búsqueda (p, ├ a b b b a ┤ , 2)
del final de
la cadena
avanzando (p, ├ a b b b a ┤ , 3)
hacia la
derecha (p, ├ a b b b a ┤ , 4)

(p, ├ a b b b a ┤ , 5)

(p, ├ a b b b a ┤ , 6)

(q, ├ a b b b a ┤ , 5)
Comprobación
del sufijo “ba”
requerido para (r, ├ a b b b a ┤ , 4)
aceptar la
cadena (s, ├ a b b b a ┤ , 5)

(s, ├ a b b b a ┤ , 6) Configuración final

Figura 3.21: Árbol de configuraciones de aceptación de abbba.

Una alternativa muy conveniente para visualizar el comportamiento de un AFDB es utilizar el
esquema que se representa en la Figura 3.22, donde la cinta es representada una única vez y se

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 12

 Unidad 3: Máquinas Secuenciales y Autómatas Finitos Deterministas (continuación)

muestra el movimiento del cabezal sobre la misma. El símbolo correspondiente al estado de la

máquina sirve a su vez para mostrar la posición del cabezal y los cambios de sentido se dibujan
en diferentes líneas horizontales por razones de claridad. Ésta es una representación muy utiliza-
da por la literatura para los autómatas que se mueven en dos sentidos.

├ a b b b a ┤
p p p p p p p

r q

s s

Figura 3.22: Esquema de movimientos al aceptarse la cadena abbba.

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

APUNTE DE CÁTEDRA SSL – 2020 - GIRÓ, VÁZQUEZ, MELONI, CONSTABLE 13