Application correcte du lemme de pompage CFL
Je suis tombé sur cette question pour montrer que la langue $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$est sans contexte mais pas linéaire dans le livre de Peter Linz. C'est facilement faisable par le lemme de pompage séparé pour les langages linéaires (comme indiqué dans le livre de Linz), mais ma question est différente.
Évidemment, il s'agit d'un CFL, et un automate de refoulement peut être construit pour cela. Mais si j'applique le lemme de pompage pour les CFL, je trouve que je suis capable de pomper des cordes qui n'appartiennent pas à la langue, ce qui signifierait que la langue n'est pas une CFL. Je fais clairement quelque chose de mal.
Selon le format «semblable à un jeu» donné à Linz, disons que vous choisissez $w = a^mb^mc^{2m}$, $|w| \ge m$. L'adversaire peut choisir un certain nombre de décompositions$w = uvxyz$, ils peuvent ressembler à -:
- $v = a^k, y = a^l$: Le cas où $|vxy|$ est contenu dans le $a$de la chaîne. Pompe$i = 0$, et alors $w_0 = a^{m – (k + l)}b^mc^{2m}$ ne peut pas être dans la langue puisque l'égalité ne tient plus.
- $v = a^k, y = b^l$: Le cas où $v$ est dans le $a$ section, $x$ s'étend sur le $a$'le sable $b$'le sable $y$ est dans le $b$section. Encore une fois, pompe$i = 0$. $w_0 = a^{m – k}b^{m – l}c^{2m}$ ne peut pas être dans la langue.
Il y a plus de cas comme ceux-ci. Où est-ce que je me trompe dans l'application du CFL PL?
Réponses
Le lemme de pompage pour les CFL indique que si $L$ est une CFL, il existe une constante $N \ge 1$ tel que pour tous $\omega \in L$ avec $\lvert \omega \rvert \ge N$ il y a une division $\sigma = u v w x y$ avec $\lvert v w x \rvert \le N$ et $v x \ne \varepsilon$ tel que $u v^k w x^k y \in L$ pour tous $k \ge 0$.
(Le lemme de pompage pour les langues régulières est similaire, la discussion ci-dessous s'applique avec des changements mineurs).
Vous voulez prouver par contradiction que $L$n'est pas une CFL. Alors vous supposez$L$est une LCF, et contredit le lemme. Cela signifie, en détail:
- Comme $L$est un CFL, il satisfait le lemme. En particulier, il y a une constante$N$ tel que...
- Comme le lemme l'indique, toutes les longues chaînes de$L$ peut être divisé, vous êtes libre d'en choisir un avec lequel il est facile de travailler.
- Le lemme dit qu'il y a une certaine division de$\omega$tel que ... pour tous $k \ge 0$...; pour contredire le lemme, vous devez prouver qu'aucune division ne fonctionne. En pratique, vous prenez une division donnée de votre$\omega$( toute division) et pour cela, choisissez$k$car cela ne donne pas de chaîne dans la langue. Vous devrez peut-être diviser cela en cas.
Que se passe-t-il pour les chaînes qui n'appartiennent pas à la langue ou qui sont plus courtes que $N$, est complètement hors de propos. Il se peut que certaines chaînes puissent être pompées, que certaines valeurs de$k$fonctionne pour toutes les chaînes, ... Ce qui est crucial, c'est que pour une chaîne$\omega$(celui que vous avez choisi) aucune division ne fonctionne avec une valeur de$k$(encore une fois, celui que vous avez choisi). Comme l'affirme le lemme, cela fonctionne pour toutes les chaînes assez longues, avec une certaine division pour tous $k$, un contre-exemple suffit. Des exemples infinis ne prouvent rien.