Download - La máquina sin memoria
![Page 1: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/1.jpg)
La máquina sin memoria
Memory can change the shape of a room; it can change the color of a car. And memories can bedistorted. They're just an interpretation, they're not a record, and they're irrelevant if you have thefacts. —Leonard Shelby, Memento
Ivan Meza
![Page 2: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/2.jpg)
Hasta ahoraAlfabetos, Palabras, Lenguajes,
Σw
L
![Page 3: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/3.jpg)
Para lenguajes
ConcatenaciónUniónCerradura
esto es equivalente
![Page 4: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/4.jpg)
![Page 5: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/5.jpg)
({b {a}{b {a}{b}∗ }∗ }∗)∗
![Page 6: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/6.jpg)
Regresando al objetivo
![Page 7: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/7.jpg)
Todas lás máquinas
Caja negra
Ya podemos hablar de todas las entradas: de�nimos unalfabeto, creamos cadenas, vemos las salidas...
![Page 8: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/8.jpg)
El verdadero objetivo
Caja negraL Verdadero
Falso
Asociar lenguajes a un comportamiento de la máquina
![Page 9: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/9.jpg)
Opciones
Algunas cadenas de resultan en verdadero y otras falsosTodas las cadenas de resultan en verdaderoTodas las cadenas de resultan en falso
LLL
![Page 10: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/10.jpg)
Caso interesante
Todas las cadenas resultan en verdadero
Si se dá, tendríamos una correspondencia entre máquina ylenguaje
![Page 11: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/11.jpg)
Los circulos de Dante
![Page 12: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/12.jpg)
Jerarquía de Chomsky
regular
independiente del contexto
dependiente del contexto
recursivamente enumerable
![Page 13: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/13.jpg)
Jerarquía de Chomsky
independiente del contexto
dependiente del contexto
recursivamente enumerable
regular
![Page 14: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/14.jpg)
Lenguajes regularesLenguages básicosComposición de lenguajes regulares
![Page 15: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/15.jpg)
Lenguajes básicos regulares, el lenguaje vacío, es regular
, el lenguaje de la cadéna vacía, es regularSi entonces , el lenguaje un símbolo del alfabeto, esregular
∅{ϵ}
a ∈ Σ {a}
![Page 16: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/16.jpg)
Composición de lenguajesregulares
Si y son regulares, entonces es regularSi y son regulares, entonces es regularSi es regular, entonces es regularSi es regular, entonces es regular
L1 L2 ∪L1 L2L1 L2 L1L2L L∗
L (L)
![Page 17: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/17.jpg)
Un lenguaje es regular si es un lenguaje básico regular o si se puedegenerar a través de una secuencia �nita de operaciones de lenguajesregulares de lenguajess
![Page 18: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/18.jpg)
El lenguaje regular de número debes paresCon Σ = {a, b}
Ejemplos:
bbbbabbaabbabbaabbabbaaaaaaaabaaababaabaaaaaa
![Page 19: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/19.jpg)
y {a} {b}{b}{a}{b}{b}{a {b}}∗
{a}{b}{a {b}{a}}∗
{a {b}{a {b}{a}∗ }∗ }∗
({a {b}{a {b}{a}∗ }∗ }∗)∗
![Page 20: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/20.jpg)
Expresiones regularesExpresiones básicasComposición de expresiones regulares
![Page 21: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/21.jpg)
Expresiones básicas regulares representa al lenguaje vacío representa al lenguaje de la cadéna vacía representa al lenguaje de un símbolo del alfabeto
∅ϵa
Ésta es notación para representar lenguajes regulares básicos
![Page 22: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/22.jpg)
Composición de lenguajesregulares
representa a la unión de dos lenguajes representa la concatenación
representa a la cerradura sobre un lenguaje representa al lenguaje con prioridad
+L1 L2L1L2L∗
(L)
![Page 23: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/23.jpg)
El lenguaje regular de número debes pares
({a {b}{a {b}{a}∗ }∗ }∗)∗
Su expresión regular es:
( b ba∗ a∗ a∗)∗
(b ba∗ a∗ a∗)∗
![Page 24: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/24.jpg)
El lenguaje regular cuyopenúltimo símbolo a
![Page 25: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/25.jpg)
Un cambio de canal: ¡máquinas!
![Page 26: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/26.jpg)
![Page 27: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/27.jpg)
![Page 28: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/28.jpg)
Autómata finitoEs una tupla (Q, Σ, , A, δ)q0
conjunto finito de estados un alfabeto estado inicial, conjunto de estados finales,
función de transición
QΣq0 ∈ Qq0A A ⊆ Qδ δ : Q × Σ → Q
Tambien conocida: Máquina de estados �nitos
![Page 29: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/29.jpg)
q₀ q₁b
a a
b
![Page 30: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/30.jpg)
Estados, Q = { , }q0 q1
q₀ q₁
![Page 31: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/31.jpg)
Alfabeto, Σ = {a, b}
b
a a
b
![Page 32: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/32.jpg)
Estado inicial, q0
q₀
![Page 33: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/33.jpg)
Estados finales, { }q0
q₀
![Page 34: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/34.jpg)
Función de transición, δ
q₀ q₁b
a a
b
![Page 35: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/35.jpg)
En otras palabras
({ , }, {a, b}, , { }, δ)q0 q1 q0 q0
donde δ =
⎧⎩⎨⎪⎪⎪⎪⎪⎪
( , a) →q0 q0
( , b) →q0 q1
( , a) →q1 q1
( , b) →q1 q0
![Page 36: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/36.jpg)
Variaciones
![Page 37: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/37.jpg)
q₀ q₁b
a a
b
![Page 38: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/38.jpg)
En otras palabras
({ , }, {a, b}, , { }, δ)q0 q1 q0 q1
donde δ =
⎧⎩⎨⎪⎪⎪⎪⎪⎪
( , a) →q0 q0
( , b) →q0 q1
( , a) →q1 q1
( , b) →q1 q0
![Page 39: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/39.jpg)
q₀ q₁b
a a
b
![Page 40: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/40.jpg)
En otras palabras
({ , }, {a, b}, , { , }, δ)q0 q1 q0 q0 q1
donde δ =
⎧⎩⎨⎪⎪⎪⎪⎪⎪
( , a) →q0 q0
( , b) →q0 q1
( , a) →q1 q1
( , b) →q1 q0
![Page 41: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/41.jpg)
Cadenas aceptadas por un AF
De�niendo función de transición extendida
= {δ∗ (q, ϵ) = qδ∗
(q, wa) = δ( (q, w), a)δ∗ δ∗q ⊆ Q
q ⊆ Q, w ⊆ , a ⊆ ΣΣ∗
![Page 42: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/42.jpg)
Con la cadena: abbaa
q₀ q₁b
a a
b
![Page 43: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/43.jpg)
( , abbaa) = δ( ( , abba), a)δ∗ q0 δ∗ q0= δ(δ( ( , abb), a), a)δ∗ q0= δ(δ(δ( ( , ab)b), a), a)δ∗ q0= δ(δ(δ(δ( ( , a), b), b), a), a)δ∗ q0= δ(δ(δ(δ(δ( ( , ϵ), a), b), b), a), a)δ∗ q0= δ(δ(δ(δ(δ( , a), b), b), a), a)q0= δ(δ(δ(δ( , b), b), a), a)q0= δ(δ(δ( , b), a), a)q1= δ(δ( , a), a)q0= δ( , a)q0= q0
![Page 44: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/44.jpg)
Ya que pertence a , la cadena es aceptadaq0 A
![Page 45: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/45.jpg)
Un automata acepta un lenguaje A L
Si es aceptada por Si no es aceptada por
w ∈ L Aw ∉ L A
![Page 46: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/46.jpg)
Ejemplos
![Page 47: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/47.jpg)
q₀ q₁ q2 q₃a a a
Concatenación
![Page 48: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/48.jpg)
q₀ q₁ q2 q₃a a a
b
Cerradura
![Page 49: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/49.jpg)
q₀ q₁ q2 q₃
q₄ q₅ q₆
a a a
bb b
b
a
Unión
![Page 50: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/50.jpg)
Teorema de KleenUn lenguaje sobre el alfabeto es regular si y sólo si existeun AF con un alfabeto que acepta
L ΣΣ L
![Page 51: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/51.jpg)
Una pausa
![Page 52: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/52.jpg)
Vamos a repetirlo
![Page 53: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/53.jpg)
Teorema de Kleen
Un lenguaje sobre el alfabeto esregular si y sólo si existe un AF con unalfabeto que acepta
L Σ
Σ L
![Page 54: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/54.jpg)
Otra pausa
![Page 55: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/55.jpg)
Un lenguaje sobre elalfabeto es regular si ysólo si existe un AF conun alfabeto queacepta
LΣ
ΣL
![Page 56: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/56.jpg)
¿Qué información recuerda lamáquina?
![Page 57: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/57.jpg)
El estado
![Page 58: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/58.jpg)
Dado un lenguaje y L w ∈ Σ∗
Vamos a de�nir al lenguaje como:L/w
L/w = {z ∈ |wz ∈ L}Σ∗
![Page 59: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/59.jpg)
q₀ q₁b
a a
b
Ejemplo: si le concatenamos L/a z = (b ba∗ a∗)∗
![Page 60: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/60.jpg)
son todas las cadenas que concatenadas a diferentes llegan a un estado �nalL/w z
Para que ambos sean iguales,
( , z)δ∗ q0 w1( , z)δ∗ q0 w2
( ( , ), z)δ∗ δ∗ q0 w1( ( , ), z)δ∗ δ∗ q0 w2
( , ) = ( , )δ∗ q0 w1 δ∗ q0 w2
![Page 61: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/61.jpg)
q₀ q₁b
a a
b
Comparar con , son la mismaL/a L/a∗
![Page 62: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/62.jpg)
q₀ q₁b
a a
b
Comparar , , ,son la mismaL/a L/a∗ L/ b ba∗ a∗
![Page 63: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/63.jpg)
L/a∗
L/ b ba∗ a∗
L/( b ba∗ a∗ )∗
Concatenadas con siempre llegan a , no sondiferenciables
(b ba∗ a∗)∗ q0
![Page 64: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/64.jpg)
q₀ q₁b
a a
b
¿Qué hay de ?, concatenada con L/a ∗ b ( b (b ba∗ a∗)∗ a∗ a∗)∗
![Page 65: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/65.jpg)
L/ ba∗
L/ b( b ba∗ a∗ a∗ )∗
Concatenadas con siempre llegan a , no son diferenciables
(a^*ba^*)^*(ba^*ba^a^*)^*
q0
![Page 66: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/66.jpg)
Sin embargo,
, con , con
L/( b ba∗ a∗ )∗ z = (b ba∗ a∗)∗
L/ b( b ba∗ a∗ a∗ )∗ z = ( ba∗ a∗)∗
Si son diferenciables porque son dos diferentesz
![Page 67: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/67.jpg)
¿Cuantos estados hay para un lenguaje ?L
¿Cuantos conjuntos diferenciables hay?
Los estados dividen en conjutos las cadenas
![Page 68: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/68.jpg)
Lenguajes regularesExpresiones regulares
BásicasComposición
Autómatas finitosEstadosEstado finalEstados aceptoresFunción de transición
Función de transición extendidaCadenas diferenciables
![Page 69: La máquina sin memoria](https://reader031.vdocumento.com/reader031/viewer/2022013109/58f04f5e1a28abb2328b4689/html5/thumbnails/69.jpg)
[email protected] ivanvladimir.github.io ivanvladimir
La máquina sin memoria 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/fsm.html