Palabras que tienen el mismo producto asociativo derecho e izquierdo

He comenzado a estudiar autómatas no deterministas utilizando el libro de Hopcroft y Ullman . Estoy atrapado en un problema que me pareció muy interesante:

Dé un autómata finito no determinista que acepte todas las cadenas que tienen el mismo valor cuando se evalúan de izquierda a derecha como de derecha a izquierda al multiplicar de acuerdo con la siguiente tabla:

$\qquad \displaystyle\begin{array}{c|ccc} \times & a & b & c \\ \hline a & a & a & c \\ b & c & a & b \\ c & b & c &a \end{array}$

Entonces, si tenemos la cadena , el producto de izquierda a derecha es ( a × b ) × c = a × c = c y el producto de derecha a izquierda es a × ( b × c ) = a × b = $abc$
$(a \times b) \times c=a \times c=c$
$a \times (b \times c)=a \times b=a$

Entonces no debería ser aceptable para los autómatas. Para mí es obvio que cualquier cadena a a ∗ o b b ∗ o c c ∗ es una cadena aceptable (su evaluación derecha e izquierda funciona en las mismas cadenas parciales). Es fácil dar un NFA que describa la evaluación de izquierda a derecha, pero el problema es que si la máquina intenta calcular la evaluación de derecha a izquierda , creo que necesita saber la longitud de la cadena (por lo que es necesaria una memoria infinita).$abc$$aa^*$$bb^*$$cc^*$

Entonces, ¿cómo puede un autómata no determinista evaluar de derecha a izquierda para comparar con la evaluación de izquierda a derecha?

El primer truco aquí es pensar en la tabla de multiplicar como la tabla de transición de un autómata con cada estado representando una letra en su tabla de multiplicar, pero sin preocuparse aún por la aceptación. Entonces, las letras a la izquierda y en el cuerpo de la tabla son en realidad estados: sería más exacto escribirlas como q a , q b , q c , pero no lo haré. Las letras en la parte superior son entradas.$A$$q_a, q_b, q_c$

Luego construya el autómata (" T " para transposición) para la multiplicación inversa transponiendo A :$A_T$$T$$A$

$\qquad \displaystyle\begin{array}{c|ccc} A_T & a & b & c \\ \hline a & a & c & b \\ b & a & a & c \\ c & c & b & a \end{array}$

Entonces te lleva al estado c , y de la misma manera A T ( c b a ) se mueve al estado a de A T , como notas.$A(abc)$$c$$A_T(cba)$$a$$A_T$

Sin embargo, asume que vas de derecha a izquierda, y aún queremos ir de izquierda a derecha. Entonces, el segundo truco es revertir el autómata (no la multiplicación, que simplemente nos recuperaría si empezáramos), invirtiendo todas las flechas, lo que conduce a un autómata no determinista A T R dado por la tabla de transición a continuación, con subconjuntos indicados por letras concatenadas para mantener al pollo rascando, por lo que a c es realmente { a , c } . (Espero haberlo hecho bien, parece funcionar).$A_T$$A_{TR}$$ac$$\{a,c\}$

$\qquad \displaystyle\begin{array}{c|ccc} A_{TR} & a & b & c \\ \hline a & ab & b & c \\ b & ∅ & c & a \\ c & c & a & b \\ \hline ab & ab & bc & ac \\ bc & c & ac & abc \\ ac & abc & ab & bc \\ abc & abc & abc & abc \\ ∅ & ∅ & ∅ & ∅ \end{array}$

Puede interpretar esto como un autómata no determinista con solo las tres filas por encima de la línea o una versión determinada con las 8 filas.

Finalmente, la máquina para resolver el problema es el autómata multiproducto de y A T R originales , es decir A × A T R para realizar el comportamiento de intersección de los dos autómatas (ya no necesitamos A T ) . A × A T R tiene estados que son pares como ⟨ una , una c ⟩ . La función de transición ejecuta A y A T R independientemente. Un solo estado de inicio ⟨ 1 , 1 $A$$A_{TR}$$A \times A_{TR}$$A_T$$A \times A_{TR}$$\langle a,ac\rangle$$A$$A_{TR}$$\langle 1,1 \rangle$entra en bajo entrada de una , en ⟨ b , b ⟩ bajo de entrada b , etc. $\langle a,a \rangle$$a$$\langle b,b \rangle$$b$

