De lenguajes y palabras

No one shall expel us from the paradise which Cantor has created for us

—

David Hilbert

​

Buscamos identificar propiedades fundamentales de las computadoras

2

💻

3

👉

👉

👉

👉

Escenario deseado

• Computadora como un objeto integral

💻

• La computadora y su relación con el exterior

🌎➡️💻➡️🌎

​

4

Primero, necesitamos una forma de hablar de cualquier computadora

5

💻

Abstracción de computadora

Una computadora para gobernar a todas

6

1

Como caja negra

7

Pero...

Muchas entradas

En este escenario es difícil determinar qué entrada causa el comportamiento de la caja negra…

… pero las computadoras a las que estamos acostumbrados tienen muchas entradas

Muchas salidas

En este escenario es difícil determinar por qué la salida es como es…

… pero las computadoras a las que estamos acostumbrados tienen muchas salidas

8

Sobre las entradas en nuestras computadoras

• Número�1, 2, 3, 4, ...
• Tipos�booleanos, números, cadenas, estructuras, clicks, funciones, ...
• Dispositivos:�Teclado, mouse, táctil, antenas, sensores...

9

Sobre las salidas en nuestras computadoras

• Número�1, 2, 3, 4, ...
• Tipos�booleanos, números, cadenas, estructuras, colores,, ...
• Dispositivos:�Pantalla, impresoras, bocinas, antenas, ...

10

Muchas entradas y salidas funcionan porque es práctico… dejando a un lado lo práctico

11

“

Propuesta

12

Una sola entrada

Las entradas se intercalan en un orden que ahora tiene que considerar nuestra caja negra.

13

Por ejemplo para la suma

Suma: a + b, puede entrar

• ‘valor de a’ : ‘valor de b’
• ‘valor de a en n-bits’ ‘valor de b en n-bits’
• ‘Posicion valor 0: valor de a’ ‘Posición valor 1: valor de b’

14

Una sola salida

La salida codifica si algo “útil” se pudo calcular dentro de la caja negra.

15

Por ejemplo para la suma

Suma: a + b, puede salir

• Verdadero si se calculó a+b
• 2+2=4
• Falso si no se calculó a+b
• ‘ab’+8
• -inf + 2
• None + 4

16

Recordemos qué queremos

Relacionar lo que pasa en la computadora con el exterior

• En nuestro modelo ¿Qué une a la “computadora” con el exterior?

​

17

En relación al exterior

Entrada

�Es el punto de contacto con el exterior 🌎

Salida

�Codifica la relación de la computadora con la entrada, no necesariamente con lo producido para el exterior

18

19

🌎

🌎

Computadoras como las conocemos

Falso/�Verdadero

Caja negra

Falso/�Verdadero

Abstracción

Qué realmente queremos

Relacionar lo que pasa en la computadora con el exterior

• Idea pasar todo el exterior a nuestra “caja negra” y checar que pasa con su salida

​

20

Alfabetos y cadenas

Formalizando las entradas

21

2

Aquí vienen nuestros conjuntos

22

💻

Alfabeto

23

Alfabeto

• Conjunto de elementos "básicos" finito
• Notación Σ

​

​

​

​

24

Ejemplos de alfabeto

• {a,b}
• {0,1}
• {import ,print ,for ,in ,v1 ,1,2,3,[,],′,′,m,’ ‘}

​

​

​

​

25

Cadenas

26

Cadenas

• Secuencia finita de elementos de un alfabeto Σ
• Notación w

​

​

​

​

27

Ejemplos de cadenas

• Baaaaa,bab y abbbbabbbb
• 0,1,0101,10001 y 10001
• import m,for v1 in[1,2,3] y in while if

​

​

​

​

​

28

Longitud de una cadena

|w| → n

• |baaaaa|=6
• |bab|=3
• |abbbbabbbb|=11
• |0|=1
• |1|=1
• |0101|=4

​

​

​

​

​

29

La cadena vacia

Longitud cero, una secuencia donde se escoge ningún elemento del alfabeto

Notación: ε

|ε|=0

​

​

​

​

30

La operación concatenación de cadenas

Para dos palabras w₁ y w₂

• w₁=a₁₁a₁₂...a_1n donde |w₁|=n
• w₂=a₂₁a₂₂...a_2m donde |w₂|=m

La concatenación de w₁ y w₂ es

w₁w₂=a₁₁a₁₂...a_1na₂₁a₂₂...a_2m

​

​

​

​

31

Ejemplos de concatenación de cadenas

• b y aaaa = baaaa
• 0 y 1 = 01
• 1 y 0 = 10
• ε y 0 = 0
• 1 y ε = 1

​

​

​

​

​

32

Propiedades de la concatenación de cadenas

• w₁w₂≠w₂w₁
• w₁w₂w₃=(w₁w₂)w₃=w₁(w₂w₃)
• wε = εw = w
• |w₁w₂|=|w₁|+|w₂|

​

​

​

​

​

​

33

Lenguajes

34

Lenguajes

35

💻

¡Lenguajes!

36

💻

¡¡Lenguajes!!

37

💻

¡¡¡Lenguajes!!!

38

💻

Lenguaje

• Conjunto de cadenas basado en un alfabeto Σ
• Notación L

​

​

​

​

39

Bienvenidos al infinito

y más allá

40

Ejemplos de lenguaje

