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?

  • $\begingroup$ The language is not context free. And it's certainly not regular. What does "of a finite automata" mean? $\endgroup$ – Karolis Juodelė Sep 27 '14 at 8:07
  • 2
    $\begingroup$ 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 $\endgroup$ – 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 | ε
  • 1
    $\begingroup$ can you show me some guidelines on deriving such grammars? $\endgroup$ – Amen Sep 28 '14 at 16:19
  • 1
    $\begingroup$ 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. $\endgroup$ – d'alar'cop Sep 28 '14 at 16:43

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





FOR EXAMPLE:INPUT STRING aaabbbccc when n=3



->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$
  • $\begingroup$ please notify, if something wrong. $\endgroup$ – Harshil Gupta Aug 10 '15 at 14:52
  • $\begingroup$ 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. $\endgroup$ – babou Aug 10 '15 at 16:02
  • $\begingroup$ I think the obligation of rule 4 is rule 5. Is it ? $\endgroup$ – Harshil Gupta Jun 10 '17 at 20:20
  • $\begingroup$ 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. $\endgroup$ – babou Jun 10 '17 at 20:51
  • $\begingroup$ To much time has been passed so, that's ok. $\endgroup$ – 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$

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

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.