1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ The language is not context free. And it's certainly not regular. What does "of a finite automata" mean? $\endgroup$ Sep 27, 2014 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, 2014 at 8:09

4 Answers 4

0
$\begingroup$

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 | ε
$\endgroup$
2
  • 1
    $\begingroup$ can you show me some guidelines on deriving such grammars? $\endgroup$
    – Amen
    Sep 28, 2014 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, 2014 at 16:43
3
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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$
$\endgroup$
5
  • $\begingroup$ please notify, if something wrong. $\endgroup$ Aug 10, 2015 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, 2015 at 16:02
  • $\begingroup$ I think the obligation of rule 4 is rule 5. Is it ? $\endgroup$ Jun 10, 2017 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, 2017 at 20:51
  • $\begingroup$ To much time has been passed so, that's ok. $\endgroup$ Jun 11, 2017 at 19:36
-1
$\begingroup$

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$

$\endgroup$
1
  • 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$ Oct 29, 2018 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.