14.4: El monoide de una máquina de estado finito

En esta sección, veremos cómo cada máquina de estado finito tiene un monoide asociado a ella. Para cualquier máquina de estado finito, los elementos de su monoide asociado corresponden a ciertas secuencias de entrada. Debido a que solo es posible un número finito de combinaciones de estados y entradas para una máquina de estado finito, solo hay un número finito de secuencias de entrada que resumen la máquina. Esta idea se ilustra mejor con algunos ejemplos.

Considera el verificador de paridad. La siguiente tabla resume el efecto sobre el verificador de paridad de cadenas en\(B^1\) y\(B^2\text{.}\) La fila etiquetada “Even” contiene el estado final y la salida final como resultado de cada cadena de entrada en\(B^1\) y\(B^2\) cuando la máquina comienza en el estado par. Del mismo modo, la fila etiquetada como “Odd” contiene la misma información para las secuencias de entrada cuando la máquina inicia en el estado impar.

\ begin {ecuación*}\ begin {array} {c|cccccc}\ textrm {Entrada}\ textrm {String} & 0 & 1 & 00 & 01 & 10 & 11\\ hline\ textrm {par} & (\ textrm {par} ,0) & (\ textrm {impar} ,1) & (\ textrm {par} ,0) & (\ textrm {par} ,0) & (\ textrm {par} ,0) & (\ textrm {Impares} ,1) & (\ textrm {Impares} ,1) & (\ textrm {Par} ,0)\\\ textrm {Impares } & (\ textrm {Impares} ,1) & (\ textrm {Par} ,1) & (\ textrm {Impares} ,1) & (\ textrm {Par} ,1) & (\ textrm {Par} ,0) & (\ textrm {Impares} ,1)\\\ textrm {Igual}\ textrm {Efecto}\ textrm {como} & & 0 y 1 y 0\\\ end {array}\ end {ecuación*}

Observe cómo, como se indica en la última fila, las cadenas en\(B^2\) tienen el mismo efecto que ciertas cadenas en\(B^1\text{.}\) Por esta razón, podemos resumir la máquina en términos de cómo se ve afectada por cadenas de longitud 1. El monoide real que ahora describiremos consiste en un conjunto de funciones, y la operación sobre las funciones se basará en la operación de concatenación.

Dejar\(T_0\) ser el efecto final (estado y salida) sobre el verificador de paridad de la entrada 0. De igual manera,\(T_1\) se define como el efecto final sobre el verificador de paridad de la entrada 1. Más precisamente,

\ begin {ecuación*} T_0 (\ textrm {par}) = (\ textrm {par} ,0)\ cuádruple\ textrm {y}\ quad T_0 (\ textrm {impar}) = (\ textrm {impar} ,1)\ textrm {,}\ final {ecuación*}

mientras

\ begin {ecuación*} T_1 (\ textrm {par}) = (\ textrm {impar} ,1)\ quad\ textrm {y}\ quad T_1 (\ textrm {impar}) = (\ textrm {par} ,0)\ textrm {.} \ end {ecuación*}

En general, definimos la operación sobre un conjunto de tales funciones de la siguiente manera: si\(s\text{,}\)\(t\) son secuencias de entrada\(T_s\) y y\(T_t\text{,}\) son funciones como las anteriores, entonces es\(T_s*T_t=T_{st}\text{,}\) decir, el resultado de la función que resume el efecto en la máquina por la concatenación de\(s\) con \(t\text{.}\)Ya que, por ejemplo, 01 tiene el mismo efecto en el verificador de paridad\(T_0*T_1=T_{01}=T_1\text{.}\) que 1, no paramos nuestro cálculo en\(T_{01}\) porque queremos usar la cadena más corta de entradas para describir el resultado final. Una tabla completa para el monoide del verificador de paridad es\(\begin{array}{c|c} * & \begin{array}{cc} T_0 & T_1 \\ \end{array} \\ \hline \begin{array}{c} T_0 \\ T_1 \\ \end{array} & \begin{array}{cc} T_0 & T_1 \\ T_1 & T_0 \\ \end{array} \\ \end{array}\)

¿Cuál es la identidad de este monoide? El monoide del verificador de paridad es isomórfico al monoide\(\left[\mathbb{Z}_2; +_2\right]\text{.}\)

