Teoría de autómatas y lenguajes formales
Enviado por Melissa Sanchez • 22 de Noviembre de 2024 • Tarea • 1.639 Palabras (7 Páginas) • 33 Visitas
Teoría de autómatas y lenguajes formales.
Tarea 1.1
- Sean 𝐴 y 𝐵 conjuntos 𝐴 = {2,3,4,5} 𝐵 = {1,3,5,7,9}. Se define la relación ℛ = {(𝑥, 𝑦) ∈ 𝐴 × 𝐵|𝑥 < 𝑦} listar todos los elementos de la relación.
ℛ = { (2,3) , (2,5) , (2,7) , (2,9) , (3,5) , (3,7) , (3,9) , (4,5) , (4,7) , (4,9) , (5,7) , (5,9) }
- Determinar si cada una de las relaciones siguientes es una relación de equivalencia sobre el conjunto 𝐴 = {0,1,2,3,4,5}:
- ℛ1 = {(0,0), (1,1), (1,2), (2,2), (3,3), (4,4), (5,5)}
La relación ℛ1 si es una relación reflexiva ya que cuenta con los pares {(0,0), (1,1), (2,2), (3,3), (4,4), (5,5)}, por lo que si se cumple que ∀x ∈ A, x ℛ x. No es una relación simétrica porque en el conjunto existe el par (1,2), pero no existe el par (2,1), entonces no se cumple ∀x, y ∈ A, x ℛ y ^ y ℛ x. Tampoco es una relación transitiva porque no se cumple ∀x, y, z ∈ A, x ℛ y ^ y ℛ z → x ℛ z, como en los siguientes ejemplos:
(0,0) ^ (1,1) → (0,1) ∉ ℛ1
(0,0) ^ (1,1) → (0,1) ∉ ℛ1
Por lo tanto, NO es una relación de equivalencia.
- ℛ2 = ℛ1 ∪ {(2,1)} = {(0,0), (1,1), (1,2), (2,2), (3,3), (4,4), (5,5), (2,1)}
La relación ℛ2 si es una relación reflexiva ya que cuenta con los pares {(0,0), (1,1), (2,2), (3,3), (4,4), (5,5)}, por lo que si se cumple que ∀x ∈ A, x ℛ x. También es una relación simétrica porque en el conjunto existe el par (1,2) igual que el par (2,1), entonces se cumple ∀x, y ∈ A, x ℛ y ^ y ℛ x. Tampoco es una relación transitiva porque no se cumple ∀x, y, z ∈ A, x ℛ y ^ y ℛ z → x ℛ z, como en los siguientes ejemplos:
(0,0) ^ (1,1) → (0,1) ∉ ℛ2
(1,1) ^ (3,3) → (1,3) ∉ ℛ2
Por lo tanto, NO es una relación de equivalencia.
- ℛ3 = ℛ1 − {(1,2)} = {(0,0), (1,1), (2,2), (3,3), (4,4), (5,5)}
La relación ℛ3 si es una relación reflexiva ya que cuenta con los pares {(0,0), (1,1), (2,2), (3,3), (4,4), (5,5)}, por lo que si se cumple que ∀x ∈ A, x ℛ x. También es una relación simétrica porque se cumple ∀x, y ∈ A, x ℛ y ^ y ℛ x, ya que el conjunto solo cuenta con pares de x relacionándose con sí misma. Tampoco es una relación transitiva porque no se cumple ∀x, y, z ∈ A, x ℛ y ^ y ℛ z → x ℛ z, como en los siguientes ejemplos:
(0,0) ^ (1,1) → (0,1) ∉ ℛ3
(1,1) ^ (3,3) → (1,3) ∉ ℛ3
Por lo tanto, NO es una relación de equivalencia.
- ℛ4 = ℛ2 ∪ {(2,3), (1,3), (3,1), (3,2)}
ℛ4 = {(0,0), (1,1), (1,2), (2,2), (3,3), (4,4), (5,5), (2,1), (2,3), (1,3), (3,1), (3,2)}
La relación ℛ4 si es una relación reflexiva ya que cuenta con los pares {(0,0), (1,1), (2,2), (3,3), (4,4), (5,5)}, por lo que si se cumple que ∀x ∈ A, x ℛ x. También es una relación simétrica porque se cumple ∀x, y ∈ A, x ℛ y ^ y ℛ x, ya que en el conjunto existe el par (1,2) igual que el par (2,1), existe el par (2,3), al igual que el par (3,2) y existe el par (1,3) igual que el par (3,1). No es una relación transitiva porque no se cumple ∀x, y, z ∈ A, x ℛ y ^ y ℛ z → x ℛ z, como en los siguientes ejemplos:
(0,0) ^ (1,1) → (0,1) ∉ ℛ2
(1,1) ^ (4,4) → (1,4) ∉ ℛ2
Por lo tanto, NO es una relación de equivalencia.
- Sea 𝑋 = {−1,0,1} y 𝐴 = ℙ(𝑋). Determinar si ℛ define una relación de equivalencia sobre 𝐴. 𝑆ℛ𝑇 ⇔ la suma de los elementos de 𝑆 es igual a la suma de elementos de 𝑇. Para 𝑆, 𝑇 ⊂ ℙ(𝑋)
ℙ(𝑋) = {(0,0), (1,1), (-1,-1), (0,1), (1,0),(0,-1),(-1,0),(1,-1),(-1,1)}
La relación ℛ si es una relación reflexiva ya que cuenta con los pares {(0,0), (1,1), (-1,-1)}, por lo que si se cumple que ∀x ∈ A, x ℛ x. También es una relación simétrica porque se cumple ∀x, y ∈ A, x ℛ y ^ y ℛ x, ya que en el conjunto existe el par (1,0) igual que el par (0,1), existe el par (0,-1), al igual que (-1,0) y existe el par (1,-1) igual que el par (-1,1). También es transitiva porque se cumple ∀x, y, z ∈ A, x ℛ y ^ y ℛ z → x ℛ z, como en los siguientes ejemplos:
(0,0) ^ (1,1) → (0,1) ∈ ℛ
(0,0) ^ (-1,-1) → (0,-1) ∈ ℛ
(0,0) ^ (0,1) → (0,1) ∈ ℛ
(0,0) ^ (1,0) → (0,1) ∈ ℛ
ℛ si define una relación de equivalencia sobre 𝐴
- Sea 𝐴 = {−4, −3,−2,−1,0,1,2,3,4}. Definimos la relación ℛ sobre el conjunto 𝐴 por:
𝑚ℛ𝑛 ⇔ 5⁄𝑚2 − 𝑛2
Enlistar todos los elementos de ℛ
ℛ = {(-4,-1), (-4,1), (-4,4), (-3,-2), (-3,2), (-3,3), (-2,-3), (-2,2), (-2,3), (-1,4), (-1,1), (-1,4), (1,-4), (1,-1), (1,4), (2,-3), (2,-2), (2,3), (3,-3), (3,-2), (3,2), (4,-4), (4,-1), (4,1)}
5 | (-4)2- (-3)2 5 | 16 – 9 5 | 7 | 5 | (-3)2- (-4)2 5 | 9 – 16 5 | -7 | 5 |(-2)2- (-4)2 5 |4 – 16 5 |-12 | 5 |(-1)2- (-4)2 5 | 1 – 16 5 |-15 | 5 | (0)2- (-4)2 5 | 0 – 16 5 |-16 | 5 |(1)2- (-4)2 5 | 1 – 16 5 |-15 | 5 |(2)2- (-4)2 5 | 4 – 16 5 |-12 | 5 |(3)2- (-4)2 5 | 9 – 16 5 |-7 | 5 |(4)2- (-4)2 5 |16 – 16 5 |0 |
5 | (-4)2- (-2)2 5 | 16 – 4 5 | 12 | 5 | (-3)2- (-2)2 5 | 9 – 4 5 |5 | 5 |(-2)2- (-3)2 5 |4 – 9 5 |-5 | 5 |(-1)2- (-3)2 5 | 1 – 9 5 |8 | 5 | (0)2- (-3)2 5 | 0 – 9 5 |-9 | 5 |(1)2- (-3)2 5 | 1 – 9 5 |-8 | 5 |(2)2- (-3)2 5 | 4 – 9 5 |-5 | 5 |(3)2- (-3)2 5 | 9 – 9 5 |0 | 5 |(4)2- (-3)2 5 |16 – 9 5 |7 |
5 | (-4)2- (-1)2 5 | 16 – 1 5 | 15 | 5 | (-3)2- (-1)2 5 | 9 – 1 5 |8 | 5 |(-2)2- (-1)2 5 |4 – 1 5 |3 | 5 |(-1)2- (-2)2 5 | 1 – 4 5 |-3 | 5 | (0)2- (-2)2 5 | 0 – 4 5 |-4 | 5 |(1)2- (-2)2 5 | 1 – 4 5 |-3 | 5 |(2)2- (-2)2 5 | 4 – 4 5 |0 | 5 |(3)2- (-2)2 5 | 9 – 4 5 |5 | 5 |(4)2- (-2)2 5 |16 – 4 5 |12 |
5 | (-4)2- (0)2 5 | 16 – 0 5 |16 | 5 | (-3)2- (0)2 5 | 9 – 0 5 |9 | 5 | (-2)2- (0)2 5 |4 – 0 5 |4 | 5 |(-1)2- (0)2 5 | 1 – 0 5 |1 | 5 | (0)2- (-1)2 5 | 0 – 1 5 |-1 | 5 |(1)2- (-1)2 5 | 1 – 1 5 |0 | 5 |(2)2- (-1)2 5 | 4 – 1 5 |3 | 5 |(3)2- (-1)2 5 | 9 – 1 5 |8 | 5 |(4)2- (-1)2 5 |16 – 1 5 |15 |
5 | (-4)2- (1)2 5 | 16 – 1 5 |15 | 5 | (-3)2- (1)2 5 | 9 – 1 5 |8 | 5 | (-2)2- (1)2 5 |4 – 1 5 |3 | 5 |(-1)2- (1)2 5 | 1 – 1 5 |0 | 5 | (0)2- (1)2 5 | 0 – 1 5 |-1 | 5 |(1)2- (0)2 5 | 1 – 0 5 |1 | 5 |(2)2- (0)2 5 | 4 – 0 5 |4 | 5 |(3)2- (0)2 5 | 9 – 0 5 |9 | 5 |(4)2- (0)2 5 |16 – 0 5 |16 |
5 | (-4)2- (2)2 5 | 16 – 4 5 |12 | 5 | (-3)2- (2)2 5 | 9 – 4 5 |5 | 5 | (-2)2- (2)2 5 |4 – 4 5 |0 | 5 |(-1)2- (2)2 5 | 1 – 4 5 |-3 | 5 | (0)2- (2)2 5 | 0 – 4 5 |-4 | 5 |(1)2- (2)2 5 | 1 – 4 5 |-3 | 5 |(2)2- (1)2 5 | 4 – 1 5 |3 | 5 |(3)2- (1)2 5 | 9 – 1 5 |8 | 5 |(4)2- (1)2 5 |16 – 1 5 |15 |
5 | (-4)2- (3)2 5 | 16 – 9 5 |7 | 5 | (-3)2- (3)2 5 | 9 – 9 5 |0 | 5 | (-2)2- (3)2 5 |4 – 9 5 |-5 | 5 |(-1)2- (3)2 5 | 1 – 9 5 |-8 | 5 | (0)2- (3)2 5 | 0 – 9 5 |-9 | 5 |(1)2- (3)2 5 | 1 – 9 5 |-8 | 5 |(2)2- (3)2 5 | 4 – 9 5 |-5 | 5 |(3)2- (2)2 5 | 9 – 4 5 |5 | 5 |(4)2- (2)2 5 |16 – 4 5 |12 |
5 | (-4)2- (4)2 5 | 16 – 16 5 |0 | 5 | (-3)2- (4)2 5 | 9 – 16 5 |-7 | 5 | (-2)2- (4)2 5 |4 – 16 5 |12 | 5 |(-1)2- (4)2 5 | 1 – 16 5 |-15 | 5 | (0)2- (4)2 5 | 0 – 16 5 |-16 | 5 |(1)2- (4)2 5 | 1 – 16 5 |-15 | 5 |(2)2- (4)2 5 | 4 – 16 5 |-12 | 5 |(3)2- (4)2 5 | 9 – 16 5 |-7 | 5 |(4)2- (3)2 5 |16 – 9 5 |7 |
...