MT Generadora de L={ a^nb^2na^n, con n mayor o igual a 0}

Esta MT genera cadenas del lenguaje L={a^n b^2n a^n, con 0≤n}.

Para realizar esta MT, hemos utilizado una MT multicinta, en la que, en la primera cinta, pondremos  0's que equivaldrá a n y en la segunda cinta iremos almacenando la cadena resultante.

Situación inicial:

Cinta 1: ...qoBBBBB...

Cinta 2: ...qoBBBBB...

Salida:

Cinta 1: 000....

Cinta 2: lambda$abba$aabbbbaa$aaabbbbbbaaa$...

Funcionamiento:

En q0 ponemos lambda en la cinta de resultados. Pasamos a q5 encontrando [B,B] por lo que pondremos el separador $ en la cinta2 y pasamos al bucle que empieza en q1.

En q1 añade un 0 al principio de la cadena de la cinta 1, entonces pasa a q2 donde pone en la cinta 2 tantas a's como ceros haya en la cinta 1, es decir, n a's.

Entre q3 y q4 pone en la cinta 2, dos b's por cada 0 que hay en la cadena de la cinta 1. 

En q5 pone otra vez por cada cero de la cinta 1, una a en la cinta 2 y vuelva a q1 añadiendo el separador en la cinta 2 y volvemos a por el siguiente valor de n.

Es una MT bastante sencilla. Hemos elegido multicinta porque nos facilita mucho el trabajo, ya que mientras vamos recorriendo la cadena de 0's de la Cinta 1 vamos generando la cadena del lenguaje L.