Esta operación puede recordarle la operación de composición en funciones, pero hay dos diferencias principales. El dominio de no\(T_s\) es el codominio de\(T_t\) y las funciones se leen de izquierda a derecha a diferencia de la composición, donde normalmente se leen de derecha a izquierda.

Es posible que hayas notado que la salida del verificador de paridad se hace eco del estado de la máquina y que solo podríamos haber mirado el efecto en la máquina como estado final. El siguiente ejemplo tiene la misma propiedad, de ahí que solo consideraremos el estado final.

Ejemplo\(\PageIndex{1}\)

El diagrama de transición para la máquina que reconoce cadenas en las\(B*\) que no tienen 1 consecutivos aparece en la Figura\(\PageIndex{1}\). Observe cómo es similar a la gráfica de la Figura 9.1.1. Sólo se ha agregado un “estado de rechazo”, para el caso cuando ocurre una entrada de 1 mientras en Estado\(a\text{.}\) Construimos una tabla similar a la del ejemplo anterior para estudiar el efecto de ciertas cadenas en esta máquina. Esta vez, debemos incluir cadenas de longitud 3 antes de reconocer que no se pueden encontrar “nuevos efectos”.

Figura\(\PageIndex{1}\): No hay monoides consecutivos

\(\begin{array}{ccccccccccccccc} \textrm{ Inputs} & 0 & 1 & 00 & 01 & 10 & 11 & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\ s & b & a & b & a & b & r & b & a & b & r & b & a & r & r \\ a & b & r & b & a & r & r & b & a & b & r & r & r & r & r \\ b & b & a & b & a & b & r & b & a & b & r & b & a & r & r \\ r & r & r & r & r & r & r & r & r & r & r & r & r & r & r \\ \textrm{ Same} \textrm{ as} & & & 0 & & & & 0 & 01 & 0 & 11 & 10 & 1 & 11 & 11 \\ \end{array}\)

La siguiente tabla resume cómo las combinaciones de las cadenas\(0,1,01,10, \textrm{ and } 11\) afectan a esta máquina.

\ begin {ecuation*}\ begin {array} {c|c} * &\ begin {array} {ccccc} T_0 & T_1 & T_ {01} & T_ {10} & T_ {11}\\\ end {array}\\ hline\ begin {array} {c} T_0\\ T_1\ T_ {01}\\ T_ {10}\ T_ _ {11}\\\ end {array} &\ begin {array} {ccccc} T_0 & T_1 & T_ {01} & T_ {10} & T_ {11}\\ T_ {10} & T _ {11} y T_ 1 y T_ {11} y T_ {11}\ T_ 0 y T_ {11} y T_ {01} y T_ {11} y T_ {11}\ T_ {10} y T_ 1 y T_ {10} y T_ {11} y T_ {11} y T_ {11} y T_ {11} y T_ {11} y T_ {11} & T_ {11}\\\ end {array}\\\ end {array}\ end {ecuación*}

Todos los resultados de esta tabla se pueden obtener utilizando la tabla anterior. Por ejemplo,

\ begin {ecuación*}\ begin {array} {c} T_ {10} *T_ {01} =T_ {1001} =T_ {100} *T_1=T_ {10} *T_1=T_ {101} =T_1\\ textrm {y}\\ T_ {01} *T_ {01} =T_ {0101} =T_ {010} T_1=T_0T_1=T_ {01}\\\ end {array}\ end {ecuación*}

Tenga en cuenta que ninguno de los elementos que hemos enumerado en esta tabla sirve como identidad para nuestra operación. Este problema siempre se puede remediar incluyendo la función que corresponde a la entrada de la cadena nula,\(T_{\lambda }\text{.}\) Dado que la cadena nula es la identidad para la concatenación de cadenas,\(T_sT_{\lambda }=T_{\lambda }T_s=T_s\) para todas las cadenas de entrada\(s\text{.}\)

Ejemplo \(\PageIndex{2}\): The Unit-Time Delay Machine

Una máquina de estado finito llamada máquina de retardo de tiempo unitario no hace eco de su estado actual, sino que imprime su estado anterior. Por esta razón, cuando encontramos el monoide de la máquina de retardo de tiempo unitario, debemos considerar tanto el estado como la salida. El diagrama de transición de esta máquina aparece en la Figura\(\PageIndex{2}\).

