Construya una máquina de Turing para el lenguaje L = {a^nb^mc^nm donde n >=0 y m >= 0}

Prerrequisito – Máquina de Turing El lenguaje L = {a ⁿ b ^m c ^nm | n >= 0 andm>=0} representa un tipo de lenguaje donde usamos solo 3 símbolos, es decir, a, b y c. Al principio, el lenguaje tiene un número n de a seguido de un número m de b y luego un número n*m de c. Cualquier string que caiga en esta categoría será aceptada por este idioma. 

Ejemplos:

Input : abbcc
Output : YES

Input : abbbcc
Output : NO

Input :  or empty stringOutput : 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 a y al principio solo lo dejaremos en blanco. Luego, atravesaremos para hacer ba $más a la izquierda y reemplazaremos c más a la derecha por un espacio en blanco, haremos este patrón de zigzag de reemplazar b por $y c por espacio en blanco hasta que todos los b no sean reemplazados por $. Después de esto, volveremos a cruzar en dirección izquierda hasta que obtengamos a a la izquierda y reemplacemos todo $por b en el recorrido. Después de esto, hemos reducido nuestra string a la forma ^n-1 b ^m c ^nm-m para que podamos calcular si todas las a se reemplazan por espacios en blanco y si la string pertenece al idioma L, entonces no quedarán c, por lo que será aceptado.

  

Significados de los símbolos utilizados: R, L – dirección de movimiento de una unidad a cada lado. B-Blank, a, b, c -símbolos cuya string de combinación se va a probar. $-Símbolo temporal para reemplazar b. 

Procedimiento de trabajo :

• Paso 1: primero reemplazamos la a de la izquierda por un espacio en blanco y luego recorremos para reemplazar la b de la izquierda por $y la c de la derecha por un espacio en blanco. Repita este paso desde el estado Q1 hasta que no quede más b.
• Paso 2: Después de reemplazar todo b por $, también hemos reemplazado m c’s más a la derecha con espacios en blanco y luego volveremos a la izquierda más a y reemplazaremos todos $por b’s. Después de este paso, si verifica la string, ahora se reduce a una ^{n -1} b ^m c ^nm-m forma. Ahora repetiremos desde el paso 1 hasta que no queden todas las a en blanco.
• Paso 3: Entonces, después de que todas las a se dejen en blanco y si la string pertenecía al idioma L, entonces se deben dejar 0 c, que verificamos en el estado Q0 y Q6, ya que solo quedarán b y después de lo cual si se encuentra en blanco, entonces todas las c deben han sido reemplazados por Blank ya que estábamos haciendo c’s Blank desde el extremo derecho de la string.
• Paso 4: Entonces, si obtenemos un símbolo en blanco en el estado Q6, la string se acepta en el estado final Q7. Además, si la string estaba vacía, también se aceptará como entrada de símbolo en blanco en el estado Q0, luego llegará al estado Q7 y se aceptará.