• {a,aa, aaa, aaaa, aaaaa, aaaaaa}
• {bb,aa,bbbb,aaaa,bbbb,aaaaa}
• {a,b,aa,ab,ba,bb,aaa,aba,aab,baa,abb,bba,bab,bbb,...}
• {a,b}

​

​

​

​

41

Lenguajes Notables

• {ε}�El lenguaje de la cadena vacía�
• {} = ∅�El lenguaje vacío

​

​

​

42

Potencia

Lenguajes a partir de alfabetos

43

3

Potencia de un alfabeto Σⁿ

Σ¹

Lenguaje formado por todas las cadenas formadas concatenaciones de un sólo símbolo del alfabeto Σ

Σ²

Lenguaje formado por todas las cadenas formadas por concatenaciones de dos símbolos del alfabeto Σ

Σ³

Lenguaje formado por todas las cadenas formadas por concatenaciones de tres símbolo del alfabeto Σ

​

Σ⁰={ε}

Lenguaje formado por todas las cadenas conformadas por ningún símbolo del alfabeto Σ

44

Ejemplo Σ={a,b}

Σ¹

{a,b}

Σ²

{aa,ab,ba,bb}

Σ³

{aaa,aab,aba,baa,abb,bab,bba,bbb}

​

Σ⁰={ε}

{ε}

45

Otro lenguaje notable

Σ^*=Σ⁰∪ Σ¹∪ Σ²∪ Σ³∪…�

Ejemplo Σ={a,b}:

Σ*={𝜺, a, b, aa, ab, ba, bb, aaa, aba, aab, baa, abb, bba, bab, bbb, ...}

​

El conjunto de todas las palabras posibles usando el alfabeto Σ

​

​

​

46

Consecuencia de Σ*

Todo L sobre Σ es un subconjunto de Σ*

47

Ilustración

48

Σ*

Hasta ahora

De alfabeto 🠚 cadena

De cadenas 🠚 lenguaje

De alfabeto 🠚 lenguaje

​

​

49

Operaciones lenguajes

Lenguajes a partir de lenguajes

50

4

Concatenación de lenguajes

Entre dos lenguajes L₁ y L₂

​

Todas las cadenas posibles de concatenaciones entre cadenas del lenguaje uno y el lenguaje dos

Formalmente

​

L₁L₂={w₁w₂| w₁∈L₁ y w₂∈L₂}

51

Ejemplos

L₁={aa}, L₂={a,b}, L₃={ϵ} y L₄={a,aa,aaa,aaaa,...}

​

• L₁L₂= {aaa,aab}
• L₂L₁= {aaa,baa}
• L₂L₂= {aa,ab,ba,bb}
• L₂L₃= {a,b}
• L₁L₄= {aaa,aaaa,aaaaa,...}

52

L^*

¿Si es posible concatenar dos lenguajes podemos pensar en la potencia de un lenguaje?

​

Sí

53

Cerraduras de lenguajes

​

• L^∗ =⋃^∞_i=0Lⁱ (Cerradura estrella)

​

• L⁺ =⋃^∞_i=1 Lⁱ (Cerradura más)

​

54

Stephen C. Kleene

55

Ejemplos de cerraduras

Para L={aa}

​

L^∗ = {ε ,aa,aaaa,aaaaaa,aaaaaaaa,...}

L⁺ = { aa,aaaa,aaaaaa,aaaaaaaa,...}

​

¿Cómo describirían este lenguaje?

​

56

Cerraduras notables

{ε}^*={ε}

{ε}⁺={ε}

​

∅^*={ε}

∅⁺={}

57

El poder de la cadena vacía y concatenación

{ε}L=L

L{ε}=L

​

{ε,...}L=({ε}∪Lr)L=({ε}L)∪(LrL)=L∪LrL

58

Además operaciones normales de conjuntos

• Union: L₁∪L₂
• Intersección: L₁∩L₂
• Diferencia: L₁−L₂

​

• Complemento: Σ*−L₂

​

​

​

59

Unión

60

Σ*

Lenguaje uno

Lenguaje dos

L₁ ∪ L₂

Concatenación

caso sin cadena vacía en lenguaje

61

Σ*

Lenguaje uno

Lenguaje dos

L₁ L₂

Concatenación

caso con cadena vacía en un lenguaje

62

Σ*

Lenguaje uno

Lenguaje dos

L₁ L₂

Concatenación

caso con cadena vacía en ambos lenguajes

63

Σ*

Lenguaje uno

Lenguaje dos

L₁ L₂

Cerradura

64

Σ*

Lenguaje

L^*

Complemento

65

Σ*

Lenguaje

L

Formas de hablar de lenguajes

• Enumerando el lenguaje�{a,b,aa,ab,ba,bb,...}
• Usando operaciones�L₁∪L₂
• Describiendo una propiedad�{w | |w| es par}
• De forma descriptiva�El lenguaje cuyas longitud de cadena es par

66

Gracias

¿Alguna pregunta ?

​

​

• @ivanvladimir
• ivanvladimir@turing.iimas.unam.mx

67

Resumen

Computadora como caja negra

Una entrada tipo cadena, y una salida tipo booleano

Conceptos de alfabeto, cadena y lenguaje

Operaciones sobre alfabetos

Operaciones sobre lenguajes

Formas de describir a un lenguaje

​

​

Esta obra está bajo una Licencia Creative Commons Atribución 4.0 Internacional.

​