Construya una máquina de Turing para el lenguaje L = {02n1n | n>=0}

Prerrequisito – Máquina de Turing

El lenguaje L = {0 ²ⁿ 1 ⁿ | n >= 0} representa un tipo de lenguaje en el que usamos solo 2 símbolos, es decir, 0 y 1. Al principio, el lenguaje tiene un número de 0 seguido de exactamente la mitad del número de 1. Cualquier string que caiga en esta categoría será aceptada por este idioma.

Ejemplos:

Input : 001
Output : YES

Input : 00001
Output : NO 

Input :  or empty string
Output : YES 

Representación básica –

Inicio del cálculo:
la cinta contiene la string de entrada w, el cabezal de la cinta está en el símbolo más a la izquierda de w y la máquina de Turing está en el estado de inicio Q0.

Idea básica:
el cabezal de la cinta lee el símbolo más a la izquierda de w, que es 0 y deja en blanco, luego el siguiente 0 más a la izquierda se deja en blanco después de esto, recorremos el 1 más a la derecha de la string y lo dejamos en blanco. En la enésima forma, hemos reducido la string a 0 ^2n-2 1 ^n-1 . Si la string pertenece al idioma L, al final se dejará una string vacía y, por lo tanto, la máquina la aceptará.

Significados de los símbolos utilizados:
R, L – dirección de movimiento de una unidad a cada lado.
B-En blanco.
0, 1: símbolos cuya string de combinación se va a probar.

Procedimiento de trabajo :

• Paso 1:
  Como sabemos, la string tendrá el doble de ceros al principio que la cantidad de unos. Entonces, primero dejaremos los primeros dos ceros en blanco y pasaremos del estado Q0 al Q1 y del estado Q1 al Q2.
• Paso 2:
  después de dejarlos en blanco, viajaremos hasta el final de la string hasta que obtengamos el 1 más a la derecha en el estado Q3 y lo dejaremos en blanco para alcanzar el estado Q4.
• Paso 3:
  ahora retrocederemos hasta que obtengamos el cero más a la izquierda en la string y regresemos al estado Q0 desde Q4.
• Paso 4:
  simplemente estamos reduciendo la string dejando dos ceros en blanco más a la izquierda y 1 en blanco más a la derecha y si la string pertenece al idioma, se dejará vacía y, por lo tanto, se aceptará en el estado Q5, que es el estado final. Si la string está vacía, también se aceptará en Q5.