Bonjour, j'aurais besoin d'une relecture de ce que j'ai fais pour un exercice:

Montrer que le langage n'est pas un language non - contextuel.

Intuition: le nombre de a et de b dépendent du nombre de c ce que l'on ne peut pas illustrer avec la structure de donnée pile.

On va utiliser le lemme d'itération pour prouver cela:

Supposons que L soit libre de contexte.

Par le lemme d'itération, il existe un entier m >0 où tous les mots du langage L supérieurs ou égaux  (en taille) à m peuvent être divisés en 5 parties u, v, x , y et z telles que
la taille de vxy est bornée par m, la taille de vy est au moins égale à 1 et pour tout entier positif i, nous avons le uv^ixy^iz dans notre langage L.

En particulier, nous pouvons prendre le mot w = a^(m+2) b^(m+1)c^n.

La taille de vxy est bornée ci-dessus par m implique que :

- vy = a^j b^k où j+k <= m

- vy = b^k c^l où k+l <= m


La taille de vy est au moins 1 implique que le mot contient au moins 1 lettre : a,b ou c. En d'autres termes,

- Si alors j>=1 ou k>=1 (i)

- Si alors k>=1 ou l>=1 (ii)

Prenons i = 0 :

- Si   alors . Remarquez que la seule façon pour que est puisque k est un entier positif. En raison de la relation (i), nous avons. Cependant, la seule façon d'avoir est j < 1. Donc uxz n'appartient pas à L.

- Si alors .   implique que   donc . De plus l peut prendre les valeurs 1,...,m mais si l = m alors on a une contraction puisque k+l <=m.

Comme dans tous les cas, nous avons c'est que notre hypothèse de départ était fausse !

L n'est pas non-contextuel.

Ma question est ce qu'il est suffisant dans le deuxième cas de trouver une contradiction sur un cas limite ou est ce que je dois véritablement montrer que c'est faux pour chaque possibilité  comme je l'ai fais dans le premier cas   ?


c