# Grammar that numbers of letters c is greater than number of letters b

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.

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

$C \rightarrow cb \mid ca$

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

• @LorenzoDematté I do not have 1000 rep in the other service. But thank you.
– Yoda
May 21, 2013 at 8:24
• You can ask questions without offering a bounty, it's not mandatory...
– Lorenzo Dematté
May 21, 2013 at 8:27
• So the grammar must contain all words with all combinations of a, b and c, that satisfy the "greater than" constraint?
– cyroxx
May 21, 2013 at 8:30
• No need to offer 1000 RP for this question, just wait for 5 mins.. May 21, 2013 at 8:38
• 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.
– Daniel Daranas
May 21, 2013 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.

• @Gilles thanks for the edit. I should have read again before posting ;)
– wece
May 21, 2013 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.

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

The correct grammar is:

C -> ScS //starting from C
S -> SaS | ScS | ScSbS | SbScS | ε

• s --> SaS --> εaε --> a in string a, numbersof(b) == numberof(c)==0 , your grammar is wrong according to language, there is many other cases May 21, 2013 at 9:34
• An infinite number of them, in fact, since a* is a subset of this grammar's language. May 21, 2013 at 9:58
• @GrijeshChauhan forgot to rewrite upper line from the paper. Now it is corrected.
– Yoda
May 21, 2013 at 11:30
• 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.) May 21, 2013 at 19:43
• @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 May 22, 2013 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  | ^


Edit:

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

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


produces bbacb ad follows:

S --> bS --> bbS --> bbaS --> bbacb

• This produces ab by S --> ABC --> aBC --> abC --> ab. May 21, 2013 at 8:47
• @larsmans ok... May 21, 2013 at 8:47
• I think you swapped b and c. May 21, 2013 at 8:53
• @larsmans yes that why I confusing while re-writing for your fist comment Thanks May 21, 2013 at 8:54
• 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. May 21, 2013 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$

• 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. Dec 7, 2013 at 12:44