Upload
milagros-vega
View
8
Download
3
Embed Size (px)
DESCRIPTION
matematica discreta
Citation preview
1
Estructuras Discretas II
Lenguajes y
Autómatas
Dra. Norka Bedregal Alpaca
1
Dra. Norka Bedregal Alpaca
2
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
LENGUAJES
2
Dra. Norka Bedregal Alpaca
� Lenguaje Natural:
oAquel que ha evolucionado con el tiempo para fines de lacomunicación humana
o Continúan su evolución sin tomar en cuenta reglasgramaticales formales
o Cualquier regla es posterior y trata de explicar laestructura del lenguaje
� Lenguaje Formal:
o Está definido por reglas preestablecidas y se ajustarigurosamente a ellas
o Por ejemplo: lenguajes de programación decomputadoras, lenguajes matemáticos (álgebra, lógicaproposicional..)
3
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
Introducción
Dra. Norka Bedregal Alpaca
�Se sabe que una cadena de un conjunto X es una secuencia finita de elementos de X.
� Las cadenas son objetos fundamentales usados en la definición de lenguajes.
� El conjunto de elementos de donde las cadenas son producidas se llama alfabeto del lenguaje.
� Un alfabeto consiste de un conjunto finito de objetos no divisibles.
Ejemplo:
Sea ={a,b,c}, las siguientes son cadenas de ese alfabeto:
abc cb cab aaaabbbccc
4
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
Cadenas
3
Definiciones.
Alfabeto
Palabra, cadena o frase
Palabra vacía
Longitud de una palabra
0 si x = λλλλ| x | =
| y | + 1 si x = ya (con a ∈∈∈∈ ΣΣΣΣ, y palabra sobre ∑ )
Ej. ∑ = {a, b}
λλλλ
Ej. x = abbab
∑ n : conjunto de todas las palabras de longitud n sobre ∑
U0
*
≥Σ=Σ
i
i
5
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
Cadenas o Palabras
Dra. Norka Bedregal Alpaca
Concatenación de cadenas: Sean x = a1a2...am e y = b1b2...bn se define
xy = a1a2...amb1b2...bnEjemplo: Sean u=ab v=ca w=bbEntonces
uv=abcavw=cabb(uv)w=abcabbu(vw)=abcabb
Propiedades. 1. Asociativa2. Elemento neutro (λλλλ)
Lenguaje: cualquier subconjunto de ∑* .
6
Concatenación de Cadenas
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
4
Dra. Norka Bedregal Alpaca
Longitud de una cadenaTambién llamada tamaño de una cadena w es el número de elementos que contiene la cadena.
Ejemplo: La cadena abcdef tiene una longitud de 6.
SubcadenaDada la cadena v, si existen las cadenas x y y de tal forma que
v = xuy. entonces se dice que u es una subcadena de vEsto quiere decir Que u “ocurre dentro de” v.
Un prefijo de v es una subcadenau en donde x es la cadena vacía en la descomposición de v. Eso quiere decir que v=uy. Similarmente, u es un sufijo de v si v=xu.
7
Cadenas o PalabrasLE
NG
UA
JES
Y A
UT
ÓM
ATA
S
Dra. Norka Bedregal Alpaca
Ejemplo:ab es un prefijo de la cadena abcdef y ef es un sufijo de la misma cadena.
Representación finita del lenguaje
Un lenguaje consiste de un grupo de cadenas de un alfabeto.Usualmente ciertas restricciones se aplican a las cadenas del lenguaje.
Ejemplo:El lenguaje Español consiste de todas las cadenas de palabras con sentido, también llamadas oraciones.No todas las combinaciones de palabras forman oraciones.
De allí que un lenguaje consiste de un subconjunto de el conjunto de todas las posibles cadenas que se pueden formar de el alfabeto.
8
Lenguajes
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
5
Dra. Norka Bedregal Alpaca
Ejemplo:Sea A = {Juan, Luis, come, fruta, camina, y, queso, rápidamente}Luego A* contiene
� Oraciones o cadenas con sentidoo Juan Luis come fruta y quesoo Luis camina y comeo Juan come rápidamente
� Oraciones o cadenas sin sentidoo fruta camina y quesoo y come caminao Juan queso
Ejemplo: Sea el lenguaje L de cadenas de el alfabeto {a,b} en donde cada cadena comienza con una a y tiene longitud par.Las cadenas aa, ab, aaaa, abbb, abab, abbbaaba forman partede ese lenguaje. 9
LenguajesLE
NG
UA
JES
Y A
UT
ÓM
ATA
S
Dra. Norka Bedregal Alpaca
El lenguaje anterior se puede definir recursivamente como:
i) Base: aa, ab son miembros de L.
ii) Paso recursivo: Si u es miembro de L, entoncesuaa, uab, uba, ubb
son miembros de L.
iii) Cierre (Closure): Una cadena u es miembro de L solo si puede obtenerse de los elementos base por un número finito de aplicaciones del paso recursivo.
10
Lenguajes
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
6
Dra. Norka Bedregal Alpaca
MA
QU
INA
S D
E E
STA
DO
FIN
ITO
Ejemplo: El lenguaje L consiste de cadenas del alfabeto {a,b} en donde cada ocurrencia de b es inmediatamente precedida por una a.
Por ejemplo, λ, λ, λ, λ, a, abaab están en L y bb, bab, abb no están en L.
i) Base: λλλλ es miembro de L.
ii) Paso recursivo: Si u es miembro de L, Entoncesua, uabson miembros de L.
iii) Cierre (Closure): Una cadena u es miembro de L solo si puede obtenerse de los elementos base por un número finito de aplicaciones del paso recursivo.
Definiciones recursivas como la anterior son una herramienta para definir las cadenas de un lenguaje.
Lenguajes
11
Dra. Norka Bedregal Alpaca
MA
QU
INA
S D
E E
STA
DO
FIN
ITO
Otra técnica para construir lenguajes es usar operaciones de conjuntos (sets) para construir, desde conjuntos mas simples hasta conjuntos complejos de cadenas.
Por ejemplo, la concatenación de los lenguajes X y Y, denotadaXY, es el lenguaje
XY = { uv | u es miembro de X y v es miembro de Y}
La concatenación de X consigo mismo n veces se denota como Xn.
X0 se define como {λλλλ}.
Lenguajes
12
7
Dra. Norka Bedregal Alpaca
MA
QU
INA
S D
E E
STA
DO
FIN
ITO
Ejemplo: Sea X = {a,b,c} y Y = {abb, ba}. Entonces
XY = {aabb,babb,cabb,aba,bba,cba}X0 = {λλλλ}X1 = X = {a,b,c}X2 = XX = {aa,ab,ac,ba,bb,bc,ca,cb,cc}X3 = X2X = {aaa,aab,aac,aba,abb,abc,aca,acb,acc,
baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc,caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc}
Lenguajes
13
Dra. Norka Bedregal Alpaca
MA
QU
INA
S D
E E
STA
DO
FIN
ITO
Ejemplo: El lenguaje L = {a,b}*{bb}{a,b}* consiste de las cadenas del alfabeto {a,b} que contiene la subcadena bb.
La concatenación de el conjunto {bb} asegura la presencia debb en cualquier cadena en L.
Los conjuntos {a,b}* permiten cualquier número de a’s y b’s, en cualquier orden, y que preceden y siguen la ocurrencia de bb.
Las cadenas bb, abba, ababbbabab, bbaaaa, aaaabbson ejemplos de cadenas de el lenguaje L.
Lenguajes
14
8
Operaciones con lenguajes
Dra. Norka Bedregal Alpaca
MA
QU
INA
S D
E E
STA
DO
FIN
ITO
-Booleanas.
UniónL1∪L2 ={x ∈ ∑ * : x ∈ L1 ∨ x ∈ L2}
IntersecciónL1∩L2 ={x ∈ ∑ * : x ∈ L1 ∧ x ∈ L2}
Complementación
Lc = {x ∈ ∑ * : x ∉ L}
DiferenciaL1 - L2 = L1 ∩ Lc
2
Diferencia simétricaL1 ∆ L2 = (L1 - L2 ) ∪ (L1 - L2 ) 15
Dra. Norka Bedregal Alpaca
MA
QU
INA
S D
E E
STA
DO
FIN
ITO
Concatenación de lenguajes. L1⋅L2 = {x ⋅ y ∈ ∑ * : x ∈ L1 ∧ y ∈ L2}
-No conmutativa L1⋅L2 ≠ L2⋅L1
-Asociativa L1⋅(L2 ⋅ L3) = (L1 ⋅ L2) ⋅L3
-Anulador L1⋅∅ = ∅
-Distributiva respecto de la unión L1⋅(L2 ∪ L3) = L1⋅L2 ∪ L1⋅L3
-No distributiva respecto de la intersección L1⋅(L2 ∩ L3) ⊆ L1⋅L2 ∩ L1⋅L3
Ej: L1= {a, ab}, L2= {a}, L3= {ba}
Propiedades.
Operaciones con lenguajes
16
9
Dra. Norka Bedregal Alpaca
17
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
AUTOMATAS
Dra. Norka Bedregal Alpaca
� Los autómatas de estado finito son un tipo especial deMáquinas de Estados Finitos.
� Los Autómatas se caracterizan por:
o tener un estado inicial
o recibir una cadena de símbolos
o cambiar de estado por cada elemento leído o poderpermanecer en el mismo estado
o tener un conjunto de Estados Finales o Aceptables queindican si una cadena o palabra pertenece al lenguaje alfinal de una lectura.
18
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
Introducción
10
Dra. Norka Bedregal Alpaca
Definición:
Un autómata de estado finito,
A = (I, O, S, f, g, σ)
es una máquina de estado finito en la que el conjunto de símbolos de salida es
O = {0, 1}
y donde el estado actual determina la última salida.
Aquellos estados para los cuales la última salida es 1, reciben el nombre de estados de aceptación.
Los Autómatas se clasifican en 2 tipos:
�Autómata Finito Determinista.
�Autómata Finito no Determinista. 19
DefiniciónLE
NG
UA
JES
Y A
UT
ÓM
ATA
S
Dra. Norka Bedregal Alpaca
Ejemplo:Dibuje el diagrama de transición de la máquina de estado finitodefinida por la tabla
Sf g
a b a b
σ0 σ1 σ0 1 0
σ1 σ2 σ0 1 0
σ2 σ2 σ0 1 0
σ0 σ1σ2
b/0
b/0
b/0
a/1a/1
a/1
20
AU
TO
MA
TAS
Ejemplo
11
Dra. Norka Bedregal Alpaca
Determine si la máquina graficada es o no un autómata de estadofinito
σ0 σ1σ2
b/0
b/0
b/0
a/1a/1
a/1
Se debe cumplir:
� el conjunto de símbolos de salida debe ser {0, 1}
� para cada estadoσ todos los arcos que llegan aσ tienen la mismaetiqueta de salida
� los estadosσ que tienen como única etiqueta de salida el 1, son losestados de aceptación
Luego, la máquina propuesta es un autómata de estado finito.21
EjemploLE
NG
UA
JES
Y A
UT
ÓM
ATA
S
Dra. Norka Bedregal Alpaca
Diagrama de Transición de un Autómata
• En un diagrama de transición existe un vértice por cada estadode S.• Los estados finales están encerrados en un círculo doble.• El estado inicial es apuntado por una flecha que no proviene deningún otro estado.• Para cada estadoσi y un símbolo de entrada ak , hay exactamenteuna y solo una flecha que inicia enσi y termina en σv, la flecha seetiqueta como ak.
En el ejemplo anterior:
σ0 σ1σ2
b
b
b
aa
a
22
Autómatas de Estado Finito
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
12
Dra. Norka Bedregal Alpaca
Existe una definición alternativa para un autómata de estadofinito
Definición:
Una autómata de estado es una estructura descrita por la quíntupla
A = (I, S, f, A, σ)
donde:� I, alfabeto de entrada, es un conjunto finito de símbolos.
� S, conjunto de estados, es un conjunto finito
� f: S x I ���� S Función de estado siguiente
�A: subconjunto de S, integrado por los estados de aceptación
� σ: estado inicial, pertenece a S 23
Otra DefiniciónLE
NG
UA
JES
Y A
UT
ÓM
ATA
S
Dra. Norka Bedregal Alpaca
Para describir por completo una función de transición o funciónde estado siguiente, se utiliza una Tabla de Transición.
Las columnas se etiquetan con los símbolos de entrada, la filas sonetiquetadas con los estados y en las intersecciones se colocan losnuevos estados.
Ejemplo:Dibujar el diagrama de transición del autómata definido por
A = (I, S, f, A, σ)Donde: I = {a,b} S = {σ0,σ1, σ2} A ={ σ2} σ = {σ0} y f está definidapor
Sf
a b
σ0 σ0 σ1
σ1 σ0 σ2
σ2 σ0 σ224
Tabla de Transición
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
13
Dra. Norka Bedregal Alpaca
El diagrama pedido es:
σ0 σ1σ2
a
a
a
bb
b
25
Tabla de TransiciónLE
NG
UA
JES
Y A
UT
ÓM
ATA
S
Dra. Norka Bedregal Alpaca
Sea A = (I, S, f, A,σ) un autómata de estado finitoDada una cadena de entrada sobre I
kk Ixxxxx ∈= ,..,,, 321
r
Si existe una secuencia de estados:
nσσσσσ ,..,,, 321=r
tales que: � σ0 = σ � f(σi-1, xi) = σi� el estado final σn es un estado de aceptación
Entonces, se dice que la cadena es aceptada por Axr
26
Cadenas Aceptadas por un Autómata
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
14
Dra. Norka Bedregal Alpaca
Se denota por Ac(A) al conjunto de cadenas aceptadas por elautómata A y se dice que A acepta Ac(A)
Ejemplo:Diseñar un autómata que acepte exactamente aquellas cadenassobre {a, b} que no tengan letras “a”
σ0 σ1
ba
ba
donde :σ0: no se encontró “a”σ1 : se encontró “a”
27
Cadenas Aceptadas por un AutómataLE
NG
UA
JES
Y A
UT
ÓM
ATA
S
Dra. Norka Bedregal Alpaca
donde :P: se encontró un número par de letras “a”I : se encontró un número impar de letras “a”
Ejemplo:Diseñar un autómata que acepte exactamente aquellas cadenas sobre{a, b} que contengan un número impar de letras “a”
P I
b
a
ab
Observación:Un autómata de estado finito es la representación de un algoritmoque sirve para decidir si una cadena es aceptada o no
28
Cadenas Aceptadas por un Autómata
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
15
Dra. Norka Bedregal Alpaca
Ejemplo: Construir un autómata de estado finito que no acepte cadenas que contengan la subcadena “aa” y donde I={a,b}.
q0 q1 q2
a,b
a
b
a
b
29
Cadenas Aceptadas por un AutómataLE
NG
UA
JES
Y A
UT
ÓM
ATA
S
Dra. Norka Bedregal Alpaca
Ejemplo:
Diseñar un AFD que reconozca cadenas que contienen la subcadena001
Por ejemplo debe reconocer cadenas como 0010, 1001, 11111110011111, pero no como 11, 0000, 1100, 10101.
q q0 q00 q001
1
1
0 0
0 0
1
1
30
Cadenas Aceptadas por un Autómata
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
16
Autómatas y Lenguajes
Dra. Norka Bedregal Alpaca
Lenguaje aceptado por autómata
Se define el lenguaje aceptado por un Autómata finito determinista como:
L(M) = {w ∈ Σ∗ | w es aceptada por M}
Por tanto,L(M) es el conjunto de las cadenas que hacen queM pase delestado inicial a un estado de aceptación.
31
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
Dra. Norka Bedregal Alpaca
Ejemplo:
Sea el AFD, A = (I, S, f, A,σ) donde
S= {q0, q1, q2, q3}
I = { a, b}
σ = q0
A = {q0, q1, q2}
f definida por la tabla
a b
q0 q0 q1
q1 q0 q2
q2 q0 q3
q3 q3 q3
Dibuje su diagrama de transición y determine que lenguaje acepta
32
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
Autómatas y Lenguajes
17
Dra. Norka Bedregal Alpaca
acepta el lenguaje
L(M) = {w ∈ { a, b} * | w no contiene tres b consecutivas}
σ0 σ1 σ2 σ3
a
a
b b
a
b
ba
33
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
Autómatas y Lenguajes
Dra. Norka Bedregal Alpaca
Se puede aplicar recursivamente una serie de caracteres de unacadena dada al AFD.
Por ejemplo, la aplicación de la cadenabbaben el caso anterior daráf( f( f( f( σ 0,b),b),a),b) = σ1.
Esto puede abreviarse como f(q0,bbab).
Se dice que dos AFDM1 y M2 son equivalentes siL(M1) = L(M2).
σ0 σ1 σ2 σ3
a
a
b b
a
b
ba
34
Autómatas y Lenguajes
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
18
Dra. Norka Bedregal Alpaca
Ejemplos:
El siguiente autómata acepta cadenas de la forma akb.
Mientras que el siguiente autómata acepta el lenguaje A = {(ab)i | i ≥ 1}.
35
Autómatas y LenguajesLE
NG
UA
JES
Y A
UT
ÓM
ATA
S
Dra. Norka Bedregal Alpaca
Ejercicio:
Compruebe que el autómata de la figura acepta cadenas de la forma (ab)*.
36
Autómatas y Lenguajes
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
19
Dra. Norka Bedregal Alpaca
Ejercicio:
Construya un autómata que genere el lenguaje a*b ∪ ab*
37
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS
Autómatas y Lenguajes
Dra. Norka Bedregal Alpaca
38
FIN
LEN
GU
AJE
S Y
AU
TÓ
MA
TAS