Exactly as stated in the subject. I look for grammar which use letters $a, b ,c$ that numbers of letters $c$ is greater than number of letters $b$.

Example: $acbccba$ is generated by the grammar.

I thought about:

$S \rightarrow aS \mid bS \mid SCS$

$ C \rightarrow cb \mid ca$

but not sure if it works. Could you help me, please.

  • $\begingroup$ @LorenzoDematté I do not have 1000 rep in the other service. But thank you. $\endgroup$ – Yoda May 21 '13 at 8:24
  • $\begingroup$ You can ask questions without offering a bounty, it's not mandatory... $\endgroup$ – Lorenzo Dematté May 21 '13 at 8:27
  • 1
    $\begingroup$ So the grammar must contain all words with all combinations of a, b and c, that satisfy the "greater than" constraint? $\endgroup$ – cyroxx May 21 '13 at 8:30
  • 1
    $\begingroup$ No need to offer 1000 RP for this question, just wait for 5 mins.. $\endgroup$ – Grijesh Chauhan May 21 '13 at 8:38
  • 3
    $\begingroup$ I don't think it's a good idea to advertise a bounty in the question title and body. Actually, I edited out these advertisements. $\endgroup$ – Daniel Daranas May 21 '13 at 8:56

Your grammar never accepts a word since you can't make the $S$ disappear.

If you want to create more $c$ than $b$ you just have to make sure that when you create a $b$ you create a $c$ with it (but be careful they don't need to be side to side). You can also generate as much $a$ or $c$ as you want.

If you need more indication please ask.

  • $\begingroup$ @Gilles thanks for the edit. I should have read again before posting ;) $\endgroup$ – wece May 21 '13 at 9:08

Lowercase letters are terminals, uppercase nonterminals.

S → TcT

T → ε

T → aT
T → Ta

T → Tc
T → cT

T → bTc
T → cTb

The S rule ensures that there is at least one c. T then generates any string of (abc)* where every b is balanced by a c.

  • 1
    $\begingroup$ your grammar is simple and correct, I didn't notice first. Thanks! $\endgroup$ – Grijesh Chauhan May 21 '13 at 9:00
  • 1
    $\begingroup$ I don't think this grammar is correct. How do you produce "cbca" with it? $\endgroup$ – svinja May 21 '13 at 11:12
  • $\begingroup$ @svinja: you're right. I corrected it to generate S → cT → cTa → cbTca → cbca. $\endgroup$ – Fred Foo May 21 '13 at 11:38
  • 1
    $\begingroup$ The solution alone is not very helpful. How did you get there? How can the OP solve similar problems? $\endgroup$ – Raphael May 21 '13 at 19:43

The correct grammar is:

C -> ScS //starting from C
S -> SaS | ScS | ScSbS | SbScS | ε
  • 1
    $\begingroup$ s --> SaS --> εaε --> a in string a, numbersof(b) == numberof(c)==0 , your grammar is wrong according to language, there is many other cases $\endgroup$ – Grijesh Chauhan May 21 '13 at 9:34
  • 1
    $\begingroup$ An infinite number of them, in fact, since a* is a subset of this grammar's language. $\endgroup$ – Fred Foo May 21 '13 at 9:58
  • $\begingroup$ @GrijeshChauhan forgot to rewrite upper line from the paper. Now it is corrected. $\endgroup$ – Yoda May 21 '13 at 11:30
  • 1
    $\begingroup$ The solution alone is not very helpful. How did you get there? How can the OP solve similar problems? (By the way, "the" correct grammar is not unique.) $\endgroup$ – Raphael May 21 '13 at 19:43
  • $\begingroup$ @Raphael I think the solution is quite simple, it start with some (or at-least one) c, (start variable is C), then via S always insert either a, c, but whenever b is added a c is also added...Its good solution $\endgroup$ – Grijesh Chauhan May 22 '13 at 4:44

Whenever you add a b also add a c and add some(atleat one extra c) whereas on a language do not impose any constraint so feel free a add a any numbers of time (even 0), any where in language string. A Context Free Grammar is possible for your language.

S  --> cS | Sc | T

T  -->  ABC | BAC | BCA | ACB | CAB | CBA 

C  -->  cC  | c    

B  -->  b   | ^

A  -->  aA  | ^


your grammar is not correct, because you can generate a string in which *b*s are more then *c*s, e.g:

your grammar:

S --> aS | bS |SCS    
C --> cb | ca

produces bbacb ad follows:

S --> bS --> bbS --> bbaS --> bbacb
  • $\begingroup$ This produces ab by S --> ABC --> aBC --> abC --> ab. $\endgroup$ – Fred Foo May 21 '13 at 8:47
  • $\begingroup$ @larsmans ok... $\endgroup$ – Grijesh Chauhan May 21 '13 at 8:47
  • $\begingroup$ I think you swapped b and c. $\endgroup$ – Fred Foo May 21 '13 at 8:53
  • $\begingroup$ @larsmans yes that why I confusing while re-writing for your fist comment Thanks $\endgroup$ – Grijesh Chauhan May 21 '13 at 8:54
  • 2
    $\begingroup$ I think this new version is correct (and maybe more easy to grasp than mine, so +1). I don't think you even need the S rules. $\endgroup$ – Fred Foo May 21 '13 at 9:04

$S \rightarrow SbS \mid bSS \mid SSb \mid b \mid bX \mid Xb$

$X \rightarrow bB \mid cA$

$A \rightarrow cX \mid cAA \mid b$

$B \rightarrow cX \mid bBB \mid b$

  • 1
    $\begingroup$ If I understand your notation here, you have a rule $S \rightarrow b$, and $S$ is the start symbol. This would allow the derivation of the string $b$, which is certainly not in the language. As a general note, this sort of answer is not really what this site is aiming to attract, try to make it clear, include explanations and put some effort into the formatting. Think of it like you're producing a (very short) lesson on the topic. I'll render your answer in TeX markup, take a look at it to see how to do it. $\endgroup$ – Luke Mathieson Dec 7 '13 at 12:44

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.