Construya la Máquina de Turing para L = {a^ib^j | i<j, i>0}

Prerrequisito – Máquina de Turing

Tarea:
Tenemos que diseñar una máquina de Turing para a^ib^j donde i<j e i>0.

Análisis :
Aquí lo principal es notar que i<j. Significa que el conteo de ‘b’ en la string siempre es mayor que el conteo de ‘a’. Por lo tanto podemos escribir a^ib^j así –

a^i b^j = a^n b^n + extra number of b.

Ejemplos –

Input: aabbbb
Output: Accepted

Input: aaabb
Output: Not Accepted

Enfoque:
Entendamos el enfoque tomando una string «aabbb».

1. Escanea la entrada desde la izquierda.
2. Primero, reemplaza una ‘a’ con ‘X’ y muévete 1 paso a la derecha. Luego omita todas las letras a y b y muévase a la derecha.
3. Cuando el puntero llega a Blank(B), escanea la entrada desde la derecha y reemplaza la primera ‘b’ con ‘Y’.

   

4. De nuevo, el puntero llega a Blank(B). Ahora escanea la entrada de izquierda a derecha. El puntero se mueve hacia adelante y reemplaza ‘a’ con ‘X’.
5. De nuevo, el puntero llega a Blank(B). Ahora escanea la entrada de derecha a izquierda. El puntero se mueve hacia adelante y reemplaza ‘b’ con ‘y’.
6. Repetimos los mismos pasos hasta convertir todas las a en ‘X’. b igual a la cuenta de a también se convertirá en ‘Y’ y nos quedarán algunas de las b restantes.