de palabras y lenguajes
TRANSCRIPT
![Page 1: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/1.jpg)
De palabras y lenguajes
It appeared that way, Lawrence, but this raised the question of was mathematics really true or was it just a gameplayed with symbols? In other words—are we discovering Truth, or just wanking? —
Neal Stepheson, Cryptomicon
Ivan Meza
![Page 2: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/2.jpg)
¿Qué es una computadora?
¿Qué hace una computadora?
¿Qué no hace una computadora?
![Page 3: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/3.jpg)
Una buena aproximación...
Proceso/cajanegra
Caja negra
![Page 4: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/4.jpg)
Entradas¿Cuántas y cuáles?
Una, dos, tres....Booleanos, Números, cadenas, estructuras,funciones
![Page 5: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/5.jpg)
Salidas¿Cuántas y cuáles?
UnaBooleanos, números, cadenas, estructuras,funciones
![Page 6: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/6.jpg)
¿Cómo hablamos de todas las cajasnegras?
Una entradaUna salidaBooleano
![Page 7: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/7.jpg)
Caja negra
![Page 8: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/8.jpg)
Una entrada: muchos casos
Todas las entradas pueden ser reducidas a una, porconcatenación de cadenas
Existen muchas cajas negras para todas estas entradas
![Page 9: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/9.jpg)
Una salida: dos casos
El caso más sencillo
Existen muchas cajas negras para estas dos salidas
![Page 10: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/10.jpg)
¿Cómo generamos todas las entradas?
Combinaciones de elementos básicos
![Page 11: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/11.jpg)
¡Teoría de conjuntos!
![Page 12: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/12.jpg)
concepto AlfabetoUn conjunto de elementos "básicos"
finitoNotación Σ
![Page 13: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/13.jpg)
Ejemplos de alfabetos{a, b}{0, 1}
{import , print , for , in , v1 , 1, 2, 3, [, ] },′ ,′
![Page 14: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/14.jpg)
concepto Cadena
Secuencia finita de elementos de un alfabeto
Notación
Σ
w
![Page 15: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/15.jpg)
Ejemplos de cadenasbaaaaa, bab, abbbbabbbb, . . .0, 1, 0101, 10001, 10001, . . .
import m, for v1 in[1, 2, 3], in while if, . . .
![Page 16: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/16.jpg)
Longitud de una cadena|baaaaa| = 6|bab| = 3
|abbbbabbbb| = 11|0| = 1|1| = 1|0101| = 4
![Page 17: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/17.jpg)
Longitud de una cadena|10001| = 5|10001| = 5|import m| =?
|for v1 in[1, 2, 3]| =?|in while if| =?
![Page 18: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/18.jpg)
concepto LA CADENA VACIALongitudceroNotación ϵ
0|ϵ| =
![Page 19: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/19.jpg)
concepto ConcatenaciónPara dos palabras y w1 w2
= . . .w1 w11 w12 w1m
| | = mw1= . . .w2 w21 w22 w2n
| | = nw2
La concatenación de y esw1 w2
= . . . . . .w1w2 w11 w12 w1mw21 w22 w2n
aab bba = aabbba
![Page 20: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/20.jpg)
Propiedades de la concatenación≠w1w2 w2w1
= ( ) = ( )w1w2w3 w1w2 w3 w1 w2w3ϵ = ϵ =w1 w1 w1
| | = | | + | |w1w2 w1 w2
![Page 21: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/21.jpg)
Lenguajes
![Page 22: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/22.jpg)
¡Lenguajes!
![Page 23: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/23.jpg)
¡¡Lenguajes!!
![Page 24: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/24.jpg)
¡¡¡Lenguajes!!!
![Page 25: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/25.jpg)
concepto LenguajesConjunto de cadenas de un alfabeto
Notación
Σ
L
![Page 26: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/26.jpg)
Bienvenidos alinfinito
![Page 27: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/27.jpg)
Ejemplos de lenguajes{a, b}{aa, bb, aaa, bbb, aaaa, bbbb}
{a, aa, aaa, aaaa, aaaaa, . . . }
![Page 28: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/28.jpg)
Lenguajes notables{ϵ}
{} = ∅
![Page 29: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/29.jpg)
Potencia de un alfabetoDe alfabeto a lenguaje , supongamos Σ L Σ = {a, b}
...
= {ϵ}Σ0
= {a, b}Σ1
= {aa, ab, ba, bb}Σ2
= {aaa, aab, aba, abb, baa, bab, bba, bbb}Σ3
![Page 30: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/30.jpg)
Un lenguaje notable
El conjunto de todas las palabras posibles con , incluyendo lacadena vacía
= ∪ ∪ ∪ ∪. . .Σ∗ Σ0 Σ1 Σ2 Σ3
Σ
Para Σ = {a, b}
= {ϵ, a, b, aa, ab, ba, bb, aaa, aan, aba, abb, baa, bab, bba, bbb,Σ∗
![Page 31: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/31.jpg)
Todo sobre es un subconjunto de L Σ Σ ∗
![Page 32: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/32.jpg)
concepto Concatenación de lenguajesPara dos lenguajes y L1 L2
= { | ∈ y ∈ }L1L2 w1w2 w1 L1 w2 L2
![Page 33: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/33.jpg)
Ejemplos concatenación de lenguajes, , y = {aa}L1 = {a, b}L2 = {ϵ}L3
= {a, aa, aaa, aaaa, . . . }L4
=L1L2 {aaa, aab}=L2L1 {aaa, baa}=L2L2 {aa, ab, ba, bb}=L2L3 {a, b}=L1L4
{aaa, aaaa, aaaaa, . . . }
![Page 34: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/34.jpg)
Si podemos concatenar lenguajes ¿exite ?L∗
![Page 35: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/35.jpg)
Cerradura de un Lenguaje (Kleene
estrella)
(Kleene más)
=L∗ ⋃∞i=0 Li
=L+ ⋃∞i=1 Li
![Page 36: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/36.jpg)
Stephen C. Kleene
![Page 37: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/37.jpg)
Ejemplos de cerradurasPara L = {aa}
= {ϵ, aa, aaaa, aaaaaa, aaaaaaaa, . . . }L∗
= { aa, aaaa, aaaaaa, aaaaaaaa, . . . }L+
¿alguien puede describir este lenguaje?
![Page 38: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/38.jpg)
Cerraduras notables{ϵ =}∗ {ϵ}{ϵ =}+
{ϵ}
∅∗ ={ϵ}=∅+ { }
![Page 39: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/39.jpg)
El poder de la cadena vacía
{ϵ}L = L
L{ϵ} = L
Si presente, copia un lenguajeϵ
{ϵ, . . . }L = ({ϵ} ∪ )L = ({ϵ}L) ∪ ( L) = L ∪ LLr Lr Lr
![Page 40: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/40.jpg)
Las operaciones normales de losconjuntos
Union: Intersección:
Diferencia:
∪L1 L2
∩L2 L2−L1 L2
![Page 41: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/41.jpg)
Complemento
= − LL¯ ¯¯̄ Σ∗
![Page 42: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/42.jpg)
concepto Lenguajes que generan lenguajesConcatenaciónCerraduraOperación deconjuntos
Todos aceptan lenguajes y crean "nuevos" lenguajes
![Page 43: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/43.jpg)
Describiendo lenguajes con propiedad{w|w ∈ Σ
}
![Page 44: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/44.jpg)
Ejemplos de lenguajesSi Σ = {a, b}
y con número par de aes y con sólo bes y número impar de bes
{w|w ∈ Σ∗ }{w|w ∈ Σ∗
}
![Page 45: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/45.jpg)
AlfabetoCadenasLenguajesDe alfabeto a lenguaje: potenciaConcatenación de lenguajesOperaciones que toman lenguajes y hacen otroslenguajes
![Page 46: De palabras y lenguajes](https://reader031.vdocumento.com/reader031/viewer/2022022413/58efa71c1a28ab915f8b459b/html5/thumbnails/46.jpg)
[email protected] ivanvladimir.github.io ivanvladimir
De palabras y lenguajes by is licensed under a.
Creado a partir de la obra en.
Ivan V. Meza RuizCreative Commons Reconocimiento 4.0 Internacional License
http://turing.iimas.unam.mx/~ivanvladimir/slides/lfya/lenguajes.html