La tabla de transición es básicamente una representación tabular de la función de transición. Toma dos argumentos (un estado y un símbolo) y devuelve un estado (el 'siguiente estado').
Una tabla de transición está representada por lo siguiente:
- Las columnas corresponden a símbolos de entrada.
- Las filas corresponden a los estados.
- Las entradas corresponden al siguiente estado.
- El estado inicial se indica con una flecha sin fuente.
- El estado de aceptación se indica con una estrella.
Ejemplo 1:
Solución:
La tabla de transición de DFA dado es la siguiente:
si no java
| Estado actual | Siguiente estado para la entrada 0 | Siguiente estado de la entrada 1 |
|---|---|---|
| →q0 | q1 | q2 |
| q1 | q0 | q2 |
| *q2 | q2 | q2 |
Explicación:
- En la tabla anterior, la primera columna indica todos los estados actuales. En las columnas 0 y 1, se muestran los siguientes estados.
- La primera fila de la tabla de transición se puede leer como, cuando el estado actual es q0, en la entrada 0 el siguiente estado será q1 y en la entrada 1 el siguiente estado será q2.
- En la segunda fila, cuando el estado actual es q1, en la entrada 0, el siguiente estado será q0, y en la entrada 1, el siguiente estado será q2.
- En la tercera fila, cuando el estado actual es q2 en la entrada 0, el siguiente estado será q2 y en la entrada 1 el siguiente estado será q2.
- La flecha marcada con q0 indica que es un estado inicial y el círculo marcado con q2 indica que es un estado final.
Ejemplo 2:
Solución:
La tabla de transición de NFA dada es la siguiente:
| Estado actual | Siguiente estado para la entrada 0 | Siguiente estado de la entrada 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q1, q2 | q2 |
| q2 | q1 | q3 |
| *q3 | q2 | q2 |
Explicación:
cadena de entrada java
- La primera fila de la tabla de transición se puede leer como, cuando el estado actual es q0, en la entrada 0 el siguiente estado será q0 y en la entrada 1 el siguiente estado será q1.
- En la segunda fila, cuando el estado actual es q1, en la entrada 0 el siguiente estado será q1 o q2, y en la entrada 1 el siguiente estado será q2.
- En la tercera fila, cuando el estado actual es q2 en la entrada 0, el siguiente estado será q1 y en la entrada 1 el siguiente estado será q3.
- En la cuarta fila, cuando el estado actual es q3 en la entrada 0, el siguiente estado será q2 y en la entrada 1 el siguiente estado será q2.