J'essaie de prouver que L={y#x|(y is a substring of x) ∧x,y∈{a,b}^* } n'est pas libre de contexte en utilisant le lemme de pompage, mais je ne peux pas sembler le faire. SiUtilisez le lemme de pompage pour prouver que la grammaire n'est pas sans contexte?
|vy|≠ε ,|vxy|≤k , uv^n xy^n z∈L ,∀n≥0
Ensuite, soit vxy a à la fois a et b, ou seulement b ou seulement a.
Comment puis-je le pomper pour le montrer?
Je suis d'accord avec cHao, utilisez le lemme de pompage pour montrer qu'une langue n'est pas Context Free. Pour prouver qu'une langue est libre de contexte, créez une grammaire contextuelle libre ou un DFA.
{y#x | y est un sous-ensemble de x} sur l'alphabet {a, b}* ne semble pas être contextuel, juste avec un coup d'oeil rapide.
Que s = (a|b)^p#(a|b)^(2p) donc c'est la chaîne où p caractères précèdent le # et 2p après pour en faire un sous-ensemble facile. Nous devons maintenant décomposer cette chaîne en x y^i z parties où |y| > 0 et |xy| = p. Donc le y doit être composé de n'importe quelle chaîne de caractères avant le #. Nous pouvons "pomper" cette chaîne maintenant le s.t. la première chaîne avant le # est plus grande que la seconde. Ce n'est plus un sous-ensemble de la seconde moitié. C'est une contradiction donc ce langage n'est pas libre de contexte.
Le lemme de pompage que vous utilisez est pour les langues régulières. Le lemme de pompage pour les langages sans contexte impliquerait une décomposition en 'uvxyz', où à la fois' v' et 'y' seraient pompés. Tel que présenté, la forme de la preuve ci-dessus serait applicable à d'autres langages non réguliers, non contextuels, «prouvant» qu'ils ne sont pas contextuels. Essayez-le avec 'a^nb^n', en prenant' s = a^pb^p'. Aussi, '| xy | ≤ p' dans la version normale, et 'vxy ≤ p' dans la version sans contexte. – outis
Le lemme de pompage n'est-il pas seulement utile pour montrer une langue * n'est pas * sans contexte? c'est-à-dire: Même si cela satisfait les conditions, cela pourrait ne pas être encore? – cHao
Ceci est hors sujet pour SO. Il appartient à http://cstheory.stackexchange.com. – andand
@andand Non, ce n'est pas le cas; [cstheory.SE] est seulement pour * niveau de recherche * TCS. Cela appartient à [cs.SE] qui a en fait une bonne [question de référence] (http://cs.stackexchange.com/questions/265/how-to-prove-that-a-language-is-not-context libre) sur le sujet. – Raphael