Mots ayant le même produit associatif droit et gauche

J'ai commencé à étudier les automates non déterministes en utilisant le livre de Hopcroft et Ullman . Je suis coincé dans un problème que j'ai trouvé très intéressant:

Donnez un automate fini non déterministe acceptant toutes les chaînes qui ont la même valeur lorsqu'elles sont évaluées de gauche à droite comme de droite à gauche en multipliant selon le tableau suivant:

$\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}$

Donc, si nous avons la chaîne $abc$ ,
le produit de gauche à droite est $(a \times b) \times c=a \times c=c$ et
le produit de droite à gauche est $a \times (b \times c)=a \times b=a$

Donc , ne devrait pas être acceptable pour les automates. Pour moi, il est évident que toute chaîne a a ∗ ou b b ∗ ou c c ∗ est une chaîne acceptable (leur évaluation droite et gauche fonctionne sur les mêmes chaînes partielles). Il est facile de donner un NFA qui décrit l'évaluation de gauche à droite mais le problème est que si la machine essaie de calculer l' évaluation de droite à gauche , je pense qu'elle a besoin de connaître la longueur de la chaîne (donc une mémoire infinie est nécessaire).$abc$$aa^*$$bb^*$$cc^*$

Alors, comment un automate non déterministe peut-il évaluer de droite à gauche afin de se comparer à l'évaluation de gauche à droite?

La première astuce consiste à considérer la table de multiplication comme la table de transition d'un automate chaque état représentant une lettre dans votre table de multiplication, mais sans se soucier encore de l'acceptation. Ainsi, les lettres à gauche et dans le corps du tableau sont en fait des états - il serait plus précis de les écrire comme$A$ , mais je ne le ferai pas. Les lettres en haut sont des entrées.$q_a, q_b, q_c$

Construisez ensuite l'automate ("$A_T$ " pour la transposition) pourla multiplication inverseen transposant A :$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}$

Donc vous amène à l'état c , et de même A T ( c b $A(abc)$$c$ passe à l'état a de A T , comme vous le constatez.$A_T(cba)$$a$$A_T$

Cependant, suppose que vous allez de droite à gauche, et nous voulons toujours aller de gauche à droite. Donc, la deuxième astuce consiste à inverser l'automate (pas la multiplication, qui nous ramènerait juste si nous avions commencé), en inversant toutes les flèches, ce qui conduit à un automate A T R non déterministe donné par le tableau de transition ci-dessous, avec sous-ensembles indiqués par des lettres concaténées pour empêcher le poulet de se gratter, donc un c est vraiment { a , c } . (j'espère que j'ai bien compris - semble fonctionner).$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}$

Vous pouvez l'interpréter comme un automate non déterministe avec seulement les trois lignes au-dessus de la ligne ou une version déterminée avec les 8 lignes.

