Ejercicios fundamentos de la computacion

Ejercicios. Fundamentos de la Computación

1. Resolver:

1. ¿Cuántos y qué números son invertibles en Z9? Enumere los números y su inverso.
2. Determinar x en Z9 tal que: 4x + 5 = 1. Describa todos los pasos para obtener la solución.

Solución:

1. Los números invertibles en Z9 son seis:

1*1 = 1 (mod 9) ⇒ 1 es inverso de sí mismo

2*5 = 1 (mod 9) ⇒ 2 y 5 son inversos

4*7 = 1 (mod 9) ⇒ 4 y 7 son inversos

8*8 = 1 (mod 9) ⇒ 8 es inverso de sí mismo

1. 4x + 5 = 1 ⇒ 4x = 1 – 5 = 1 + 4 = 5

⇒ x = 5*4-1 = 5*7 ⇒ x = 8 (mod 9)

1. Resolver el siguiente sistema de ecuaciones en Z9. Describa todos los pasos para obtener la solución.

16x – 31y = 29

21x + 25y = 13

Solución: el sistema se reescribe usando aritmética módulo 9:

1. 7x – 4y = 2
2. 3x + 7y = 4

Multiplicando (1) por 3 y (2) por 7 se tiene:

1. 21x – 12y = 6        
2. 21x + 49y = 28

Restando (3) de (4) se tiene:

61y = 22 ⇒ 7y = 4 ⇒ y = 4*7-1 = 4*4

⇒ y = 7 (mod 9)

        ⇒ reemplazando en (1): 7x = 3 ⇒ x = 3*7-1 = 3*4 = 3 (mod 9)

1. Para el conjunto {1, 2, 3, 6, 7, 14, 15, 30, 31,…}

1. Describa sus valores en binario (que no empiece con 0) y determine un AFD que los acepte.
2. Determine la expresión regular asociada usando un sistema de ecuaciones.

Solución:

1. En binario se tiene:

{1, 10, 11, 110, 111, 1110, 1111, 11110, 11111,…}

El AFD que los acepta es:

[pic 1][pic 2][pic 3][pic 4][pic 5]

[pic 6][pic 7][pic 8][pic 9]

[pic 10][pic 11][pic 12]

[pic 13][pic 14]

[pic 15][pic 16]

[pic 17][pic 18]

[pic 19]

[pic 20][pic 21][pic 22]

[pic 23]

[pic 24]

1. El sistema de ecuaciones es:

X0 = 1X1 + 0X3 

X1 = ε + 1X1 + 0X2

X2 = ε + 1X3 + 0X3

X3 = 1X3 + 0X3 🡺 X3 = ∅ 🡺 X2 = ε

🡺 X1 = ε + 0 + 1X1 🡺 X1 = 1*(ε + 0) 🡺 X0 = 11*(ε + 0).

1. Para el alfabeto Σ = {0, 1} sea el AFD siguiente en que q1 es el estado inicial y F = {q1, q2, q5} determinar el sistema de ecuaciones y el lenguaje aceptado. Trate de simplificar las expresiones en los pasos en que pueda hacerlo.

Solución:

El sistema es:

X1 = ε +0X2 + 1X6 

X2 = ε +0X4 + 1X3 

X3 =      0X5 + 1X6 

X4 =      0X6 + 1X3 

X5 = ε +0X4 + 1X3 

X6 =      0X6 + 1X3

Entonces: X6 = 0*1X3 🡺 X5 = ε +0X4 + 1X3 

🡺 X4 = 00*1X3 + 1X3 = (00* + ε)1X3 = 0*1X3 

🡺 X3 = 0X5 + 1X6 = 0(ε + 00*1X3) + 1X3 

🡺 X3 = 0 + (000*1 + 1)X3 🡺 X3 = ((0 + 1)0*1)*0

🡺 X2 = ε +00*1((0 + 1)0*1)*0 + 1((0 + 1)0*1)*0

🡺 X2 = ε +0*1((0 + 1)0*1)*0

🡺 X1 = ε +0X2 + 1X6 

🡺 X1 = ε + 0(ε +0*1((0 + 1)0*1)*0) + 10*1((0 + 1)0*1)*0

1. Probar la siguiente equivalencia indicando las propiedades correspondientes utilizadas:

0*1(00*1 + 10*1)*(0 + 1) + ε = (0*1(0 + 1))*

Solución:

0*1(00*1 + 10*1)*(0 + 1) + ε

= 0*1((00* + 10*)1)*(0 + 1) + ε                 (r + s)t = rt + st

...