Construya una máquina de Turing para L = {an bm a(n+m) | n,m≥1}

L = {un norte segundo ^metro un ( ^{n +m)} | n,m≥1} representa un tipo de lenguaje en el que usamos solo 2 caracteres, es decir, a y b. La primera parte del lenguaje puede ser cualquier número de «a» (al menos 1). La segunda parte puede ser cualquier número de “b” (al menos 1). La tercera parte del lenguaje es un número de «a» cuyo recuento es la suma del recuento de a en la primera parte de la string y el recuento de b en la segunda parte de la string. Cualquier string que caiga en esta categoría será aceptada por este idioma. El principio y el final de la string están marcados con el signo $.

Ejemplos:

Input  : a a b b b a a a a a  // n=2, m=3 
Output : Accepted

Input  : a a b a a a a       // n=2, m=1 
Output : Not accepted

Enfoque utilizado –

1. Convierta «a» en la primera parte en «X» y luego muévase hacia la derecha ignorando todos los símbolos intermedios. Cuando se encuentre «a» justo después de «b», conviértalo en «Z» y muévase hacia la izquierda y deténgase en la posición justo al lado de «X». Repita el procedimiento anterior.
2. Cuando todas las a en la primera parte se hayan convertido, aplique el mismo proceso en la segunda parte. Convierta «b» en «Y» y «a» en «Z» en la tercera parte.

Cuando se haya convertido la primera y la segunda parte completas y si también se convierte la tercera parte, se aceptará la string, de lo contrario no.

Pasos –

Paso 0: Convierta «a» en «X», muévase a la derecha y vaya al estado 1. Si el símbolo es «b», ignórelo, muévase a la derecha y vaya al estado 4.

Paso 1: si el símbolo es «a», ignórelo y muévase a la derecha, permanezca en el mismo estado. Si el símbolo es «b», ignórelo, muévase a la derecha y vaya al estado-2.

Paso 2: si el símbolo es «Z», ignórelo y muévase a la derecha, permanezca en el mismo estado. Si el símbolo es «b», ignórelo y muévase a la derecha, permanezca en el mismo estado y si el símbolo es «a», conviértalo en «Z», muévase a la izquierda y vaya al estado-3.

Paso 3: si el símbolo es «Z», ignórelo y muévase hacia la izquierda, permanezca en el mismo estado. Si el símbolo es «b», ignórelo y muévase a la izquierda, permanezca en el mismo estado. Si el símbolo es «a», ignórelo y muévase a la izquierda, permanezca en el mismo estado, y si el símbolo es «X», ignórelo y muévase a la derecha, vaya al estado-0.

Paso 4: si el símbolo es «b», ignórelo y muévase a la izquierda, vaya al estado 5, y si el símbolo es «Z», ignórelo y muévase a la izquierda, vaya al estado 5.

Paso 5: Convierta «b» en «Y», muévase a la derecha y vaya al estado 6, y si el símbolo es «Z», ignórelo y muévase a la derecha, vaya al estado 8.

Paso 6: si el símbolo es «Z», ignórelo y muévase a la derecha, permanezca en el mismo estado. Si el símbolo es «b», ignórelo y muévase a la derecha, permanezca en el mismo estado, y si el símbolo es «a», conviértalo en «Z», muévase a la izquierda y vaya al estado-7.

Paso 7: Si el símbolo es «Z», ignórelo y muévase hacia la izquierda, permanezca en el mismo estado. Si el símbolo es «b», ignórelo y muévase a la izquierda, permanezca en el mismo estado, y si el símbolo es «Y», ignórelo y muévase a la derecha, vaya al estado-5.

Paso 8: si el símbolo es «Z», ignórelo y muévase a la derecha, permanezca en el mismo estado, y si el símbolo es «$», ignórelo y muévase a la izquierda, vaya al estado-9.

Paso 9: String ACEPTADA