1. No category

1
Curso Básico de Computación
2.1 Autómatas finitos y expresiones
regulares
2.5 Expresiones Regulares
Los lenguajes aceptados por un AF son facilmente descritos por una simple
expresión llamada expresión regular.
Sea Σ un conjunto finito de sı́mbolos y sean L, L1 y L2 conjuntos de cadenas de Σ∗ . La concatenación de L1 y L2 , denotada por L1 L2 , es el conjunto
{xy | x esta en L1 e y esta en L2 }. Definimos L0 = {} y Li = LLi−1 para
toda i ≥ 1. La cerradura de Kleene de L, denotada por L∗ , es el conjunto
∗
L =
∞
[
Li
i=0
y la cerradura positiva de L, denotada por L+ es el conjunto
+
L =
∞
[
Li
i=1
+
Note que L contiene a si y sólo si L la contiene.
Ejemplo:
Sea L1 = {10, 1} y L2 = {011, 11}. Entonces L1 L2 = {10011, 1011, 111}.
Tambien
{10, 11}∗
= {, 10, 11, 1010, 1011, 1110, 1111, . . . }
Sea Σ un alfabeto. Las expresiones regulares sobre Σ y los conjuntos que ellas
denotan son definidas recursivamente como:
1) φ es una expresión regular y denota al conjunto vacı́o.
2) es una expresión regular y denota al conjunto {}.
3) Para cada a en Σ, a es una expresión regular y denota al conjunto {a}.
4) Si r y s son expresiones regulares que denotan los lenguajes R y S, respectivamente, entonces (r+s), (rs) y (r ∗ ) son expresiones regulares que
denotan los conjuntos R ∪ S, RS y R∗ , respectivamente.
Ejemplo:
00 es una expresión regular que representa a {00}. La expresión (0 + 1)∗
denota todas las cadenas de 00 s y 10 s. Ası́ (0 + 1)∗ 00(0 + 1)∗ denota todas
las cadenas de 0’s y 1’s con al menos dos ceros consecutivos.
Feliú Sagols Troncoso
Matemáticas-Cinvestav
2
Equivalencia entre autómatas finitos y
expresiones regulares
Demostraremos que los lenguajes que aceptan los autómatas finitos son precisamente los lenguajes denotados por las expresiones regulares.
Teorema 2.3: Sea r una expresión regular. Entonces existe un AFND con
transiciones- que acepta L(r). (L(r) es el lenguaje denotado por r).
Demostración:
a) r = b) r = ∅
c) r = a
d) r = r1 + r2
e) r = r1 r2
f) r = r1∗
Start
(a) r =
q
0
Start
q
0
ε
(b) r =
φ
Start
qf
(c) r = a
M1
1
a
q
0
(b)
q
ε
Start
qf
f
ε
1
f
q
0
0
ε
ε
q
2
M2
f
2
(d)
q
Start
1
M1
ε
f1
q
2
M2
f
2
(e)
ε
q
Start
0
ε
q
M1
1
ε
f
f
0
1
ε
(f)
Ejemplo:
Construyamos un AFND para la expresión regular 01∗ +1.
La expresión 01∗ +1 es realmente (0(1∗ ))+1, asi que es de la forma r1 + r2 ,
donde r1 =01∗ y r2 =1.
El autómata para r2 es:
Inicio
q1
1
q2
Se puede expresar r1 como r3 r4 , donde r3 =0 y r4 =1∗ .
3
Curso Básico de Computación
El autómata para r3 es:
q3
Inicio
q4
0
r4 es r5∗ , donde r5 es 1, y el AFND para r5 es:
q5
Inicio
q6
1
Finalmente se tienen los siguientes AFND:
a) Para r4 =1∗
q7
Inicio
q5
1
q6
q5
1
q8
Inicio
b) Para r1 =01∗
q3
0
q4
q7
q1
Inicio
q2
q10
q3
0
q4
q7
q5
1
q8
q9
c) Para r=01∗ +1
1
q6
Teorema 2.4: Si L es aceptado por un AFD, entonces L es denotado por una
expresión regular.
Demostración: Sea L el conjunto aceptado por el AFD
M = ({q1 , · · · qn }, Σ, δ, q1 , F )
k
Sea Rij
el conjunto de todas las cadenas que toma el autómata finito para ir
del estado qi al estado qj sin pasar por algún estado numerado mayor que k.
k
Definimos a Rij
como
k
Rij
= {x ∈ Σ∗ | δ(qj , x) = qj y
∀ prefijo y de x
δ(qi , y) = ql donde l ≤ k}
k
Recursivamente Rij
se define como:
k−1
k−1 ∗ k−1
k
k−1
) Rkj ∪ Rij
(Rkk
Rij
= Rik
q6
q8
Feliú Sagols Troncoso
0
Rij
Matemáticas-Cinvestav
=
4
{a | δ(qi , a) = qj }
si i 6= j
{a | δ(qi , a) = qj } ∪ {} si i = j
k
Ahora hay que demostrar que para cada i, j, k existe una expresión regular r ij
k
que denota el lenguaje Rij
, y procedemos por inducción sobre k.
0
Base: (k = 0). Rij es un conjunto de cadenas que pueden ser o un solo
0
sı́mbolo. Ası́ rij
se puede escribir como a1 + a2 + · · ·+ ap (o a1 + a2 + · · ·+ ap + si i = j), donde {a1 , a2 , · · · , ap } es el conjunto de todos los sı́mbolos a tales
que δ(qi , a) = qj . Si no existen tales a’s, entonces ∅ (o en el caso de i = j)
0
sirven como rij
.
k
Inducción: La fórmula recursiva de Rij
involucra sólo las siguientes operaciones
de expresiones regulares: unión, concatenación y cerradura. Por la hipótesis de
k−1
k−1
inducción, para cada l y m existe una expresión regular rlm
tal que L(rlm
)=
k−1
k
Rlm . Ası́ para rij se selecciona la expresión regular
k−1 k−1 ∗ k−1
k−1
rik
(rkk ) rkj + rij
Para terminar la demostración solo hay que observar que
[
n
L(M ) =
R1j
qj ∈F
Ejemplo:
k
Sea M el AF de la figura 2.5, los valores de rij
para toda i, j y para toda
k=0, 1, 2 son:
k
r11
k
r12
k
r13
k
r21
k
r22
k
r23
k
r31
k
r32
k
r33
k=0 k=1
k=2
(00)∗
0
0
0(00)∗
1
1
0∗ 1
0
0
0(00)∗
+ 00
(00)∗
1
1 + 01
0∗ 1
∅
∅
(0 + 1)(00)∗ 0
0+1 0+1
(0 + 1)(00)∗
+ (0 + 1)0∗ 1
1
Inicio
q1
0
q2
0
1
q3
0,1
Figura 2.5
Usaremos las siguientes expresiones
5
Curso Básico de Computación
(r + s)t = rt + st
( + r)∗ = r ∗
1
La expresión r22
esta dada por
1
0
0 ∗ 0
0
r22
= (r21
)(r11
) r12 + r22
=0()∗ 0+ Similarmente
2
1
1 ∗ 1
1
r13
= r12
(r22
) r23 + r13
=
0( + 00)∗ (1 + 01) + 1
Dado que ( + 00)∗ es equivalente a (00)∗ y 1+ 01 es equivalente a (+ 0)1,
se tiene
2
r13
= 0(00)∗ ( + 0)1+1
Como (00)∗ (+ 0) es equivalente a 0∗ .
Ası́ 0(00)∗ (+0)1+1 es equivalente a 00∗ 1+1 y por lo tanto a 0∗ 1.
Para completar la construcción de la expresión regular para M , la cual es
3
3
r12
+ r13
, escribimos
3
2
2 ∗ 2
2
r12
= r13
(r33
) r32 + r12
= 0∗ 1( + (0 + 1)0∗ 1)∗ (0 + 1)(00)∗ + 0(00)∗
= 0∗ 1((0 + 1)0∗ 1)∗ (0 + 1)(00)∗ + 0(00)∗
y
3
2
2 ∗ 2
2
r13
= r13
(r33
) r33 + r13
= 0∗ 1( + (0 + 1)0∗ 1)∗ ( + (0 + 1)0∗ 1) + 0∗ 1
= 0∗ 1((0 + 1)0∗ 1)∗
Por lo tanto
3
3
r12
+ r13
=
= 0∗ 1((0 + 1)0∗ 1)∗ ( + (0 + 1)(00)∗ ) + 0(00)∗
2.6 Autómata Finito Bidireccional
Un autómata finito determinı́stico de doble vı́a (AFD2) es una 5-tupla M =
(Q, Σ, δ, q0 , F ), donde δ transforma Q × Σ a Q × {L, R}. Si δ(q, a) = (p, L),
entonces en el estado q, con entrada a, el AFD2 entra al estado p y mueve su
cabeza a la izquierda un cuadro de la cinta. Si δ(q, a) = (p, R), el AFD2 entra
al estado p y mueve su cabeza hacia la derecha un cuadro.
Introducimos el concepto de descripción instantánea (DI) para un AFD2, que
describe la cadena de entrada, el estado actual y la posición actual de la cabeza.
También introducimos la relación
en DI tal que I1
I2 si y sólo si M
puede ir de I1 a I2 en un movimiento.
M
M
Feliú Sagols Troncoso
Matemáticas-Cinvestav
6
Una DI de M es una cadena en Σ∗ QΣ∗ . Para la DI wqx, donde w, x ∈ Σ∗ y
q ∈ Q, se pretende que represente los siguientes hechos:
1) wx es una cadena de entrada,
2) q es el estado actual,
3) la cabeza de entrada esta analizando el primer sı́mbolo de x.
Si x = , entonces la cabeza de entrada se ha movido más allá del extremo
derecho de la entrada.
Definimos la relación
M
o ` por:
1)a1 a2 · · · ai−1 qai · · · an ` a1 a2 · · · ai−1 ai p
ai+1 · · · an siempre que δ(q, ai ) = (p, R),
2)a1 a2 · · · ai−2 ai−1 qai · · · an ` a1 a2 · · · ai−2 p
ai−1 ai · · · an siempre que δ(q, ai ) = (p, L) y i > 1.
*
la cerradura transitiva y reflexiva de `. Es decir, I
Sea
*
DI I, y I1
Ik siempre que I1 ` I2 ` · · · ` Ik .
Definimos:
*
L(M ) = {w | q0 w wp para algún p ∈ F }
*
I para toda
Ejemplo:
Considere el siguiente AFD2 M : comienza en el estado q0 , M repite un ciclo de
movimientos donde la cabeza se mueve hacia la derecha hasta que encuentre
dos 1’s, entonces se mueve a la izquierda hasta encontrar un 0, luego el punto
q0 es el inicio y el ciclo de repite. M tiene 3 estados, todos son estados finales
y δ esta dada por:
0
1
q0 (q0 , R) (q1 , R)
q1 (q1 , R) (q2 , L)
q2 (q0 , R) (q2 , L)
Considere la entrada 101001. Como q0 es el estado inicial, la primera DI es
q0 101001. Para obtener la seguna DI, note que el sı́mbolo que se encuentra a
la derecha de q0 en la primera DI es 1 y δ(q0 , 1) = (q1 , R). Entonces la segunda
DI es 1q1 01001. El resultado se muestra en la siguiente tabla:
q0 101001 `
`
`
`
`
`
`
`
`
`
1q1 01001
10q1 1001
1q2 01001
10q0 1001
101q1 001
1010q1 01
10100q1 1
1010q2 01
10100q0 1
101001q1
7
Curso Básico de Computación
Ası́ 101001 ∈ L(M ).
Secuencia de cruces
La lista de estados debajo de cada frontera entre cuadros se llama secuencia
de cruces. La secuencia de cruces del ejemplo anterior es:
1
q0
0
q1
1
0
0
1
q1
q
2
q0
q1
q1
q1
q2
q
0
q
1
Note que un AFD2 no pueden tener secuencia de cruces que repita estados con
la cabeza moviendose a la misma dirección, en este caso, entrarı́a en un ciclo
y nunca terminarı́a.
Otras observaciones acerca de la secuencias de cruces es si la primera frontera es
cruzada, la cabeza se debe mover a la derecha. Subsecuencias de cruces deben
alternar direcciones. Ası́ elementos impares de la secuencia de cruces representan movimientos hacia la derecha y elementos pares representan movimientos
hacia la izquierda. Si una entrada es aceptada, todas las secuencias de cruces
tienen longitud impar.
Una secuencia de cruces q1 , q2 , ..., qk es válida si su longitud es impar y no hay
dos elementos pares o dos elementos impares iguales. Un ADF2 con s estados
pueden tener secuencias válidas de longitud a lo más 2s, ası́ el número de
secuencias válidas es finito.
Definimos caza por la derecha y caza por la izquierda de las secuencias de cruces
recursivamente por i a v.
i) La secuencia nula tiene secuencia nulas que cazan por la derecha e izquierda.
ii) Si q3 , ..., qk caza por la derecha a p1 , ..., pl y δ(q1 , a) = (q2 , L), entonces
q1 , ..., qk caza por la derecha a p1 , ..., pl .
iii) Si q2 , ..., qk caza por la izquierda a p2 , ..., pl y δ(q1 , a) = (p1 , R), entonces
q1 , ..., qk caza por la derecha a p1 , ..., pl .
iv) Si q1 , ..., qk caza por la izquierda a p3 , ..., pl y δ(p1 , a) = (p2 , R), entonces
q1 , ..., qk caza por la izquierda a p1 , ..., pl .
v) Si q2 , ..., qk caza por la derecha a p2 , ..., pl y δ(p1 , a) = (q1 , L), entonces
q1 , ..., qk caza por la izquierda a p1 , ..., pl .
Feliú Sagols Troncoso
Matemáticas-Cinvestav
8
Equivalencia entre Autómatas Finitos
de Una y Doble Vı́a
Teorema 2.5: Si L es aceptado por un AFD2, entonces L es un conjunto regular.
Demostración: Sea M = (Q, Σ, δ, q0 , F ) un AFD2. La demostración consiste
en construir un AFND M 0 que acepte L(M ). Definimos M 0 = (Q0 , Σ, δ 0 , q00 , F 0 ),
donde
1. Q0 consiste de todas las secuencias válidas para M .
2. q00 es la secuencia de cruce que consiste solo de q0 .
3. F 0 es el conjunto de todas las secuencias de cruce de longitud 1 que
consiste de un estados de F .
4. δ 0 (c, a) = {d | d es una secuencia válida que es cazada por la derecha
con c y con entrada a}
Para terminar se tiene que demostrar que L(M 0 ) = L(M ).
Ejemplo:
Consideremos la construcción de un AFND M 0 equivalente a un AFD2 M
del ejemplo anterior. Como q2 entra solo cuando se mueve hacia la izquierda,
y q1 , q3 entran solo cuando se mueven a la derecha, todas los componentes pares
de las secuencias válidas deben ser q2 . Existen solo 4 secuencias de cruces de
interés:
Secuencia Caza por la Caza por la
Válida
derecha en 0 derecha en 1
[q0 ]
[q0 ]
[q1 ]
[q1 ]
[q1 ], [q1 , q2 , q0 ]
−
[q0 , q2 , q1 ]
−
−
[q1 , q2 , q0 ]
−
[q1 ]
Note que los estados [q0 , q2 , q1 ] se pueden quitar y el AFND M 0 que se obtiene
es el siguiente:
0
Start
[ q0]
0
1
[ q1]
1
0
[q , q , q ]
1 2 0
9
Curso Básico de Computación
Note que L(M ) = ( + 1)(0 + 01)∗ . Considere la entrada 1001, la cual es
aceptada por M 0 usando la secuencia de estados [q0 ], [q1 ], [q1 ], [q1 , q2 , q0 ], [q1 ]. Y
en la siguiente figura se visualiza la secuencia de cruces.
1
q
0
0
q
1
0
q
1
1
q
1
q
2
q0
q1
2.7 Autómatas Finitos con Salida
Una limitación de los autómatas finitos es su salida, ésta se limita a una señal
binaria: “aceptado/no aceptado”. Ahora consideremos modelos cuyas salidas
pertenecen a un alfabeto arbitrario. Primero consideremos autómatas donde
las salidas se asocian a los estados (Máquinas de Moore) y luego consideremos
autómatas cuyas salidas se asocian con las transiciones (Máquinas de Mealy).
Máquina de Moore
Una Máquina de Moore es una 6-tupla (Q, Σ, ∆, δ, λ, q0 ), donde Q, Σ, δ y q0 son
iguales que en un AFD. ∆ es el alfabeto salida y λ es una transformación de Q
a ∆, que da la salida asociada con cada estado. La salida de M en respuesta
a la entrada a1 a2 · · · an , n ≥ 0, es λ(q0 )λ(q1 ) · · · λ(qn ), donde q0 , q1 , · · · , qn es
la secuencia de estados tal que δ(qi−1 , ai ) = qi , para 1 ≤ i ≤ n. Note que
cualquier máquina de Moore da la salida λ(q0 ) en respuesta a la entrada . Un
AFD puede verse como un caso especial de una Máquina de Moore donde el
alfabeto salida es {0,1} y el estado q es de aceptación si y sólo si λ(q) = 1.
Ejemplo:
Suponga que deseamos determinar el residuo módulo 3 para cada cadena binaria tratada como un entero binario. Observe que si i es binario seguido por
un 0, la cadena resultante tiene valor 2i, y si i es binario seguido por un 1,
la cadena resultante tiene valor 2i + 1. Si el residuo de i/3 es p, entonces el
residuo de 2i/3 es 2p módulo 3. Si p = 0, 1 o 2, entonces 2p módulo 3 es 0,
2 o 1, respectivamente. Similarmente, el residuo de (2i + 1)/3 es 1, 0, o 2,
respectivamente.
Por lo tanto, se diseña una máquina de Moore con 3 estados q0 , q1 y q2 , donde
qj es entero si y sólo si la entrada hasta este punto tiene residuo j. Se define
λ(qj ) = j para j = 0, 1 y 2. En la figura 2.6 se muestra el diagrama de
transición.
Feliú Sagols Troncoso
0
Inicio
1
q0
0
Matemáticas-Cinvestav 10
1
0
q1
0
1
2
q2
1
Figura 2.6
Máquina de Mealy
Una Máquina de Mealy es una 6-tupla M = (Q, Σ, ∆, δ, λ, q0 ), cuyos elementos son como en la máquina de Moore, excepto que λ transforma Q × Σ
en ∆. Es decir, λ(q, a) da la salida asociada con la transición del estado
q con entrada a. La salida de M en respuesta a la entrada a1 a2 · · · an es
λ(q0 , a1 )λ(q1 , a2 ) · · · λ(qn−1 , an ) donde q0 , q1 , · · · , qn es la secuencia de estados
tales que δ(qi−1 , ai ) = qi para 1 ≤ i ≤ n. Note que la entrada en una máquina
de Mealy da la salida .
Equivalencia entre las máquinas de
Moore y de Mealy
Sea M una Máquina de Moore o de Mealy. Definimos TM (w) como la salida
producida por M con entrada w. Note que si M es una máquina de Mealy
y M 0 es una máquina de Moore entonces |TM (w)| es uno menos que |TM 0 (w)|
para cada w. Si M es una máquina de Mealy y M 0 es una máquina de Moore
se dice que son equivalentes si para toda entrada w, bTM (w) = TM 0 (w), donde
b es la salida de M 0 para su estado inicial.
Teorema 2.6 Si M1 = (Q, Σ, ∆, δ, λ, q0 ) es una máquina de Moore, entonces
existe una máquina de Mealy M2 equivalente a M1 .
Demostración: Sea M2 = (Q, Σ, ∆, δ, λ0 , q0 ) y definimos a λ0 (q, a) = λ(δ(q, a))
para todo estado q y entrada a. Entonces para M1 y M2 entra la misma secuencia de estados con la misma entrada, y con cada transición M2 emite la
salida que M1 asocia con el estado de entrada.
Teorema 2.7 Si M1 = (Q, Σ, ∆, δ, λ, q0 ) es una máquina de Mealy, entonces
existe una máquina de Moore M2 equivalente a M1 .
Demostración: Sea M2 = (Q × ∆, Σ, ∆, δ 0 , λ0 , [q0 , b0 ]), donde b0 es un miembro de ∆ seleccionado arbitrariamente. Es decir, los estados de M2 son pares
[q, b]. Definimos λ0 ([q, b], a) = [δ(q, a), λ(q, a)] y λ0 ([q, b]) = b. La segunda
componente de un estado [q, b] de M2 es la salida realizada por M1 en alguna
transición en el estado q. Solo el primer componente de los estados de M2
determinan los movimientos realizados por M2 . Es muy fácil demostrar por
inducción sobre n que si a M1 entran a los estados q0 , q1 , ..., qn las entradas
11
Curso Básico de Computación
a1 a2 · · · an y emite las salidas b1 , b2 , ..., bn , entonces para M2 entran los estados
[q0 , b0 ], [q1 , b1 ], ..., [qn , bn ] y emite las salidas b0 , b1 , ..., bn .
Ejemplo:
Sea M1 = ({q0 , p0 , p1 }, {0, 1}, {y, n}, δ, λ, q0) la máquina de Mealy de la figura
2.7. La etiqueta a/b en el arco que va del estado p al estado q indica que
δ(p, a) = q y λ(p, a) = b. Los estados de M2 son [q0 , y], [q0 , n], [p0 , y], [p0 , n], [p1 , y]
y [p1 , n]. Escoja b0 = n y [q0 , n] el estado inicial de M2 . La transición y salidas
de M2 se demuestran en la figura 2.8.
0/n
q0
Inicio
0/y
p0
1/n
0/n
1/n
p1
1/y
Figura 2.7
Inicio
1
n
n
[q 0 , n]
0
n
[p 0 , n]
[p 1 , n]
1
0
0
1
0
[q 0 , y]
y
1
0
0
[p 0 , y]
[p 1 , y]
y
y
1
Figura 2.8
1