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

Ejercicio 02

(m) $\{(x,y)/x,y\in \{0,1\}*\land$(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.

<graphviz> digraph G { rankdir="LR"; graph [ranksep = 0.7, nodesep=0.4]; node [shape=circle,fontname=Helvetica,fontsize=12]; node [width=0.7,height=0.7,fixedsize=true]; edge [fontname=Helvetica,fontsize=10];

c0 [label="C, +0"] c1 [label="C, +1"] nc0 [label="NC, +0"] nc1 [label="NC, +1"] ext [label="extra"] q0 [label="q0"] qf [label="qf", shape=doublecircle]

q0 -> nc1 [label="1 | 1"] q0 -> ext [label="1 | 1"] ext -> c1 [label="- | 0"] c1 -> c1 [label="1 | 1"] c1 -> c0 [label="0 | 0"] c0 -> c1 [label="1 | 0"] nc0 -> c0 [label="0 | 1"] c1 -> nc1 [label="1 | 0"] nc1 -> nc0 [label="0 | 1"] nc0 -> nc1 [label="1 | 1"] nc0 -> nc0 [label="0 | 0"] nc1 -> qf [label="- | 1"] nc0 -> qf [label="- | 0"] } </graphviz>