Caractérisation de

16

C'est une preuve standard dans les cours d'automates que pour et | Σ | 2 que S ( L ) = { w w : w L } n'est pas une langue sans contexte.L=Σ|Σ|2S(L)={ww:wL}

Il est également vrai que pour tout fini , S ( L ) est fini (et donc un CFL). Je suppose que L étant infini et régulier ne sont pas "suffisants" pour que S ( L ) ne soit pas une LFC. Edit : qu'en est-il des non-CFL L ?LS(L)LS(L)L

Existe-t-il une caractérisation de ce que a S ( L ) qui n'est pas une LFC?LS(L)

Ryan
la source
Si je comprends bien, la question est de décider, étant donné un langage régulier , si S ( L ) est hors contexte ou non. LS(L)
J.-E.
2
1. Pouvez-vous nous en dire plus sur le type de caractérisation que vous recherchez? Recherchez-vous un algorithme qui, étant donné , décide si S ( L ) est hors contexte? Recherchez-vous des conditions sur L suffisantes pour garantir que S ( L ) sera hors contexte? Quelle forme aimeriez-vous qu'une caractérisation prenne? 2. Si vous n'obtenez pas de réponse après quelques jours et que vous préférez le voir sur CSTheory.SE, n'hésitez pas à le signaler à l'attention du modérateur et à demander sa migration. LS(L)LS(L)
DW
@DW 1. Ce serait bien, mais je préférerais des conditions suffisantes. 2. Merci pour le conseil!
Ryan
1
@Ryan juste des conditions suffisantes? Eh bien, voici un couple: (a) L est régulier et pour tout dans L , w = w R (b) L est CF et pour tout n , L Σ n est soit vide soit égal à Σ n . Ce ne sont certainement pas nécessaires cependant. Si vous n'obtenez pas de réponses ici, veuillez déplacer la question dans la théorie. Je suis vraiment curieux de connaître les conditions nécessaires et suffisantes! wLw=wRnLΣnΣn
aelguindy du
Un infini et régulier n'est en effet pas suffisant pour S ( L ) pas CF. Si Σ = { a , b , c } , L = a alors S ( L ) = ( a a ) qui est régulier, donc CF. LS(L)Σ={a,b,c},L=aS(L)=(aa)
chi

Réponses:

2

Plus un commentaire étendu avec une conjecture, mais voici une condition qui semble saisir le problème, dans le contexte de régulier pour que S ( L ) soit hors contexte.LS(L)

Condition Dans le DFA minimal pour L , tout chemin d'acceptation contient au plus une boucle.AL

Exception: deux boucles sont autorisées si leurs étiquettes et l'étiquette du préfixe avant la première boucle commutent toutes, et le suffixe après la deuxième boucle est vide. Par exemple aab(aa) est ok.

Rappelons que deux mots et v commuent s'ils sont des puissances d'un même mot t . Nous pouvons supposer que le suffixe est vide, car il ne peut pas être non vide et commuter avec l'étiquette de la deuxième boucle dans un DFA.uvt

Suffisante Supposons que la condition, on construit une PDA pour en traitant chaque motif acceptant x u y de Au étiquettes une boucle simple. Nous voulons accepter des mots de la forme x u n y x u n y . Nous lisons x , poussons un symbole pour chaque occurrence de u , lisons y x , puis pop un symbole pour chaque occurrence de u , et finalement lisons y .LxuyAuxunyxunyxuyxuy

À propos de l'exception, si nous sommes dans ce cas, un chemin d'acceptation de base est de la forme u , v sont les étiquettes des boucles. Nous acceptons les mots de la forme x u n y v m x u n y v m , mais par hypothèse ( x , u , v commute), c'est la même chose que u n x y u n v m x y v m , qui peut être fait par un PDA: pousser nxuyvu,vxunyvmxunyvmx,u,vunxyunvmxyvmnfois (pour les occurrences de ), lire x y , pop n fois, pousser m fois (pour v ), lire x y , pop m fois.uxynmvxym

Le PDA final est l'union des PDA pour chaque modèle.

Nécessaire (handwaving) S'il y a un chemin avec deux boucles, même dans le cas le plus simple où vous devez prendre l'une puis l'autre (par exemple ), vous devez vous rappeler combien de fois chacune est prise, mais la structure de la pile vous empêche de les répéter dans le même ordre. Notez que le fait que le DFA soit minimal est important dans la caractérisation, pour éviter d'utiliser deux boucles quand l'une pourrait suffire.ab

Pour l'instant, la partie nécessaire n'est qu'une conjecture, et d'autres exceptions pourraient être nécessaires pour obtenir la condition exacte, je serais intéressé par des contre-exemples.

Denis
la source
«puis la lecture w à nouveau, popping un symbole pour chaque boucle prise dans la deuxième occurrence du mot » - mais il y a une infinité de tels ! A moins que je ne lise mal votre argument. w
Ryan
@Ryan the number of "patterns" xuy where u labels a loop is finite, so we can guess which one we are reading.
Denis
I edited to clarified this part.
Denis
u,v,w1,w2w1w2u(w1+w2)vL
ab