Diseño

Por cada cero (‘0’) en la cinta de entrada vamos a escribir una ‘C’, y por cada uno (‘1’) una ‘U’, de tal forma que, si finalmente todos los ceros y todos los unos en la cinta han sido sustituidos por una ‘C’ o una ‘U’, respectivamente, la cadena en la cinta es aceptada. La forma de sustituir estará dada de la siguiente manera:

(1) El primer cero de izquierda a derecha sustituirlo por C

(2) Avanzar a la derecha hasta encontrar un uno y sustituirlo por U

(3) Avanzar a la derecha hasta encontrar un cero y sustituirlo por C

(4) Retroceder pasando por los unos y U’s hasta encontrar una C precedida por un cero

Y Repetir (1) , hasta tener

En caso de que no se puede cumplir: “El primer cero de izquierda a derecha…” , “Avanzar a la derecha hasta encontrar un …”, “Retroceder pasando por los unos y U’s hasta encontrar …”, la cadena no será aceptada.

Formalizando.

Sea M = (Q, Σ, Γ, , q0, B, F)

La Máquina de Turing que reconoce el lenguaje

{0n1n0n | n  1}

Entonces:

Q = {q0, q1, q2, q3, q4, q5, q6, q7}

Σ = {0, 1}

Γ = {0, 1, B, C, U}

q0 = q0

F = {q6}

...