tc-leng-reg-ho

Vista previa del material en texto

Autómatas finitos Otras definiciones Limitaciones Minimalización
TEORÍA DE LA COMPUTACIÓN
LENGUAJES REGULARES Y
AUTÓMATAS FINITOS
Francisco Hernández Quiroz
Departamento de Matemáticas
Facultad de Ciencias, UNAM
E-mail: fhq@ciencias.unam.mx
Página Web: www.matematicas.unam.mx/fhq
Facultad de Ciencias
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 1 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Autómatas finitos
Un autómata finito (DFA) está formado por
Un alfabeto de entrada Σ
Un conjunto finito de estados Q
Un estado inicial s ∈ Q y un conjunto de estados finales F ⊆ Q
Una función de transición δ : Q × Σ→ Q
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 2 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Ejemplo 1
El autómata formado por Σ = {a, b, c, d}, Q = {S, 1, 2, 3, F} y δ descrita
por la siguiente tabla:
Q a b c d
S — 1 — —
1 2 — — —
2 3 — 2 2
3 — F — —
F — — — —
Y que acepta el lenguaje formado por cadenas que empiezan con ba,
terminan con ab y enmedio tienen un número indeterminado de c y d .
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 3 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Ejemplo 2
El autómata formado por Σ = {a, b}, Q = {S, 1, 2, F} y δ descrita por la
siguiente tabla:
Q a b
S 2 1
1 2 F
2 F 1
F F F
Y que acepta un lenguaje cuya descripción es demasiado larga como para
ser comprensible.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 4 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Representación gráfica
S 1 2 3 F
b a a
c,d
b
S
1
2
F
b
a
b
a
a,bab
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 5 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Lenguajes regulares
Podemos ampliar la función δ a una función δ∗ : Q × Σ∗ → Q de la
siguiente forma. Sean q ∈ Q, a ∈ Σ y α ∈ Σ∗:
δ∗(q, �) = q
δ∗(q, aα) = δ∗(δ(q, a),α)
O alternativamente
δ∗(q, �) = q
δ∗(q,αa) = δ(δ∗(q,α), a)
Nota: el alumno puede demostrar que ambas definiciones son equivalentes.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 6 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Ahora podemos definir el lenguaje aceptado por el autómata
A = (Q, Σ, S, F , δ):
L(A) = {α | δ∗(S,α) ∈ F}.
Un lenguaje L ⊆ Σ∗ es regular sii exite un autómata finito A tal que L = L(A).
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 7 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Un ejemplo aritmético
El siguiente autómata acepta el lenguaje
{α ∈ {0, 1}∗ | α es un múltiplo de 3 en binario}
0 1 2
1
0
1
0
0
1
núm. representado por el prefijo leído estado del autómata
0 mód 3 0
1 mód 3 1
1 mód 3 2
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 8 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Sea #α el número denotado por la cadena binaria α. Entonces
δ∗(0,α) = #α mód 3
Demostración. Primero
#(αd) = 2(#α) + d d ∈ {0, 1}
δ(q, d) = (2q + d) mód 3
Ahora, por inducción en α. Caso básico
δ∗(0, �) = 0 definición de δ∗
= #� pues #� = 0
= #� mód 3
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 9 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Hipótesis inductiva: δ∗(0,α) = #α mód 3. Por demostrar
δ∗(0,αd) = δ(δ∗(0,α), d)
= δ(#α mód 3, d)
= (2(#α mód 3) + d) mód 3
= (2(#α) + d) mód 3
= #αd mód 3
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 10 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Autómatas no deterministas
Un autómata finito no determinista (NFA) puede elegir uno de varios
estados posibles cuando lee un carácter.
Además, tiene un conjunto de estados iniciales S.
La función de transición de un NFA es ∆ : Q × Σ→ P(Q).
La función anterior se extiende a una función
∆∗ : P(Q)× Σ∗ → P(Q) de esta forma:
∆∗(A, �) = A
∆∗(A,αa) =
⋃
q∈∆∗(A,α)
∆(q, a)
El lenguaje aceptado es {α | ∆∗(S,α) ∩ F 6= ∅}
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 11 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Ejemplo
S
1
2
a,b
a
ba,b
a,b
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 12 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Equivalencia con los DFA
Sea N = (Q, Σ, ∆, S, F) un NFA y sea D = (QD , Σ, δD , sD , FD) el siguiente
autómata DFA
QD = P(Q)
δD(A, a) = ∆∗(A, a)
sD = S
FD = {A ⊆ Q | A ∩ F 6= ∅}
Ambos autómatas aceptan el mismo lenguaje.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 13 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Demostración. Los tres lemas siguientes
∆∗(A,αβ) = ∆∗(∆∗(A,α),β)
∆∗(
⋃
i
Ai ,α) =
⋃
i
∆∗(Ai ,α)
δ∗D(A,α) = ∆
∗(A,α)
se demuestran por inducción sobre β, α y α, en ese orden. Entonces,
L(N) = L(D):
α ∈ L(D) sii δ∗(sD ,α) ∈ FD
sii ∆∗(SN ,α) ∩ FN 6= ∅
sii α ∈ L(N)
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 14 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Transiciones �
Un autómata finito no determinista con transiciones-� es una quinteta
N = (Q, Σ, ∆, S, F), igual a un NFA salvo que
∆ : Q × (Σ ∪ {�})→ P(Q).
Ahora es posible transitar de un estado a otro sin consumir símbolos. ∆∗ se
define así
∆∗(A, �) = A ∪
⋃
q∈A
∆(q, �)
∆∗(A,αa) =
⋃
q∈∆∗(A,α)
∆(q, a) ∪
⋃
r∈∆(q,�)
q∈∆∗(A,α)
∆(r , a)
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 15 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Ejemplo
S1
S2
1
2
3
�
a,b
ba,b
�
a
a,b
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 16 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
NFA-� es equivalente a NFA
Sea N = (Q, Σ, ∆, S, F) un NFA-�, y sea q ∈ Q. Definimos la cerradura-� de
q
∆0�(q) = {q}
∆n+1� (q) =
⋃
r∈∆n�(q)
∆(r , �)
∆∗� (q) =
⋃
n∈N
∆n�(q)
Sea N′ = (Q, Σ, ∆′, S, F ′), con
∆′(q, a) = ∆(q, a) ∪
⋃
r∈∆∗� (q)
∆(r , a)
F ′ = {q | ∆∗� (q) ∩ F 6= ∅}
Claramente, L(N) = L(N′)
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 17 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Varios estados finales e iniciales
La introducción de transiciones-� permite transformar autómatas con varios
estados iniciales o finales en autómatas con un soloestado inicial o final.
Esta técnica será útil más adelante.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 18 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Propiedades de cerradura
Los conjuntos regulares son cerrados bajo las operaciones de:
Unión
Intersección
Complemento
Concatenación
Estrella de Kleene
Nota: en las demostraciones siguientes se supondrá que los autómatas son
completos, i.e., que la función δ no es parcial.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 19 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Demostración de cerradura bajo ∪
Sean D1 = (Q1, Σ, δ1, s1, F1) y D2 = (Q2, Σ, δ2, s2, F2) dos DFA.
Construiremos un D ∈ DFA tal que
L(D) = L(D1) ∪ L(D2).
Definimos D = (Q, Σ, δ, s, F) donde
Q = Q1 × Q2
s = (s1, s2)
F = (Q1 × F2) ∪ (F1 × Q2)
δ((q1, q2), a) = (δ1(q1, a), δ(q2, a))
Se puede demostrar por inducción en α que
α ∈ L(D) sii α ∈ L(D1) o bien α ∈ L(D2).
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 20 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Cerradura bajo ∩ y complemento
Intersección
Se construye un autómata como en el caso de ∪, salvo que
F = F1 × F2.
Complemento
Sea A = (Q, Σ, δ, s, F) un DFA. Sea Ā = (Q, Σ, δ, s, Q − F). Claramente
L(Ā) = Σ∗ − L(A).
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 21 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Autómatas Lenguajes regulares Autómatas no deterministas Cerradura
Cerradura bajo concatenación y estrella de Kleene
Sean A = (QA, Σ, δA, sA, FA) y B = (QB , Σ, δB , sB , FB) dos DFA. El autómata
C = (QC , Σ, ∆C , SC , FC) se construye de la siguiente forma:
QC = QA ∪ QB
SC = {sA}
FC = FB
∆(q, a) = {δA(q, a)} si q ∈ QA
∆(q, a) = {δB(q, a)} si q ∈ QB
∆(q, �) = {sB} si q ∈ FA
C es un NFA-� tal que L(C) = L(A)L(B). Para construir A′ tal que
L(A′) = L(A)∗, se añaden transiciones-� de los estados en FA a sA.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 22 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Definiciones alternativas de lenguajes regulares
Existen otras formas de definir los lenguajes regulares:
Expresiones regulares
Patrones
Gramáticas lineales
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 23 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Expresiones regulares
Las expresiones regulares son una forma muy compacta de definir
lenguajes. El lenguaje generado por la expresión α es L(α). He aquí una
definición inductiva:
Si a ∈ Σ entonces a es una expresión regular y L(a) = {a}.
∅ y � son expresiones regulares con L(∅) = ∅ y L(�) = {�}
Las expresiones regulares α y β generan las expresiones y lenguajes:
α + β L(α + β) = L(α) ∪ L(β)
α · β L(α · β) = L(α)L(β)
α∗ L(α∗) = L(α)∗
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 24 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Ejemplos
Los números naturales en notación decimal:
0 + ((1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9) · (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)∗)
Las fórmulas atómicas del cálculo proposicional:
(p + q + r) + ((p + q + r) · N)
donde N se refiere a la expresión del ejemplo anterior.
Las cadenas del alfabeto {a, b, c} con al menos una aparición de cada una
de las tres letras:
(AaAbAcA)+(AaAcAbA)+(AbAaAcA)+(AcAaAbA)+(AcAbAaA)+(AbAcAaA)
donde A es la expresión (a + b + c)∗.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 25 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Patrones
Los patrones son otra forma muy común. También se definen
inductivamente:
a, ∅ y � son iguales que en las expresiones regulares
#, con L(#) = Σ
@, con L(@) = Σ∗
Los patrones α y β generan los patrones y lenguajes:
α + β L(α + β) = L(α) ∪ L(β)
α ∩ β L(α ∩ β) = L(α) ∩ L(β)
αβ L(αβ) = L(α)L(β)
∼α L(∼α) = Σ∗ − L(α)
α∗ L(α∗) = L(α)∗
α+ L(α+) = L(α)+
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 26 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Ejemplos
Las cadenas que contienen apariciones de a, b y c, en ese orden, pero no
necesariamente consecutivas:
@a@b@c@
Las cadenas del alfabeto {a, b, c} salvo las que son repeticiones
consecutivas de la cadena abc:
∼((abc)+).
Cualquier símbolo del alfabeto seguido de cualquier cadena menos las
repeticiones consecutivas de ab o cd :
# ∼((ab)+ + (cd)+).
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 27 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Gramáticas lineales
Recordatorio. Una gramática es G = 〈Σ, Γ, S,→〉.
Sean A, B ∈ Γ y α ∈ Σ∗. Si todas las reglas de G tienen una de las
siguientes dos formas
A→ αB o bien A→ α
se trata de una gramática lineal por la derecha.
Si todas las reglas de G son de alguna de las dos formas
A→ Bα o bien A→ α
es una gramática lineal por la izquierda.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 28 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Ejemplos
La gramática GN = 〈{0, . . . 9}, {S, N}, S,→〉 con reglas de
producción
S → 0 | 1N | 2N | · · · | 9N
N → 0N | 1N | . . . 9N | �,
genera los números naturales en notación decimal.
La gramática GP = 〈{p, q, r , 0, . . . 9}, {S′, S, N}, S′,→〉 con las
siguientes reglas adicionales a las del ejemplo anterior:
S′ → p | q | r | pS | qS | rS
genera las fórmulas atómicas del cálculo de proposiciones.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 29 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Equivalencia entre patrones y expresiones regulares I
Para todo patrón α, existe una expresión regular β tal que L(α) = L(β).
Demostración. Por inducción en α.
Primero los casos básicos: a, �, ∅, # y @. Los tres primeros tienen
expresiones regulares equivalentes obvias.
En cuanto # y @, si Σ = {c1, . . . , cm}, entonces
L(#) = L(c1 + · · · + cm) y L(@) = L((c1 + · · · + cm)∗)
Hipótesis inductiva. Supongamos que dados los patrones α y β, existen
expresiones regulares γ y η tales que
L(α) = L(γ) L(β) = L(η)
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 30 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Equivalencia entre patrones y expresiones regulares II
Procedemos a probar los casos inductivos con los operadores +,
concatenación, ∗, + ∩ y∼.
Los tres primeros son obvios, pues también se encuentran presentes en las
expresiones regulares.
En cuanto a +, basta observar que α+ es equivalente a αα∗.
La prueba del patrón∼α se deja pendiente.
Finalmente, el patrón α ∩ β es equivalente al patrón∼(∼α+ ∼β), el cual
queda cubierto por los casos anteriores.
Nota. La afirmación inversa es trivialmente cierta.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 31 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regularesPatrones Gramáticas Equivalencias
Equivalencia entre expresiones regulares y autómatas
Para toda expresión regular α, existe un autómata finito A tal que
L(α) = L(A).
La demostración se hará por inducción en α.
Casos básicos. Para las expresiones a, � y ∅, se tienen los siguientes
autómatas:
S F S S
a
Casos inductivos. Ya se estudió cómo construir autómatas que acepten la
unión, la concatenación y la estrella de Kleene de lenguajes regulares.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 32 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Equivalencia entre autómatas y expresiones regulares I
Sea N = (Q, Σ, ∆, S, F) ∈ NFA y sean X ⊆ Q y p, q ∈ Q. Definiremos una
expresión regular αXpq tal que
L(αXpq) = {β | q ∈ ∆∗({p},β) y el camino pasa sólo por estados en X}.
Por inducción en X . Sean a1, . . . ak todos los símbolos de Σ tales que
q ∈ ∆(p, ai).
Si p 6= q
α∅pq =
{
a1 + · · · + ak 1 ≤ k
∅ k = 0
Si p = q
α∅pq =
{
a1 + · · · + ak + � 1 ≤ k
� k = 0
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 33 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Equivalencia entre autómatas y expresiones regulares II
Si X 6= ∅, sea r ∈ X
αXpq = α
X−{r}
pq + α
X−{r}
pr (α
X−{r}
rr )
∗α
X−{r}
rq .
Finalmente, si s1, . . . , sn ∈ S y f1, . . . , fm ∈ F , entonces
L(N) = L(
n∑
i=1
m∑
j=1
αQsi fj )
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 34 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Equivalencia entre gramáticas lineales y autómatas I
Sea G = 〈Σ, Γ, S,→〉 una gramática lineal por la derecha. Sea N ∈ NFA-�
el siguiente autómata:
Q = {α | V ∈ Γ,β ∈ Σ∗Γ ∧ V → βα}
∪ {[S]}
∆([V ], �) = {[α] | V → α} si V ∈ Γ
∆([aα], a) = {α} si a ∈ Σ ∧ α ∈ Σ∗ ∪ Σ∗Γ
{[S]} = estados iniciales
{[�]} = estados finales.
Entonces
[α] ∈ ∆∗([S], γ) sii S ⇒∗ ηV ⇒ ηθα.
Demostración. Inducción en⇒∗. A partir de este resultado, es claro que
L(N) = L(G).
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 35 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Expresiones regulares Patrones Gramáticas Equivalencias
Equivalencia entre gramáticas lineales y autómatas II
A la inversa, sea A = (Q, Σ, δ, s, F) ∈ DFA. Sea G = 〈Σ, Q, s,→〉 una
gramática con producciones de la forma
q → ar sii δ(q, a) = r
q → a sii δ(q, a) ∈ F
Entonces
δ∗(q,α) = r sii q ⇒∗G αr
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 36 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Teorema del bombeo Aplicaciones
Un lenguaje no regular I
El lenguaje {anbn} no es regular. Supongamos que lo es y que A es un
autómata determinista con k estados y L(A) = {anbn}.
Sea la cadena ambm, con m > k . Durante su lectura, el autómata debe
haber pasado al menos dos veces por un mismo estado (hay menos estados
que copias de a).
Sea q este estado repetido. Entonces:
δ∗(s, ai) = q i < m
δ∗(q, aj) = q j 6= 0
δ∗(q, ar bm) = f ∈ F i + j + r = m.
Como A es determinista, tenemos que para toda p ∈ N
δ∗(q, ajp) = q
y en consecuencia
δ∗(s, aiajpar bm) = f ∈ F
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 37 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Teorema del bombeo Aplicaciones
Un lenguaje no regular II
Pero
i + jp + r 6= m,
salvo en el caso en que p = 1. Por tanto, aunque aiajpar bm ∈ L(A),
aiajpar bm 6∈ {anbn},
lo cual es una contradicción. En conclusión, este lenguaje no es regular.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 38 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Teorema del bombeo Aplicaciones
Teorema del bombeo
El resultado anterior se puede generalizar con el siguiente
Teorema. Sea L un lenguaje regular. Entonces, ∃k ∈ N tal que
∀α,β, γ ∈ Σ∗, si
αβγ ∈ L y k ≤ |β|,
entonces ∃η, θ,φ ∈ Σ∗ tales que
β = ηθφ y θ 6= � y αηθiφγ ∈ L ∀i ∈ N.
La demostración generaliza el argumento del ejemplo anterior, en el que
α = �, β = am, η = ai , θ = aj , φ = ar y γ = bm.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 39 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Teorema del bombeo Aplicaciones
Aplicaciones del lema del bombeo I
Ejemplo 1. El lenguaje {a2n} no es regular. Supongamos que lo es y
A ∈ DFA reconoce este lenguaje. Sea k el número de estados de A y sea m
tal que 2m > k . El teorema del bombeo nos dice que ∃η, θ,φ tales que
a2
m
= αηθiφγ ∈ L(A) ∀i ∈ N.
Como θ 6= �, la afirmación anterior quiere decir que
|α| + |η| + i|θ| + |φ| + |γ|
siempre es una potencia de 2, lo cual es obviamente falso. Por tanto, A no
puede existir y {a2n} no es regular.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 40 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Teorema del bombeo Aplicaciones
Aplicaciones del lema del bombeo II
Ejemplo 2. Sean α ∈ Σ∗ y a ∈ Σ. Definimos
#a(α) = el número de apariciones de a en α.
Entonces
{α ∈ {a, b}∗ | #a(α) = #b(α)}
no es regular. La demostración en este caso es indirecta:
1 El lenguaje {a∗b∗} es regular.
2 {a∗b∗} ∩ {α ∈ {a, b}∗ | #a(α) = #b(α)} = {anbn}.
3 Los lenguajes regulares son cerrados bajo ∩.
4 Por tanto, {α ∈ {a, b}∗ | #a(α) = #b(α)} no puede ser regular.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 41 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Minimalización de estados Teorema de Myhill-Nerode
Minimalización de estados
En ocasiones, un autómata A puede reemplazarse con un autómata A′ que
reconoce el mismo lenguaje pero que tiene un conjunto de estados menor:
S
1
2
F
a
b
a, b
a, b
a,b S′ 1′ F ′
a, b a, b
a, b
De hecho, para cada lenguaje regular existe un único DFA (salvo
isomorfismo) con un número mínimo de estados que lo reconoce.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 42 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Minimalización de estados Teorema de Myhill-Nerode
Autómata cociente
Sea A ∈ DFA, A = (Q, Σ, δ, s, F). Definimos una relación de equivalencia
entre estados de Q. Sean q, r ∈ Q. Entonces:
q ≈ r sii ∀α . δ∗(q,α) ∈ F sii δ∗(r ,α) ∈ F .
Dado que≈ es una relación de equivalencia, designaremos con [q] la clase
de equivalencia a la que pertenece el estado q. El autómata cociente de A,
que denotaremos con A/ ≈= (Q≈, Σ, δ≈, s≈, F≈), se define así:
Q≈ = {[q] | q ∈ Q}
δ≈([q], a) = [δ(q, a)]
s≈ = [s]
F≈ = {[f ] | f ∈ F}.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 43 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Minimalización de estados Teorema de Myhill-Nerode
Algoritmo de minimalización I
El siguiente algoritmo permite construir el autómata cociente a partir del
autómata A = (Q, Σ, δ, s, F), con Q = {q1, . . . , qk}:
1 Se construye una tabla
Estado q1 . . . qk
q1 m . . .
...
qk
Donde m = s si el estado en el i-ésimo renglón es final y el estado en la
j-ésima columna no es final o viceversa. En caso contrario, m = n.
2 Se repite el siguiente procedimiento hasta que ya no haya cambios:
Si (qi , qj) = n y (δ(qi , a), δ(qj , a)) = s, para algún a ∈ Σ, entonces
(qi , qj) := s.
3 Al terminar el paso anterior, qi ≈ qj sii (qi , qj) = n.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 44 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Minimalización de estados Teorema de Myhill-Nerode
Algoritmo de minimalización II
El algoritmo toma cuandomucho(
n
2
)
=
n!
2!(n − 2)!
pasos, donde n es el número de estados.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 45 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Minimalización de estados Teorema de Myhill-Nerode
Relaciones de Myhill-Nerode I
Sea L un lenguaje regular y sea A ∈ DFA tal que L(A) = L, con
A = (Q, Σ, δ, s, F) y sin estados inaccesibles. Definiremos una relación de
equivalencia en Σ∗:
α ≡A β sii δ∗(s,α) = δ∗(s,β).
La relación≡A tiene las siguientes propiedades:
1 Es una congruencia por la derecha:
α ≡A β implica que αa ≡A βa.
2 Es una afinación de L:
α ≡A β implica que α ∈ L sii β ∈ L.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 46 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Minimalización de estados Teorema de Myhill-Nerode
Relaciones de Myhill-Nerode II
3 Tiene índice finito, es decir, induce un número finito de clases de
equivalencia.
Una relación que cumple con 1–3 es una relación de Myhill-Nerode.
Sea ahora R ⊆ Σ∗ un lenguaje arbitrario. La relación de equivalencia
≡R⊆ Σ∗ × Σ∗ se define de esta forma:
α ≡R β sii ∀γ ∈ Σ∗ . αγ ∈ R sii βγ ∈ R.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 47 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Minimalización de estados Teorema de Myhill-Nerode
Teorema de Myhill-Nerode
Sea L ⊆ Σ∗. Entonces, las siguientes afirmaciones son equivalentes:
L es regular.
Existe una relación de Myhill-Nerode en L.
La relación≡L tiene índice finito.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 48 / 49
Autómatas finitos Otras definiciones Limitaciones Minimalización
Minimalización de estados Teorema de Myhill-Nerode
Ejemplo
El conjunto L = {a2n} no es regular. Se demostrará utilizando el teorema
anterior. Considérense las clases de equivalencia:
α ≡L β sii ∀k . αak ∈ L sii βak ∈ L.
Pero αak ,βak ∈ L sii |α| + k = |β| + k = 2n, para alguna n ∈ N. En pocas
palabras, por cada valor de k hay una clase de equivalencia distinta, i.e.,≡L
no tiene índice finito.
Francisco Hernández Quiroz Teoría de la Computación Leng. regulares y autómatas finitos 49 / 49
	Autómatas finitos
	Autómatas
	Lenguajes regulares
	Autómatas no deterministas
	Propiedades de cerradura
	Otras definiciones de lenguajes regulares
	Expresiones regulares
	Patrones
	Gramáticas lineales
	Equivalencias
	Limitaciones
	Teorema del bombeo
	Aplicaciones del lema del bombeo
	Minimalización y el teorema de Myhill-Nerode
	Minimalización de estados
	Teorema de Myhill-Nerode