Los Diagramas de Estados se usan para representar gráficamente máquinas de estados finitos. Las Tablas de Transiciones son otra posible representación.
Una forma clásica de un diagrama de estados para una máquina de estados finitos es un grafo dirigido con los siguientes elementos:
Estados Q: un conjunto finito de vertices representados normalmente por círculos y etiquetados con símbolos designadores únicos o palabras escritas dentro de ellos (Booth (1967) p. 69, Hopcroft y Ullman (1979) p. 16, Sipser (2006) p. 34).
Símbolos de Entrada Σ: una colección finita de "símbolos" de entrada o designadores Σ (Booth, Hopcroft y Ullman, Sipser). Para una Autómata finito (AFD), Máquina de Estados Finitos no Determinista (AFN), Máquina de Estados Finita no Determinista Generalizada (GNFA), o una Máquina de Moore, la entrada está significada en cada arista, normalmente cerca del estado originador. Para una Máquina de Mealy, la entrada y la salida están significados sobre cada arista normalmente separados con una barra "/":
las etiquetas de entrada y salida Mealy sobre cada arista (flecha): "1/0" designa que el símbolo "1" causó el símbolo "0" como salida.
Símbolos de Salida Z: una colección finita de "símbolos" de salida o designadores (Booth, Hopcroft y Ullman, Sipser). Para una Máquina de Mealy, la entrada y la salida están significados en cada arista como puede verse a continuación. Para una Máquina de Moore la salida del estado está escrita normalmente dentro del círculo del estado, separado del designador del estado con una barra "/".
Ejemplo: Si un estado tiene varias salidas el diagrama debe reflejar esto : e.g. "q5/1,0" designa que el estado q5 tiene salidas a=1, b=0. Este designador será escrito dentro del círculo del estado.
La "Función de Salida ω" representa el mapeado ω de símbolos de entrada I x estados Q en símbolos de salida Z (Booth).
Aristas δ: representa las "transiciones" entre dos estados causados por la entrada (identificados sus símbolos dibujados en los "aristas"). Un 'arista' está dibujado normalmente como una flecha dirigda desde el estado presente hacia el siguiente estado. δ representa el mapeado de los símbolos de entrada I x estados Q en los símbolos de salida Z (Booth, Hopcroft y Ullman, Sipser).
Estado inicial qo: (no visto en los ejemplos anteriores). El estado inicial qo está representado normalmente por una "flecha apuntándolo desde ninguna parte" (cf Sipser (2006) p. 34, Hopcroft y Ullman (1979) p. 16). En textos antiguos (e.g. Booth (1969), McCluskey (1965), Hill y Peterson (1974)) el estado inicial no se mostraba y era inferido del texto.
Estado(s) de Aceptación F: Si se usa -- una colección de círculos dobles usados para designar los estados de aceptación(Hopcroft y Ullman, Sipser). A veces la función de el/los estado/s de aceptación se entiende como estado/s"Final/es" (cf Hopcroft y Ullman (1979) Figure 2.15, p. 33).
Estados Q: un conjunto finito de vertices representados normalmente por círculos y etiquetados con símbolos designadores únicos o palabras escritas dentro de ellos (Booth (1967) p. 69, Hopcroft y Ullman (1979) p. 16, Sipser (2006) p. 34).
Símbolos de Entrada Σ: una colección finita de "símbolos" de entrada o designadores Σ (Booth, Hopcroft y Ullman, Sipser). Para una Autómata finito (AFD), Máquina de Estados Finitos no Determinista (AFN), Máquina de Estados Finita no Determinista Generalizada (GNFA), o una Máquina de Moore, la entrada está significada en cada arista, normalmente cerca del estado originador. Para una Máquina de Mealy, la entrada y la salida están significados sobre cada arista normalmente separados con una barra "/":
las etiquetas de entrada y salida Mealy sobre cada arista (flecha): "1/0" designa que el símbolo "1" causó el símbolo "0" como salida.
Símbolos de Salida Z: una colección finita de "símbolos" de salida o designadores (Booth, Hopcroft y Ullman, Sipser). Para una Máquina de Mealy, la entrada y la salida están significados en cada arista como puede verse a continuación. Para una Máquina de Moore la salida del estado está escrita normalmente dentro del círculo del estado, separado del designador del estado con una barra "/".
Ejemplo: Si un estado tiene varias salidas el diagrama debe reflejar esto : e.g. "q5/1,0" designa que el estado q5 tiene salidas a=1, b=0. Este designador será escrito dentro del círculo del estado.
La "Función de Salida ω" representa el mapeado ω de símbolos de entrada I x estados Q en símbolos de salida Z (Booth).
Aristas δ: representa las "transiciones" entre dos estados causados por la entrada (identificados sus símbolos dibujados en los "aristas"). Un 'arista' está dibujado normalmente como una flecha dirigda desde el estado presente hacia el siguiente estado. δ representa el mapeado de los símbolos de entrada I x estados Q en los símbolos de salida Z (Booth, Hopcroft y Ullman, Sipser).
Estado inicial qo: (no visto en los ejemplos anteriores). El estado inicial qo está representado normalmente por una "flecha apuntándolo desde ninguna parte" (cf Sipser (2006) p. 34, Hopcroft y Ullman (1979) p. 16). En textos antiguos (e.g. Booth (1969), McCluskey (1965), Hill y Peterson (1974)) el estado inicial no se mostraba y era inferido del texto.
Estado(s) de Aceptación F: Si se usa -- una colección de círculos dobles usados para designar los estados de aceptación(Hopcroft y Ullman, Sipser). A veces la función de el/los estado/s de aceptación se entiende como estado/s"Final/es" (cf Hopcroft y Ullman (1979) Figure 2.15, p. 33).
No hay comentarios:
Publicar un comentario