Le langage de prévision est sans contexte avec le lemme de pompage

Question

J'ai un test à venir en utilisant le lemme de pompage pour prouver si une langue est sans contexte. J'essaie de résoudre certains problèmes de pratique et les choses ne vont pas si bien ...

Le problème de pratique est: Pour a) à j), vérifiez si la langue suivante est libre ou non . Si c'est sans contexte, donnez une grammaire sans contexte qui la génère.

Les deux premiers sont:

a) {a^(2i+1) b^(3k+2) c^(4k+3) d^(5i+4) | i >= 0, k >= 0} 

b) {a^i b^i c^k d^i | i >= 1, k >= 1} 

Si quelqu'un peut résoudre ces deux premiers, ce qui donne une explication détaillée de la façon dont ils l'ont fait, je suis sûr que je serai en mesure de comprendre le reste (c à travers j) moi-même.

Answer 1

un contexte est libre:

A -> aBdddd 
B -> aaBddddd 
B -> C 
C -> bbbCcccc 
C -> D 
D -> bbccc 

B n'est pas libre contexte. Supposons que c'est. Nous avons donc un entier p pour lequel le lemme de pompage est valable. Regardons le mot suivant dans b: a^p b^p c d^p

Selon le lemme de pompage, ce mot peut être représenté comme la séquence uvwxy, tel que | vwx | < p, u et v^i^w x i y est également dans B.

regardons vx:

Cas 1: vx contient "c". Si c'est le cas, alors Uwy est supposé être aussi dans B, mais B exige que nous ayons au moins un "c". Donc, ce cas est impossible.

Cas 2: vx ne contient pas "c". Il doit contenir au plus deux de "a", "b" ou "c" (ou bien | vwx | serait plus que p). Par conséquent, uv^2wx^2y ne contiendra pas un nombre égal de a, b et c, et n'est pas non plus dans B.

B n'est donc pas une langue sans contexte.