Context free Grammar : three small exercices Hi everybody I want to submit you my work I did on some works and receiving also some help :) 
Thank you a lot : so here the exercices on which I worked : 
Ex 1:
Prove that the language : $L=\{w\in\{a,b,c\}^*|n_a(w)=n_b(w)=n_c(w)\}$ isn't context free with $n_a(w)$ the number of a in w, $n_b(w)$ the number of b in w and $n_c(w)$ the number of c in w
What I did : I studied firstly this language  $L1= \{w\in\{a,b\}^*|n_a(w)=n_b(w)\}$ and we have this grammar for L1 : 
S --> SS|aSb|bSa|$\lambda$ 
So that we can deduce that L is context free.
N.B : $\lambda$ matches the empty word
The same for the second language I considered : $L2=\{w\in\{a,c\}^*|n_a(w)=n_c(w)\}$
But L is the intersection of the both so it can't be a context free grammar. Is it right ?
Ex 2 :
Is $L = \{a^nb^mc^nd^m | n, m > 0\}$ context-free ?
So For this exercice I try to use the Pumping lemma as I think it's not a context free grammar. But I don't manage to find a contradiction ! 
So I have a question : if we must show that this kind of language is context free how we must process ?
I also tried to divide this set on several subset to try to form L with intersections for instance but it doesn't work :/
Ex 3 
Try to prove this language : $L1=\{a^nb^n|n>0\}$ is not context free by using the  "Pumping Lemma" ...
Then I tried ... and worse I find it's the same demonstration than for proving  $L2=\{a^nb^n|n\geq0\}$ is not context free ... And I found that strange :S
And by thinking it seems that L1 is a regular language no ?
 A: Explanation for Ex1 :
I'm starting with $L1$
$L1= \{w\in\{a,b\}^*|n_a(w)=n_b(w)\}$
Well, I hope you know, Operation PUSH() and POP() on STACK.
How we identify the string which belong in language $L1$; pseudocode is :


*

*Take an empty STACK.

*PUSH each 'a' on STACK; whenever you found in string.

*POP single 'a' from STACK for each 'b'; whenever you found in string.

*If you reach end of string, and final STACK is empty, then given string is in language $L1$; else not.


Note that if the string starts with 'b' then you must exchange a and b on above pseudocode.
$\text{Since you can identify strings of L1 using single STACK, hence given language is context free.}$ 
Your grammar is correct for $L1$. Similarly you can find the language $L2$ is also context free, by replacing 'c' with 'b'.
Note that languages $L1$ and $L2$ can not be regular, since we can't do matching without STACK. Both languages are DCFL. 
Now take language $L=\{w\in\{a,b,c\}^*|n_a(w)=n_b(w)=n_c(w)\}$ 
For three alphabet, we can't do matching with single STACK. We need atleast two STACKs; pseudocode is :


*

*Take two stack; STACK1 and STACK2.

*PUSH each 'a' on STACK1; whenever you found in string.

*PUSH each 'b' on STACK2; whenever you found in string.

*POP single 'a' from STACK1 and POP single 'b' from STACK1 for each 'c'; whenever you found in string.

*If both STACKs are empty, then given string is in language $L$; else not.


Note that if the string starts with 'b' or 'c' then you must exchange a and b or a and c respectively on above pseudocode.
$\text{Since you can identify strings of L using TWO STACK, hence given language is context sensitive.}$
Explanation for Ex2 :
$L = \{a^nb^mc^nd^m | n, m > 0\}$ is not context free, since we can't identify the strings of $L$ using single STACK; pseudocode is :


*

*Take two stack; STACK1 and STACK2.

*PUSH each 'a' on STACK1; whenever you found in string.

*PUSH each 'b' on STACK2; whenever you found in string.

*POP single 'a' from STACK1 for each 'c'; whenever you found in string.

*POP single 'b' from STACK2 for each 'd'; whenever you found in string.

*If both STACKs are empty, then given string is in language $L$; else not.


Grammar for $L$ is :
$$
\begin{align*}
&S \to XY \\
&X \to aXC | aC \\
&Y \to BYd | Bd \\
&CB \to BC \\
&aB \to ab \\
&bB \to bb \\
&Cd \to cd \\
&Cc \to cc \\
\end{align*}
$$
$\text{Note that above grammar for $L$ is context sensitive.}$
Explanation for Ex3 :
I'm taking language $L2$ first,  $L2=\{a^nb^n|n\geq0\}$
Pumping lemma for regular languages
Let L = {ambm | m ≥ 1}.
 Then L is not regular.
 Proof: Let n be as in Pumping Lemma.
 Let w = anbn.
 Let w = xyz be as in Pumping Lemma.
 Thus, xy2z ∈ L, however, xy2z contains more a’s than b’s. 
You need a stack for matching; pseudocode is :


*

*Take an empty STACK.

*PUSH each 'a' on STACK; whenever you found in string.

*POP single 'a' from STACK; whenever you found in string.

*If you reach end of string, and final STACK is empty, then given string is in language $L2$; else not.


Strings of $L1 =\{ab, aabb, aaabbb,....,a^nb^n\}$ and grammar for $L1$ is :
$$S→aSb | ab$$
Strings of $L2 =\{\in, ab, aabb, aaabbb,....,a^nb^n\}$ and grammar for $L2$ is :
$$S→aSb | \in$$
Therefore, $$L2= \{\in + L1\}$$
$\text{Both $L1$ and $L2$ are DCFL, since we need STACK for matching. We can't matching in NFA/DFA.}$
