Tabla de transición en autómatas

Tabla de transición: la
función de transición (∂) es una función que mapea Q * ∑ en Q. Aquí ‘Q’ es un conjunto de estados y ‘∑’ es una entrada de alfabetos. Para mostrar esta función de transición usamos una tabla llamada tabla de transición. La tabla toma dos valores, un estado y un símbolo, y devuelve el siguiente estado.

Una tabla de transición proporciona información sobre:

1. Las filas representan diferentes estados.
2. Las columnas representan símbolos de entrada.
3. Las entradas representan el siguiente estado diferente.
4. El estado final está representado por una estrella o círculo doble.
5. El estado de inicio siempre se indica con una pequeña flecha.

Ejemplo 1: 
este ejemplo muestra la tabla de transición para NFA (autómatas finitos no deterministas).

Explicación de la tabla anterior –

1. La primera columna indica todos los estados presentes, la siguiente para la entrada 0 y 1 respectivamente.
2. Cuando el estado actual es q0, para la entrada 0 el próximo estado será q0. Para la entrada 1, el siguiente estado es q1.
3. Cuando el estado actual es q1, para la entrada 0 el siguiente estado es q1 o q2, y para 1 entrada el siguiente estado es q2.
4. Cuando el estado actual es q2 para la entrada 0, el siguiente estado será q1, y para 1 entrada el siguiente estado será Nil.
5. La pequeña flecha recta en q0 indica que es un estado inicial y el círculo en q3 indica que es un estado final.

Ejemplo 2: 
este ejemplo muestra la tabla de transición de DFA (autómatas finitos deterministas).

Explicación de la tabla anterior –

1. La primera columna indica todos los estados presentes, la siguiente para la entrada 0 y 1 respectivamente.
2. Cuando el estado actual es q0, para la entrada 0, el siguiente estado será q1 y para la entrada 1, el siguiente estado será q1.
3. Cuando el estado actual es q1, para la entrada 0, el siguiente estado será q1, y en la entrada 1, el siguiente estado será q1.
4. La pequeña flecha recta en q0 indica que es un estado inicial y el círculo en q3 indica que es un estado final.

Ejemplo 3: 
este ejemplo muestra la tabla de transición de DFA (autómatas finitos deterministas)

Explicación de la tabla anterior –

1. La primera columna indica todos los estados presentes, la siguiente para la entrada 0 y 1 respectivamente.
2. Cuando el estado actual/presente es q0, para la entrada 0 el próximo estado será q0 y para la entrada 1 el próximo estado será q1.
3. Cuando el estado actual es q1, en la entrada 0, el siguiente estado será q2, y para 1 entrada, el siguiente estado será q1.
4. Cuando el estado actual es q2 para la entrada 0, el siguiente estado será q0, y para 1 entrada, el siguiente estado será q1.
5. La pequeña flecha recta en q0 indica que es un estado inicial y el círculo en q3 indica que es un estado final.

Ejemplo 4: este ejemplo muestra la tabla de transición para NFA (autómatas finitos no deterministas).  

Explicación de la tabla anterior –

1. La primera columna indica todos los estados presentes, Siguiente para la entrada 0 y 1 respectivamente.
2. Cuando el estado actual es q0, el siguiente estado de la entrada 0 será q0 o q1 y el siguiente estado de la entrada 1 será q0 o q2.
3. Cuando el estado actual es q1, para la entrada 0 el siguiente estado será q3, y para la entrada 1 el siguiente estado es Nil ya que no hay estado para la entrada 1.
4. Cuando el estado actual es q2 para la entrada 0, el siguiente estado será nulo ya que no hay estado para la entrada 0, y para 1 entrada, el siguiente estado será q3.
5. Cuando el estado actual es q3 para la entrada 0, el siguiente estado será nulo ya que no hay estado para la entrada 0, y para 1 entrada, el siguiente estado también será nulo ya que no hay estado para la entrada 1.
6. La pequeña flecha recta en q0 indica que es un estado inicial y el círculo en q3 indica que es un estado final.

Nota: Puede haber varios estados finales tanto en DFA como en NFA, pero el estado inicial es único.