Figura\(\PageIndex{2}\)

\(\begin{array}{c|c} \textrm{ Input} & \begin{array}{cccccccccc} & \begin{array}{cc} 0 & 1 \\ \end{array} & 00\textrm{ } & 01\textrm{ } & \textrm{ }10\textrm{ } & 11 & 100\textrm{ or}000\textrm{ } & 101\textrm{ or}001 & 110\textrm{ or}101 & 111\textrm{ or}011 \\ \end{array} \\ \hline \begin{array}{c} 0 \\ 1 \\ \textrm{ Same} \textrm{ as} \\ \end{array} & \begin{array}{cccccccccc} (0,0) & (1,0) & (0,0) & (1,0) & (0,1) & (1,1) & (0,0) & (1,0) & (0,1) & (1,1) \\ (0,1) & (1,1) & (0,0) & (1,0) & (0,1) & (1,1) & (0,0) & (1,0) & (0,1) & (1,1) \\ & & & & & & 00 & 01 & 10 & 11 \\ \end{array} \\ \end{array}\)

Nuevamente, dado que no se obtuvieron nuevos resultados de cadenas de longitud 3, solo cadenas de longitud 2 o menos contribuyen al monoide de la máquina. La tabla para las cadenas de longitud positiva muestra que debemos agregar\(T_{\lambda }\) para obtener un monoide.

\ begin {ecuation*}\ begin {array} {c|c} * &\ begin {array} {cccccc} T_0 & T_1 & T_ {00} & T_ {01} & T_ {10} & T_ {11}\\ end {array}\\ hline\ begin {matriz} {c} T_0\\ T_1\\ T_ {00}\ T_ _ {01}\\ T_ {10}\\ T_ {11}\\\ end {array} &\ begin {array} {cccccc} T_ {00} & T_ {01} & T_ {00} & T_ {01} & T_ {10} & T_ {11}\ T_ {10} & T_ {11} & T_ {00} & T_ {01} & T_ {10} & T_ {11}\ T_ {00} & T_ {01} & T_ {00} & T_ {01} & T_ {01} & T_ {10} & T_ {11}\ T_ {10} & T_ {10} & T_ {10} & T_ {11} y T_ {00} y T_ {01} y T_ {10} y T_ {11}\\ T_ {00} y T_ {01} y T_ {00} y T_ {01} y T_ {10} y amp; T_ {11}\\ T_ {10} & T_ {11} & T_ {00} & T_ {01} & T_ {10} & T_ {11}\\ final {matriz}\\ final {matriz}\ texto {.} \ end {ecuación*}

14.4.1: Ejercicios

Ejercicio\(\PageIndex{1}\)

Para cada uno de los diagramas de transición de la Figura\(\PageIndex{3}\), escriba tablas para sus monoides asociados. Identificar la identidad en términos de una cadena de longitud positiva, si es posible.

Figura\(\PageIndex{3}\): Ejercicio\(\PageIndex{3}\)

Pista

Donde la salida hace eco del estado actual, la salida puede ser ignorada.

Contestar

1. \(\begin{array}{c|cccccc} \textrm{ Input String} & a & b & c & aa & ab & ac \\ \hline 1 & (a,1) & (a,2) & (c,3) & (a,1) & (a,2) & (c,3) \\ 2 & (a,2) & (a,1) & (c,3) & (a,2) & (a,1) & (c,3) \\ 3 & (c,3) & (c,3) & (c,3) & (c,3) & (c,3) & (c,3) \\ \end{array}\)\(\begin{array}{c|cccccc} \textrm{ Input String} & ba & bb & bc & ca & cb & cc \\ \hline 1 & (a,2) & (a,1) & (c,3) & (c,3) & (c,3) & (c,3) \\ 2 & (a,1) & (a,2) & (c,3) & (c,3) & (c,3) & (c,3) \\ 3 & (c,3) & (c,3) & (c,3) & (c,3) & (c,3) & (c,3) \\ \end{array}\)
   Podemos ver eso\(T_aT_a=T_{\text{aa}}=T_a,\: T_aT_b=T_{\text{ab}}=T_b\), etc. Por lo tanto, tenemos el siguiente monoide:
   \ begin {ecuation*}\ begin {array} {c|c} &\ begin {array} {ccc} T_ {a} & T_b & T_b\\ end {array}\\ hline\ begin {array} {c} T_a\\ t_B\\ t_C\\ end {array} & \ begin {array} {ccc} T_a & T_b & T_c\\ T_b & T_a & T_c\\ T_c & T_c & T_c\\ end {array}\\ end {array}\ end {equation*}
   Observe que\(T_a\) es la identidad de este monoide.