Enfin, la machine pour résoudre le problème est l'automate produit croisé des et A T R d'origine , c'est-à-dire A × A T R pour effectuer le comportement d'intersection des deux automates (nous n'avons plus besoin de A T ) . A × A T R possède des états qui sont des paires comme ⟨ un , un c ⟩ . La fonction de transition exécute A et A T R indépendamment. Un état de départ unique ⟨ 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$ passe en sous entrée$\langle a,a \rangle$ , en$a$ en entrée b , etc. $\langle b,b \rangle$$b$

Accepter les états dans la version non-déterministe sont etc. Dans la version déterministe, acceptant états sont des paires , dans lequel le premier composant est ∈ du second ensemble des composants, tels que ⟨ un , un ⟩ ou ⟨ b , b c ⟩ .$\langle a,a \rangle$$\in$$\langle a,a \rangle$$\langle b,bc \rangle$

augmenté et déterminé comme indiqué a 25 = 3 ⋅ 8 + 1 états, alors pardonnez-moi si je ne l'écris pas en détail. Mais la version non déterministe n'a que 10 = 3 ⋅ 3 + 1 états.$A \times A_{TR}$$25=3\cdot 8+1$$10=3\cdot 3+1$

Si L est une langue régulière, alors L R , la langue constituée de l'inversede tous les mots de L , est également régulière. Prenez cela comme un exercice.$(\ast)$$L$$L^R$$L$

Comment cela nous aide-t-il à résoudre le problème? Soit les langages constitués de toutes les chaînes évaluées en a , b , c lors de l'évaluation de gauche à droite. La langue qui vous intéresse est ( L a ∩ L R a ) ∪ ( L b ∩ L R b ) ∪ ( L c ∩ L R c ) . Cela montre que si vous savez prouver $L_a,L_b,L_c$$a,b,c$

En fait, si vous utilisez l' idée de la preuve de , vous pouvez probablement continuer et construire l'automate. Examinons donc cela. En particulier, essayons de construire un NFA pour L R a , le langage de toutes les chaînes qui évaluent à$(\ast)$$L_a^R$ lorsqu'il est évalué de droite à gauche.$a$

L'idée est la suivante. Supposons que la première lettre que vous voyez soit . Ensuite, le reste de la chaîne doit être évalué à b (puisque b x = a implique x = b ). Un raisonnement similaire s'applique lorsque la première lettre est c . Cependant, lorsque la première lettre est un , le reste peut être évalué à a ou b , ou être nul. Avec un NFA, nous pouvons deviner (et vérifier plus tard notre supposition).$b$$b$$bx = a$$x = b$$c$$a$$a$$b$

Cet indice devrait vous donner suffisamment de matière à réflexion et, espérons-le, résoudre le problème.

Mignonne.

Tout d'abord, construisez un automate qui calcule le produit de gauche à droite. Facile! Mettez une transition chaque fois quex⋅y=z. Il y a trois états{ → a , → b , → c }représentant les trois produits possibles. Commencez dans un quatrième état → 1 avec → $\overrightarrow x \xrightarrow{\;y\;} \overrightarrow z$$x \cdot y = z$$\{\overrightarrow a,\overrightarrow b,\overrightarrow c\}$$\overrightarrow 1$ pour toutx. L'état final est → x si et seulement si le produit du mot saisi de gauche à droite est$\overrightarrow 1 \xrightarrow{\;x\;} \overrightarrow x$$x$$\overrightarrow x$$x$ .

Construisons maintenant un automate qui calcule le produit de droite à gauche. Celui-ci sera non déterministe. Comment fait-on cela? Simple… Pour aller dans l'autre sens, il suffit de tout inverser : les flèches et le sens du produit.

Où nous avions avant $\overrightarrow{x} \xrightarrow{\;y\;} \overrightarrow{x \cdot y\:}$, on prend maintenant : quand on consomme le mot de gauche à droite, on passe d'un produit à son facteur de droite. Ou, en d'autres termes, ← $\overleftarrow{x \cdot y\:} \xleftarrow{\;x\;} \overleftarrow{y}$$\overleftarrow{x} \xleftarrow{\;y\;} \overleftarrow{y \cdot x\:}$.

Ajouter un nœud déconnecté $\overleftarrow 1$ pour le mot vide. Tous les nœuds sont initiaux.

$(\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)$ be final. A word is recognized by this non-deterministic automaton iff its product from left to right and its product from right to left are the same $x$.

It seems that your main problem is utilising nondeterminism, so let me elaborate on that.

The basic idea the others utilise is that a nondeterministic machine can guess the final result.

Let us consider your small example $abc$ and Gilles' construction idea. The automaton "computing" the right-to-left product guesses the result in the beginning and verifies it. So there are three possibilities:

• Guess $a$: As the first symol is $a$, the rl-product of $bc$ must have been $a$ or $b$.
  • Guess $a$: As the second symbol is $b$, the last symbol must have been $b$.
    • (Guess $b$:) It is $c$, so don't accept.
  • Guess $b$: As the second symbol is $b$, the last symbol must have been $c$.
    • (Guess $c$:) It is indeed $c$, so we accept.
• Guess $b$: As the first symol is $a$, this is not possible, so don't accept.
• Guess $c$: As the first symol is $a$, the rl-product of $bc$ must have been $c$
  • (Guess $c$:) As the second symbol is $b$, the last symbol must have been $a$
    • (Guess $a$:) It is $c$, so don't accept.

As you can see, the NFA is able to guess and check every possible computation bottom-up. Because the accepted language is defined as the set of strings that is accepted by at least one run, all non-accepting runs on the input are ignored; the NFA "always guesses right".

Now it is easy for this NFA to remember its first choice until the end. If it accepts, it can compare the remembered symbol to the lr-product (deterministically) obtained in parallel (how language intersection relates to NFA is surely covered in Ullman/Hopcroft, and any other basic textbook).