Lemme de pompage pour les langues sans contexte

Question

J'ai une question sur un problème spécifique de lemme de pompage pour les langues sans contexte.

Supposons que nous ayons la langue suivante:

L = {(a^i)(b^j)(c^k)(d^l) | 0 < i < k AND j > l > 0 } 

Voici mon attemp pour prouver que la langue n'est pas hors-contexte:

On suppose sans contexte L. Prenez la constante n> 0 du lemme.

Let Z = (a^n)(b^n+1)(c^n+1)(d^n), Z ∈ L. 

que selon le lemme, Z peut être écrit Z = uvwxy où les propriétés suivantes:

1. |vx| >= 1 
2. |vwx| <= n 
3. for every i >= 0, u(v^i)w(x^i)y ∈ L. 

Nous avons 6 possibilités différentes pour vwx

1. vwx = a^i, i <= n 
2. vwx = (a^i)(b^j), i+j <= n 
3. vwx = b^i, i <= n 
4. vwx = (b^î)(c^j), i+j <= n 
5. vwx = (c^i), i <= n 
6. vwx = (c^i)(d^j)), i+j <= n 

Est-ce droit jusqu'ici? Les choses que je ne suis pas sûr, c'est si mes différents cas de vwx sont corrects.

Merci à l'avance

Answer 1

Jusqu'à présent, si bon, sauf que vous avez manqué le cas où vxy est entièrement constitué d's à partir de la fin de la chaîne.