1
$\begingroup$

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 ?

$\endgroup$
0
$\begingroup$

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 = {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 :

  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.}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.