La aceptación de los estados en la versión no determinista se etc. En la versión determinista, aceptando estados son parejas en las que el primer componente es ∈ del segundo conjunto de componentes, tales como ⟨ una , una ⟩ o ⟨ b , b c ⟩ .$\langle a,a \rangle$$\in$$\langle a,a \rangle$$\langle b,bc \rangle$

aumentada y determinada como se muestra tiene 25 = 3 ⋅ 8 + 1 estados, así que perdóname si no lo escribo en detalle. Pero la versión no determinista tiene solo 10 = 3 ⋅ 3 + 1 estados.$A \times A_{TR}$$25=3\cdot 8+1$$10=3\cdot 3+1$

Si L es un lenguaje regular, entonces L R , el lenguaje que consiste en elreversode todas las palabras en L , también es regular. Toma esto como un ejercicio.$(\ast)$$L$$L^R$$L$

$L_a,L_b,L_c$$a,b,c$

$(\ast)$$L_a^R$$a$

$b$$b$$bx = a$$x = b$$c$$a$$a$$b$

Esta pista debería darle suficiente para pensar y, con suerte, resolver el problema.

Lindo.

$\overrightarrow x \xrightarrow{\;y\;} \overrightarrow z$$x \cdot y = z$$\{\overrightarrow a,\overrightarrow b,\overrightarrow c\}$$\overrightarrow 1$$\overrightarrow 1 \xrightarrow{\;x\;} \overrightarrow x$$x$$\overrightarrow x$$x$

Ahora construyamos un autómata que calcule el producto de derecha a izquierda. Este será no determinista. ¿Como hacemos eso? Simple ... Para ir en la otra dirección, simplemente invierta todo : las flechas y la dirección del producto.

$\overrightarrow{x} \xrightarrow{\;y\;} \overrightarrow{x \cdot y\:}$$\overleftarrow{x \cdot y\:} \xleftarrow{\;x\;} \overleftarrow{y}$$\overleftarrow{x} \xleftarrow{\;y\;} \overleftarrow{y \cdot x\:}$.

$\overleftarrow 1$

$(\overrightarrow{x_1}, \overleftarrow{x_2}) \xrightarrow{\;y\;} (\overrightarrow{z_1}, \overleftarrow{z_2})$$\overrightarrow{x_1} \xrightarrow{\;y\;} \overrightarrow{z_1}$$\overleftarrow{x_2} \xrightarrow{\;y\;} \overleftarrow{z_2}$$(\overrightarrow 1, \overleftarrow x)$$(\overrightarrow x, \overleftarrow x)$$x$

Parece que su principal problema es utilizar el no determinismo, así que déjenme explicarlo.

La idea básica que utilizan los demás es que una máquina no determinista puede adivinar el resultado final.

$abc$

• $a$$a$$bc$$a$$b$
  • $a$$b$$b$
    • $b$$c$
  • $b$$b$$c$
    • $c$$c$
• $b$$a$
• $c$$a$$bc$$c$
  • $c$$b$$a$
    • $a$$c$

Como puede ver, el NFA es capaz de adivinar y verificar cada cálculo posible de abajo hacia arriba . Debido a que el lenguaje aceptado se define como el conjunto de cadenas que es aceptado por al menos una ejecución , se ignoran todas las ejecuciones que no aceptan en la entrada; la NFA "siempre acierta".

Ahora es fácil para esta NFA recordar su primera opción hasta el final. Si acepta, puede comparar el símbolo recordado con el producto lr (determinísticamente) obtenido en paralelo (la forma en que la intersección del lenguaje se relaciona con NFA seguramente está cubierta en Ullman / Hopcroft y cualquier otro libro de texto básico).