Quand la concaténation de deux langues régulières est-elle sans ambiguïté?

16

Étant donné les langues A et B , disons que leur concaténation AB est sans ambiguïté si pour tous les mots wAB , il y a exactement une décomposition w=ab avec aA et bB , et ambiguë sinon. (Je ne sais pas s'il existe un terme établi pour cette propriété - chose difficile à rechercher!) Comme exemple trivial, la concaténation de {ε,a} avec elle-même est ambiguë ( ), mais la concaténation de { a } avec elle-même est sans ambiguïté.w=a=εa=aε{a}

Existe-t-il un algorithme pour décider si la concaténation de deux langues régulières est sans ambiguïté?

rstern
la source
1
Gah, c'est totalement un problème de première année CS, n'est-ce pas? Honnêtement, je n'ai pas beaucoup essayé; J'espérais qu'il existe un algorithme établi pour cela quelque part dans la littérature et je n'aurais pas à aller réinventer la roue. J'écris des logiciels ici; Je n'ai suivi que quelques cours de CS (il y a plusieurs années), je commence donc essentiellement par Wikipedia. Je sais que personne n'aime quelqu'un qui ne veut pas travailler pour sa réponse, donc s'il y a un manuel ou un document ou quelque chose que vous pourriez me montrer au lieu de me donner simplement un algorithme, ce serait utile! Merci!
2015
J'ai ajouté cela en tant que commentaire parce que, bien son sujet relativement hors sujet, mais peut-être peut vous conduire à de l'aide. Le consortium Unicode dispose de quelques processus pour déterminer les points communs entre les langues. J'ai lu un lien très informatif sur leur site mais pour la vie de moi je n'ai pas pu le trouver aujourd'hui pour en faire une réponse à la place. Si vous avez le temps de rechercher ceci, voici leur page FAQ unicode.org/faq
htm11h

Réponses:

10

Astuce: étant donné les DFA pour et B , construisez un NFA qui accepte les mots dans A B ayant au moins deux décompositions différentes. Le NFA conserve une trace de deux copies du NFA standard pour A B (formé en joignant les DFA pour A et B avec ϵ transitions), garantissant que le passage de A à B se produit à deux points différents.ABABABABϵAB

Yuval Filmus
la source
Merci pour l'astuce! Donc, si je comprends bien, je peux construire un NFA pour les mots ambigus dans , puis tester cet automate pour le vide. La partie la plus délicate semble être de "veiller à ce que le passage de A à B se fasse à deux points différents". Je ne sais pas comment faire autrement que de prendre le produit croisé (?) De deux A B DFA et de supprimer tous les états du produit ( A -terminal, A -terminal). la transition de A B NFA à A B DFA reviendrait à l'idée de AABABABAAABABA-Terminal. Cela semble, euh, inefficace; existe-t-il un algorithme connu adapté aux logiciels?
2015
Oui, cela ne semble pas trop efficace, bien qu'il soit toujours possible de le faire de manière intelligente. Je ne connais aucun algorithme spécifique pour ce problème, mais il pourrait en exister un.
Yuval Filmus
7

Mise à jour (merci à Yuval Filmus).

Étant donné deux langues et Y de A , soit X - 1 YXYA Je prétends queXYest sans ambiguïté si et seulement si la langueX-1XYY-1A+est vide.

X1Y={uAthere exists xX such that xuY}YX1={uAthere exists xX such that uxY}
XYX1XYY1A+

Preuve . Supposons que soit ambigu. Ensuite , il existe un mot u qui a deux décompositions sur X Y , par exemple u = x 1 y 2 = x 2 y 1 , où x 1 , x 2X et y 1 , y 2Y . Sans perte de généralité, nous pouvons supposer que x 1 est un préfixe de x 2 , c'est-à-dire x 2 = xXYuXYu=x1y2=x2y1x1,x2Xy1,y2Yx1x2x2=x1z for some zA+. It follows that u=x1y2=x1zy1, whence y2=zy1. Thus zX1XYY1.

X1XYY1zx1,x2Xy1,y2Y such that x2=x1z and y2=zy1. It follows that x2y1=x1zy1=x1y2 and hence the product XY is ambiguous.

If X and Y are regular, then both X1X and YY1 are regular and thus X1XYY1 is also regular (see Yuval's answer for an automaton accepting this language).

J.-E. Pin
la source
What if z is the empty word?
Yuval Filmus
Ooops. I update.
J.-E. Pin