1

w ∈ C*

"Generate a Grammar such that w contains strings of as followed by bs followed by cs such that there are either a different number of as and bs or a different number of bs and cs or both"

C= {a,b,c}

I am trying to do both. I'm having difficulties generating grammars, but I have understood that I should just write down some strings and from there try to generate some rules.

some of my strings are aabc, abbc, abcc, aabbbcc

I have produced the following rules:

$S\rightarrow aSbScS$

$S\rightarrow AS$

$S\rightarrow SB$

$S\rightarrow SC$

$S\rightarrow e$

$A\rightarrow a$

$B\rightarrow b$

$C\rightarrow c$

Did I do this right? And if not, what did I do wrong?

I am a language student and am trying to make my brain get used to such thinking, but I am somehow struggling with this.

Thank you.

koby
  • 47

1 Answers1

1

Look at it like this, at least one of the following has to be true:

  1. the number of $a$'s is larger than the number of $b$'s
  2. the number of $b$'s is larger than the number of $a$'s
  3. the number of $b$'s is larger than the number of $c$'s
  4. the number of $c$'s is larger than the number of $b$'s

So we can make a grammar for each of these, and then simply combine them.

A grammar for the first condition looks like this:

\begin{align*} S_1&\to aXC\\ X&\to aX \mid aXb\mid\varepsilon\\ C&\to cC\mid\varepsilon \end{align*}

The first rule means there is at least one $a$ in the string, which is necessary. The second rule means that either we can add $a$'s to the front, or we can add both an $a$ to the front and a $b$ to the middle. Finally, the number of $c$'s doesn't matter.

Now we can make similar grammars with starting variables $S_2$, $S_3$ and $S_4$ for the other three conditions above, and then we can combine these with the rule \begin{align*} S\to S_1\mid S_2\mid S_3\mid S_4 \end{align*}

Vsotvep
  • 6,123
  • Oh I see, that's a good way. – koby Feb 23 '20 at 16:50
  • Oh I see, that's a good way.

    For now I have:

    S2= aXC X=Xb X=aXb X=e C=cC C=e

    S3= AbX X=bX X=bXc X=e A=Aa A=e

    S4=AbXc X=Xc X=e A=Aa A=e

    Are all four of these correct? :)

     – koby Feb 23 '20 at 16:56
  • Not entirely, there's an error in your S2 rule, and an error in your S4 rule, as well as a missing X rule in the S4 case. Finally, you can't use X for each of the rules, but you need new variables since otherwise you can't combine the grammars later: they would cross-contaminate each other – Vsotvep Feb 23 '20 at 18:32