Regular Language Closure Unconcatenation

Question

J'essaie de trouver une opération qui peut prendre un langage régulier et le "déconcentrer" avec un autre. Par exemple:

a * L - a * = L | où L est un langage régulier

Je sais que la différence (soustraction) n'est pas l'opération que je veux. Mais je crois que je comprends mon point de vue. Une autre façon de voir cela est de savoir s'il existe un ensemble L logiquement égal à (A ∪ B), mais nous n'avons pas accès à A. Donc, si nous ne pouvons utiliser que L, B et les dérivations de tel, pouvons-nous en quelque sorte dériver A. Fondamentalement:

L - B = A | L = (A ∪ B)

J'ai mis beaucoup réfléchi à ce problème, en utilisant de nombreuses variantes de compliment, intersection, et d'autres propriétés de fermeture des langues régulières, mais je ne peux tout simplement pas comprendre.

Le meilleur que j'ai réussi à trouver est:

A = ((L - B) ∪ (A ∩ B) | L = (A ∪ B)

. Cependant, cela nécessite une sur le côté droit

Answer 1

Si l = AUB, définir un opérateur - tel que l - B = A.

Le problème avec ceci est que l'opérateur - n'est pas bien défini: Étant donné L et B, il y a potentiellement plusieurs langages qui satisfont L = AU B. En particulier, si A est un sous-ensemble de L et tout surensemble (éventuellement incorrect) de L \ B, alors A est une solution; c'est-à-dire, si A = (L \ B) U C, où C est un sous-ensemble (éventuellement impropre) de B, alors L - B pourrait aussi bien être égal à cet ensemble. Maintenant, vous pourriez définir - pour désigner l'ensemble de tous ces A, et dans ce cas, vous pourriez rendre cela possible en utilisant des opérateurs de différence de réglage, d'union et de jeu de puissance. Alors, L - B = Q où Q = {(L \ B) U {}, (L \ B) U {B [0]}, ..., (L \ B) U B = L}. Vous pouvez rendre ceci bien défini si vous spécifiez - retourne toujours l'élément "le plus petit" de Q (pour les ensembles finis, celui avec le moins d'éléments, pour les ensembles infinis, celui qui est un sous-ensemble de tous les autres ensembles), auquel cas vous récupérez simplement L \ B.

Si L = BA, définir un opérateur - tel que L - B = A.

un problème similaire existe ici: il peut y avoir plusieurs par exemple, considérons B = a *, et deux choix pour A: a * et {e}, la langue ne contenant que l'ensemble vide. Vous pouvez montrer sans trop d'effort que a * a * = a * e, donc L est la même chose, B est la même, et L-B doit maintenant produire deux valeurs différentes: soit * ou {e}.