Prouver la langue qui comprend toutes les chaînes dans une langue est de la même longueur qu'une chaîne dans une autre langue est régulière

8

Donc, je me gratte la tête sur ce problème depuis quelques jours maintenant. Étant donné une certaine langueA et B c'est régulier, montrer que la langue L qui se compose de toutes les chaînes A dont la longueur est égale à une chaîne B est une langue régulière.

Sous forme d'équation:

L={xAyB s.t. |x|=|y|}

Ma pensée initiale était d'essayer de trouver un DFA pour les deux langues A et B et mapper les deux états l'un avec l'autre et, espérons-le, obtenir un rapport 1: 1 de cette façon, je peux générer un nouveau DFA qui prouve que Lest régulier. Mais j'ai réalisé queA et B ne doivent pas être sur le même ensemble de symboles.

Je pense que la bonne façon de résoudre ce problème est d'utiliser les propriétés de fermeture du langage ordinaire, mais je ne sais pas comment commencer / utiliser les propriétés pour les "longueurs" de chaînes au lieu des chaînes elles-mêmes.

Quelqu'un peut-il m'indiquer la bonne direction?

Jubileux
la source

Réponses:

4

Rappelez-vous (ou trouvez) la preuve de

L1,L2REGL1L2REG.

Voyez-vous comment modifier la preuve de votre paramètre?

Abstraction de l'égalité des choses, imaginez une construction pour un automate pour

Ll={wΣxL.|x|=|w|}

pour donné, arbitraire LREG plus de Σ.

Voyez-vous la connexion?

Notez maintenant que L=ABl.

Raphael
la source
3

Astuces: Supposons que vous connaissez toutes les différentes longueurs de motsB, len(B)={1,2,3,...}. Pour le moment, supposons que ce soit fini.

Pouvez-vous utiliser ces connaissances pour créer un DFA pour A?
(indice: intersection ou construction "cross-product")

L'alphabet de B importe même?

Ensuite, ce pourrait être l'ensemble des longueurs len(B)est infini. Ensuite, regardez cette question qui devrait également résoudre ce problème.

A sonné.
la source
2

La manière de la propriété de fermeture, donc pas d'automates (explicites). Les langues régulières sont fermées sous les morphismes, les morphismes inverses et l'intersection (avec les langues régulières).

Laisser ΣA et ΣB être les alphabets de A et B. LaisserhX:ΣX{1} être le morphisme qui mappe chaque lettre aΣX à 1. alorshB(B){1} code l'ensemble de longueur de B, et hA1(hB(B)) se compose de (toutes) les chaînes de même longueur que les chaînes B, mais sur l'alphabet de A. Enfin, nous observons queL=AhA1(hB(B)).

Maintenant, pour le bonus . Il fonctionne également sans contexte A et B. Nous avons cependant besoin d'une propriété supplémentaire: siB est hors contexte alors hB(B)est régulier (!) car toutes les langues sans contexte «unaire» (= alphabet à une seule lettre) sont régulières, conséquence du théorème de Parikh . Ainsi aussihA1(hB(B)) est régulier, et L est sans contexte.

Hendrik Jan
la source