# Grammar for ${a^n b^n c^{n+m}}$

Can we define a grammar for the following language?

$$L = \{a^n b^n c^{n+m} | n,m>=0\}\,.$$

I can define one for this:
$$L=\{a^nb^n|n,m>=0\}$$

S --> aSb | λ

or this one: $$L=\{b^nc^{n+m}|n,m>=0\}$$

S --> Ac
A --> bSc | Sc | λ

but I can't solve the first one, any hint?

• The language is not context free. And it's certainly not regular. What does "of a finite automata" mean? – Karolis Juodelė Sep 27 '14 at 8:07
• Ofcourse you can. But don't try by a context free grammar... this language is not context free. You can use this grammaer for reference: en.wikibooks.org/wiki/Computability_and_Complexity/… Adding the ${c}^*$ at the end should be easy – Roi Divon Sep 27 '14 at 8:09

This gives the language: $L = \{a^n b^n c^n c^m | n,m>=0\}\,.$

1. S → a b c C | N | ε
2. N → a N B c C | a b c C
3. c B → W B
4. W B → W X
5. W X → B X
6. B X → B c
7. b B → b b
8. C → c C | ε
• can you show me some guidelines on deriving such grammars? – Amen Sep 28 '14 at 16:19
• Well in this case I noticed that the language that you need is extremely close to the very famous and most popular context-sensitive language $a^nb^nc^n$. Then I just needed to put c* on the end. Additionally, we need to modify the starting process to allow for n,m=0. Look closely at the simpler language (on wikipedia) and compare to this one. That should help. – d'alar'cop Sep 28 '14 at 16:43

GRAMMAR FOR THE LANGUAGE:{a^n b^n c^n/n>=1}

S->abc|A

A->aABc|abc

cB->Bc

bB->bb

FOR EXAMPLE:INPUT STRING aaabbbccc when n=3

S->A

->aABc

->aaABcBc (A->aABc)

->aaabcBcBc (A->abc)

->aaabBccBc (cB->Bc)

->aaabBcBcc (cB->Bc)

->aaabbcBcc (bB->bb)

->aaabbBccc (cB->Bc)

->aaabbbccc (bB->bb)

There is a solution which is context-sensitive.

$$G = (N,T,P,S)$$ $$N=\{S,A,B,C\}$$ $$T=\{a,b,c\}$$ $$S=\mbox{start symbol}$$ Production Rules(P):

1. $S \rightarrow aAB\ |\ A\ |\ \epsilon$
2. $A \rightarrow aAB\ |\ aB$
3. $B \rightarrow bC$
4. $Cb \rightarrow bC$
5. $C \rightarrow cC\ |\ c$
• please notify, if something wrong. – Harshil Gupta Aug 10 '15 at 14:52
• Welcome to Computer Science Stack Exchange. Please read cs.stackexchange.com/tour, if you have not yet done so. --- --- You do not need $S→aAB$, since you have $A→aAB$. But this grammar does not work because you have no obligation to apply rule 4, so that the $b$ and $c$ can remain mixed. You need one more trick. – babou Aug 10 '15 at 16:02
• I think the obligation of rule 4 is rule 5. Is it ? – Harshil Gupta Jun 10 '17 at 20:20
• I do not understand your last comment. This said, I have not looked at this for 2 years, and I do not really wish to dive into it again. – babou Jun 10 '17 at 20:51
• To much time has been passed so, that's ok. – Harshil Gupta Jun 11 '17 at 19:36

Grammar for the language $$\{a^nb^nc^n \mid n\ge1\}$$:
$$S\to aSBC\mid aBC$$
$$CB\to BC$$
$$aB\to ab$$
$$bB\to bb$$
$$bC\to bc$$
$$cC\to cc$$

• That's a different language than the one the OP is interested in. Furthermore, I'd bet they're interested in context-free grammars. – Yuval Filmus Oct 29 '18 at 6:58