Caractérisation de

C'est une preuve standard dans les cours d'automates que pour et que n'est pas une langue sans contexte. $L = \Sigma^\star$ $|\Sigma| \ge 2$ $S(L) = \{ww : w \in L\}$

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

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

context-free Ryan
la source

Si je comprends bien, la question est de décider, étant donné un langage régulier

, si

est hors contexte ou non.

L

$L$

S (L)

$S(L)$

J.-E.

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

est hors contexte? Recherchez-vous des conditions sur

suffisantes pour garantir que

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.

L

$L$

S (L)

$S(L)$

L

$L$

S (L)

$S(L)$

@DW 1. Ce serait bien, mais je préférerais des conditions suffisantes. 2. Merci pour le conseil!

Ryan

@Ryan juste des conditions suffisantes? Eh bien, voici un couple: (a) L est régulier et pour tout

dans

(b) L est CF et pour tout

est soit vide soit égal à

. 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!

w

$w$

L

$L$

w = w^{R}

$w = w^R$

n

$n$

L \cap Σ^{n}

$L \cap \Sigma^{n}$

Σ^{n}

$\Sigma^{n}$

aelguindy du

infini et régulier n'est en effet pas suffisant pour

pas CF. Si

alors

qui est régulier, donc CF.

L

$L$

S (L)

$S(L)$

Σ = {a, b, c}, L = a^{*}

$\Sigma = \{a,b,c\},L = a^*$

S (L) = (a a)^{*}

$S(L) = (aa)^*$

chi

Réponses:

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 soit hors contexte. $L$ $S(L)$

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

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 $aa^*b(aa)^*$ est ok.

Rappelons que deux mots et commuent s'ils sont des puissances d'un même mot . 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. $u$ $v$ $t$

Suffisante Supposons que la condition, on construit une PDA pour en traitant chaque motif acceptant de où étiquettes une boucle simple. Nous voulons accepter des mots de la forme . Nous lisons , poussons un symbole pour chaque occurrence de , lisons , puis pop un symbole pour chaque occurrence de , et finalement lisons . $L$ $xuy$ $A$ $u$ $xu^nyxu^ny$ $x$ $u$ $yx$ $u$ $y$

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

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. $a^*b^*$

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

$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, w_{1}, w_{2}

$u,v,w_1,w_2$

w_{1}

$w_1$

w_{2}

$w_2$

u (w_{1} + w_{2})^{*} v \subseteq L

$u(w_1+w_2)^*v \subseteq L$

a^{*} b^{*}

$a^*b^*$