¿Qué es una máquina de Post?
Una máquina de Post es una máquina abstracta que consiste en un conjunto de estados (incluyendo el estado inicial), un conjunto de eventos de entrada, un conjunto de eventos de salida, y una función de transición.
¿Qué es una máquina abstracta?
1. Un diseño de procesador el cual no puede intentarse implementar como hardware, pero que es un instintivo ejecutor de un lenguaje intermedio concreto (lenguaje de la máquina abstracta) usado en un compilador o intérprete. Una máquina abstracta es un conjunto de instrucciones, un conjunto de registros y un modelo de memoria. Puede proporcionar instrucciones, las cuales son pertenecientes a un lenguaje compilado por una computadora real o puede ser usada para hacer la implementación del lenguaje más fácil que en otros soportes.
2. Un procedimiento para ejecutar un conjunto de instrucciones en algún lenguaje formal, asimismo posiblemente presente en los datros de entrada y produciendo salidas. Sabemos que no es factible construir una máquina abstracta como algo físico, pero son usadas en muchos experimentos sobre computabilidad.
¿Qué hace una máquina de Post? ¿Cómo lo hace?
Una máquina de Post incorpora los estados (instrucciones) START, STORE, ACCEPT, REJECT, READ y ADD, y dada una palabra (WORD) definida por un alfabeto (ALPHABET), la introduce en la máquina y la analiza mediante los estados citados.
El estado START es activado automáticamente al iniciar la máquina. El estado STORE, imaginada como una cola, dada la palabra, la mantiene en un bucle, como si estuviera almacenada en la memoria. Entonces es posible actuar sobre el dato, si fuera necesario, incorporando el estado READ o ADD, de modo que el dato siempre mantenga la línea definida por el usuario.
Una palabra es una concatenación de elementos del alfabeto. En un simple ejemplo, examinemos la palabra de la forma {anbn}, 'aaabbb' cuyo alfabeto es desde luego 'a' y 'b'. Para hacer más fácil la tarea disponemos de diagramas de cómo la máquina de Post trabaja.
La máquina de Post comienza (START) evaluando la palabra almacenándola en STORE. Acto seguido, añade el carácter '#' (este carácter es como una bandera para la máquina) a la palabra, y otra vez es puesta en STORE. Como se puede observar, no hay un estado REJECT explícito dibujado en la figura. Esto se debe a que es empleado cuando una palabra es leída y no se puede sacar nada en el estado READ, es rechazada (REJECT) y la máquina cesa.
La primera 'a' es leída, entonces se mueve al segundo estado READ, el cual como se observa, entra en un bucle. Este 'bucle' añade (ADD) y lee (READ) todas las 'a's que estaban en STORE (después de leer la primera 'a'). El efecto de esta acción es que la maquina sitúa una 'a' menos en la cola de las que había originalmente en la palabra. Esta acción es repetida para las 'b's. Después de que todas las 'a's y las 'b's hayan sido leídas y se llega al carácter '#', nos situamos al principio del programa, la máquina vuelve y se añade el carácter '#' a la cola. De repente, volvemos donde empezamos, pero con un conjunto menos de los elementos del alfabeto (a y b) en la cola. Esta acción de eliminar un conjunto de 'a y b' nos dejará con un único carácter '#' en STORE y cuando lo ejecutamos otra vez, la máquina aceptará la palabra en una de las especificaciones del diagrama (WORD).
Inserte palabra o 'N' para la cadena vacía o '*' para desactivar la máquina: aaabbb
State = 1 START Tape = aaabbb Store = NULL
State = 2 READ Tape = aabbb Store = NULL
State = 3 STORE Tape = aabbb Store = A
State = 4 READ Tape = abbb Store = A
State = 3 STORE Tape = abbb Store = AA
State = 4 READ Tape = bbb Store = AA
State = 3 STORE Tape = bbb Store = AAA
State = 4 READ Tape = bb Store = AAA
State = 5 CONSULT Tape = bb Store = AA
State = 6 READ Tape = b Store = AA
State = 5 CONSULT Tape = b Store = A
State = 6 READ Tape = NULL Store = A
State = 5 CONSULT Tape = NULL Store = NULL
State = 6 READ Tape = NULL Store = NULL
State = 7 CONSULT Tape = NULL Store = NULL
State = 8 ACCEPT