Máquina de Turing para L = {a^nb^n | n>=1}

Prerrequisito – Máquina de Turing

Tarea :

Tenemos que diseñar una máquina de Turing para a ⁿ b ⁿ donde n>=1.

Análisis :

Podemos analizar que tenemos el mismo número de a y b y en algún orden, es decir, primero vendrán todos los a y luego todos los b.

Ejemplo :

Input-1:aabb
Output-1:YES

Input-2:aabbbb
Output-2:NO

Input-3:abab
Output-3:NO

Acercarse :

Entendamos el enfoque tomando el ejemplo «aabb».

• Escanea la entrada desde la izquierda.
• Primero, reemplaza una ‘a’ con ‘X’ y muévete a la derecha. Luego omita todas las letras a y b y muévase a la derecha.
• Cuando el puntero llega a Blank(B), Blank permanecerá en Blank(B) y el puntero gira a la izquierda. Ahora escanea la entrada desde la derecha y reemplaza la primera ‘b’ con ‘Y’. Nuestra máquina de Turing se ve así:

• De nuevo, el puntero llega a Blank(B) o X. Ahora escanea la entrada de izquierda a derecha. El puntero se mueve hacia adelante y reemplaza ‘a’ con ‘X’.
• De nuevo, el puntero llega a Blank(B) o Y. Ahora escanea la entrada de derecha a izquierda. El puntero se mueve hacia adelante y reemplaza ‘b’ con ‘y’.
• Repetimos los mismos pasos hasta convertir todas las a en ‘X’ y las b en ‘Y’.
• Cuando todas las a se conviertan en ‘X y todas las b se conviertan en ‘Y’, nuestra máquina se detendrá.