Context free Grammar : three small exercices

Question

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 ?

Answer 1

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 :

1. Take an empty STACK.
2. PUSH each 'a' on STACK; whenever you found in string.
3. POP single 'a' from STACK for each 'b'; whenever you found in string.
4. 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 :

1. Take two stack; STACK1 and STACK2.
2. PUSH each 'a' on STACK1; whenever you found in string.
3. PUSH each 'b' on STACK2; whenever you found in string.
4. POP single 'a' from STACK1 and POP single 'b' from STACK1 for each 'c'; whenever you found in string.
5. 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 :

1. Take two stack; STACK1 and STACK2.
2. PUSH each 'a' on STACK1; whenever you found in string.
3. PUSH each 'b' on STACK2; whenever you found in string.
4. POP single 'a' from STACK1 for each 'c'; whenever you found in string.
5. POP single 'b' from STACK2 for each 'd'; whenever you found in string.
6. 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 = {a^mb^m | m ≥ 1}.
Then L is not regular.
Proof: Let n be as in Pumping Lemma.
Let w = aⁿbⁿ.
Let w = xyz be as in Pumping Lemma.
Thus, xy²z ∈ L, however, xy²z contains more a’s than b’s.

You need a stack for matching; pseudocode is :

1. Take an empty STACK.
2. PUSH each 'a' on STACK; whenever you found in string.
3. POP single 'a' from STACK; whenever you found in string.
4. 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.}$