2
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ @LorenzoDematté I do not have 1000 rep in the other service. But thank you. $\endgroup$
    – Yoda
    Commented May 21, 2013 at 8:24
  • $\begingroup$ You can ask questions without offering a bounty, it's not mandatory... $\endgroup$
    – Lorenzo Dematté
    Commented May 21, 2013 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
    Commented May 21, 2013 at 8:30
  • 1
    $\begingroup$ No need to offer 1000 RP for this question, just wait for 5 mins.. $\endgroup$
    – Grijesh Chauhan
    Commented May 21, 2013 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
    Commented May 21, 2013 at 8:56

5 Answers 5

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Gilles thanks for the edit. I should have read again before posting ;) $\endgroup$
    – wece
    Commented May 21, 2013 at 9:08
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ your grammar is simple and correct, I didn't notice first. Thanks! $\endgroup$
    – Grijesh Chauhan
    Commented May 21, 2013 at 9:00
  • 1
    $\begingroup$ I don't think this grammar is correct. How do you produce "cbca" with it? $\endgroup$
    – svinja
    Commented May 21, 2013 at 11:12
  • $\begingroup$ @svinja: you're right. I corrected it to generate S → cT → cTa → cbTca → cbca. $\endgroup$
    – Fred Foo
    Commented May 21, 2013 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
    Commented May 21, 2013 at 19:43
2
$\begingroup$

The correct grammar is:

C -> ScS //starting from C
S -> SaS | ScS | ScSbS | SbScS | ε
Improve this answer
$\endgroup$
5
  • 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
    Commented May 21, 2013 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
    Commented May 21, 2013 at 9:58
  • $\begingroup$ @GrijeshChauhan forgot to rewrite upper line from the paper. Now it is corrected. $\endgroup$
    – Yoda
    Commented May 21, 2013 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
    Commented May 21, 2013 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
    Commented May 22, 2013 at 4:44
1
$\begingroup$

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:

your grammar: 

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

produces bbacb ad follows: 

S --> bS --> bbS --> bbaS --> bbacb
Improve this answer
$\endgroup$
8
  • $\begingroup$ This produces ab by S --> ABC --> aBC --> abC --> ab. $\endgroup$
    – Fred Foo
    Commented May 21, 2013 at 8:47
  • $\begingroup$ @larsmans ok... $\endgroup$
    – Grijesh Chauhan
    Commented May 21, 2013 at 8:47
  • $\begingroup$ I think you swapped b and c. $\endgroup$
    – Fred Foo
    Commented May 21, 2013 at 8:53
  • $\begingroup$ @larsmans yes that why I confusing while re-writing for your fist comment Thanks $\endgroup$
    – Grijesh Chauhan
    Commented May 21, 2013 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
    Commented May 21, 2013 at 9:04
-2
$\begingroup$

$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$

Improve this answer
$\endgroup$
1
  • 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
    Commented Dec 7, 2013 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.