2. \(\begin{array}{c|cccccc} \textrm{Input String} & 1 & 2 & 11 & 12 & 21 & 22 \\ \hline A & C & B & A & D & D & A \\ B & D & A & B & C & C & B \\ C & A & D & C & B & B & C \\ D & B & C & D & A & A & D \\ \end{array}\)
   \(\begin{array}{c|cccccccc} \textrm{Input String} &111 & 112 & 121 & 122 & 211 & 212 & 221 & 222 \\ \hline A & C & B & B & C & B & C & C & B \\ B & D & A & A & D & A & D & D & A \\ C & B & C & C & B & C & B & B & C \\ D & B & C & C & B & C & B & B & C \\ \end{array}\)
   Tenemos el siguiente monoide:
   \ begin {ecuation*}\ begin {array} {c|c} &\ begin {array} {cccc} T_1 & T_2 & T_ {11} & T_ {12}\\\ end {array}\\ hline\ begin {array} {c} T_1\\ T_2\\ T_ {11}\\ T_ {12}\\ end {array} &\ begin {array} {cccc} T_ {11} & T_ {12} & T_ 1 & T_2\\ T_b & T_ {11} & T_2 & T_2 & T_1\\ T_2 & T_ {11} & T_ {12}\ T_2 y T_1 & T_ {12} & T_ {11}\\ end {array}\\ end {array}\\ end {array}\\ end {array}}\ end {equation*}
   Observe que\(T_{11}\) es la identidad de este monoide.

Ejercicio\(\PageIndex{2}\)

¿Qué monoides comunes son isomórficos a los monoides obtenidos en el ejercicio anterior?

Ejercicio\(\PageIndex{3}\)

¿Pueden dos máquinas de estado finito con diagramas de transición no isomórficos tener monoides isomórficos?

Contestar

Sí, solo considera la máquina de retardo de tiempo de la unidad de la Figura\(\PageIndex{2}\). Su monoide es descrito por la tabla al final de la Sección 14.4 donde se omiten la\(T_{λ}\) fila y la\(T_{λ}\) columna. A continuación considere la máquina en la Figura 14.5.3. El monoide de esta máquina es:

\ begin {ecuation*}
\ begin {array} {c|ccccccc}
& T_ {\ lambda} & T_0 & T_1 & T_ {00} & T_ {01} & T_ {10} & T_ {11}\\ hline T_ {
\ lambda} &
T_ {\ lambda} & T_ {\ lambda} & T_0 & T_ 1 & T_ {00} & T_ {01} & T_ _ {10} & amp; T_ {11}\
\ hline
T_0 & T_ {00} & T_ {00} & T_ {01} & T_ {00} & T_ {01} & T_ {10} & T_ {11}\\
T_1 & T_ {10} & T_ {11} & T_ {00} & T_ {01} & T_ {10} & T_ {11}\\
T_ {00} y T_ {00} & T_ {00} y T_ {01} y T_ {00} y T_ {01} y T_ {10} y T_ {11}\ T_ {01} y
T_ {01} y T_ {10} y T_ {11} y T_ {00} y T_ {01} y T_ {10} y T_ {11}\ T_ {10} y T_ {10} y
T_ {10} y T_ {10} {10} y T_ {00} y T_ {01} y T_ {00} y T_ {01} y T_ {10} y T_ {11}\ \
T_ {11} & T_ {11} & T_ {10} & T_ {11} & T_ {00} & T_ {01} & T_ {10} & T_ {11}\
\ final {matriz}
\ final {ecuación*}

De ahí que ambas máquinas tengan el mismo monoide, sin embargo, sus diagramas de transición son no isomórficos ya que la primera tiene dos vértices y la segunda tiene siete.