Práctica 5: Traductores finitos (Teoría de Lenguajes)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 01[editar]

Ejercicio 02[editar]

Para cada na de las siguientes relaciones dar un traductor finito que la compute. Hacerlo determinístico en los casos en que sea posible.

  • b)

P5E2B.png

  • c)

P5E2C.png

(m) (el número natural representado por y) = 3(el número natural representado por x)}

Respuesta:

Idea: Multiplicar por 3 en binario a otro número binario N es lo mismo que hacer N + (N << 1), por ej:

(1 1 0 1 1) x (1 1) =    1 1 0 1 1 -
                       +   1 1 0 1 1
                       -------------
                       1 0 1 0 0 0 1

Entonces, en el siguiente traductor finito no determinístico lo que hacemos es representar en cada uno de los estados principales (C0, C1, NC1 y NC0) lo siguiente: Si se espera que la suma del próximo digito a leer de o no carry, y si el dígito con el cual se va a sumar es 1 o 0. Después unimos los estados sólo en formas que tienen sentido.

Por ejemplo: C1 está unido a NC1 ya que si leemos un 1, y le debemos sumar otro 1, y esperamos que de carry, una posibilidad es venir de un estado que dio carry. Además, como leimos un 1, es lo que debimos sumar en el estado de donde venimos, por eso NC1.

Parado en el estado "tengo que devolver carry" y "el segundo digito que sumo es 1" tenes 3 opciones:

- Lees 1 y venis de otro estado con carry, entonces 1+1+1 = 11

- Lees 1 y venis de otro estado sin carry, entonces 1+1+0 = 10

- Lees 0 y venis de otro estado con carry, entonces 1+0+1 = 10

y siempre lo que lees tiene que ser el segundo digito del estado al que te moves, porque estás sumando algo shifteado con si mismo entonces siempre el digito que leiste es el que va a estar abajo en el proximo paso.

Hay un par de estados extra para los estados finales y para el comienzo.

Tl5ejercicio2m.png


Ejercicio 03[editar]