A continuación se presentarán un conjunto de definiciones, y partes componentes que se utilizarán para definir al conjunto de máquinas.

Definiciones de propiedades comunes

En este apartado, se intenta realizar una aproximación al comportamiento general común a todas las máquinas, el cuál lo reflejan las definiciones siguientes:

• Tiempo discreto: en esencia significa que el tiempo avanza en unidades de tiempo considerados como intervalos de tiempo discretos, y que en cada uno de estos intervalos las máquinas se encontrarán en una configuración determinada, y realizan una acción determinada.

• Conjunto finito de estados: En un determinado intervalo de tiempo la máquina sólo se puede encontrar en uno y solo uno de los posibles estados.

• Alfabeto de Entrada: Los estímulos que la máquina recibe desde el exterior, pertenecen a un determinado conjunto denominado Alfabeto de Entrada.

• Cinta de entrada: La información que se recibe desde el  exterior será por medio de una cinta de entrada, los símbolos que pueden estar contenidos en esta cinta, pertenecen al Alfabeto de Entrada.

• Intencionalidad de la máquina: La funcionalidad para el cuál tiene propósito la máquina esta dada por su función de transición, que tiene como misión fundamental, dependiendo de la máquina, cual es el próximo estado al que debe pasar la máquina, dependiendo de estado actual y el estímulo (entrada) que recibe.

• Información hacia el exterior: En el caso que se tratase de una máquina traductora, devuelve información hacia el exterior, dependiendo de la máquina que se trate, tendrá una cinta especial en donde grabará la información de salida o tendrá la capacidad de regrabar la cinta única. 

Elementos constitutivos de las máquinas abstractas

A continuación se provee de la simbología y el significado que tendrá cada uno de los componentes  que serán utilizados en la descripción de las máquinas. 

 Definición y Representación

Cada una de las máquinas en lo que se refiere a su descripción, necesitará una enunciación formal de todos sus componentes, y además deberá describir la función de transición en todas las máquinas y adicionalmente la función de salida en el caso que se tratase de una máquina traductora secuencial.

Representaciones de la función de Transición

Básicamente existen tres formas de describir el funcionamiento de una máquina abstracta, y esta se puede realizar por medio de la declaración explícita de la función de transición, por medio de una tabla de doble entrada en donde básicamente se  representará el estado actual en que se encuentra la máquina, las entradas a producirse y el estado al cuál transitará, y por medio de un Grafo dirigido. Cada una de las representaciones respectivas serán equivalentes en cuanto a su definición, pero tendrán distinto grado de aceptación en cuanto su utilización.

Tabla de doble entrada

Básicamente esta forma de describir la función de transición permite una representación que facilita hacer el  seguimiento de la máquina a través de los sucesivos intervalos de tiempo por los cuales la máquina transitará e ira cambiando de estados en función a las sucesivas entradas que se produzcan.

La tabla, tendrá como mínimo la estructura que presentamos a continuación para todas las máquinas, pero diferirá de acuerdo a la máquina que se refiera, en la información que contendrá en la intersección de las filas y columnas. En las columnas se representarán las posibles entradas de acuerdo al alfabeto de entrada, mientras que el las filas se describirán los posibles estados de acuerdo al alfabeto de estados.

Detalle explícito función de transición

Esta forma de representar a la función de transición, si bien es efectiva es la que menos interés despierta ya que no facilita el seguimiento de máquina abstracta en su ejecución.

Como ejemplo de define:

En donde cada uno de los símbolos significa:

f        Función de Transición
p_i      Estado en el que se encuentra la máquina en un determinado tiempo i
e_i       Entrada a producirse en el tiempo i
q_i+1   Estado que se encontrará en tiempo  i+1

Grafo Dirijido

Este es la forma de representación mas expresiva, ya que al tratarse de una representación gráfica, facilita no solo evidenciar sus partes componentes y su función de transición, si no que permite hacer un seguimiento de la máquina abstracta en ejecución.
Las partes constitutivas del grafo serán las siguientes:

• Estados: Se representarán por medios de Nodos, los cuales se rotularán con el nombre del estado que represente

• Transiciones: Se representarán mediante arcos dirigidos, en donde el nodo donde arranca el arco representa el estado actual, el nodo a donde apunta el arco es el estado al cuál transitará  y el rótulo del arco nos indica la entrada que producirá tal transición o cambio de estado.

• Estado Inicial: Se representará mediante un nodo apuntado por una flecha 

• Estado Final: Es el estado que pertenece al subconjunto F, de estados finales de aceptación y se representará mediante un nodo con doble circulo.