Constructing regular grammar

Question

I'm trying to make a regular grammar for this language:

$$ L = \{ a^ncb^m(cc)^p : n\ge 1, m\le 1, p\ge 0\} $$

Where the alphabet is $ \Sigma = \{a,b,c\}$

It seemed like right-linear. This may be disastrously wrong, but here's how I started:

$S \to aA$

$A \to aA | cB $

$B \to bC | C $

$C \to cD |$ $\lambda$

$D \to cC$

EDIT: Corrected for the errors pointed out.

Answer 1

You’ve a couple of problems right off the bat: your grammar can generate at most one $a$, and it can generate the word $a$, which isn’t in $L$. You can solve both of these problems by replacing $A\to cB\mid\lambda$ with $A\to aA\mid cB$: with those and the initial production $S\to aA$ you can generate all strings of the form $a^ncB$ with $n\ge 1$.

You’re in trouble again with the $B$ productions: $B\to bB$ allows you to generate as long a string of $b$’s as you like, when you’re supposed to generate at most one $b$. You needed something like this for the $a$’s; you don’t want it for the $b$’s. You don’t need the $\lambda$ production, either: you can take care of that at the $C$ stage. What you need here is $B\to bC\mid C$: generate at most one $b$ and shift to generating $cc$’s. $C\to ccC\mid\lambda$ is then fine, provided that your definition of regular grammar is what many refer to as an extended regular grammar. This is a right linear grammar, but note that right linearity is a property of the grammar, not of the language.

If you’re required to use a regular grammar in the strict sense of the term, you need to replace $C\to ccC$ with regular productions, e.g., $C\to cD\mid\lambda$ and $D\to cC$. (Note that you do not want a $\lambda$ production for $D$, since you don’t want to stop with an odd number of final $c$’s.)

Answer 2

Well, your grammar isn't exactly regular according to the most common definitions: $C\to ccC$ is not a regular production.

It doesn't quite generate your language either, since we have $$ \underline S \to a\underline A \to a $$ but $a$ isn't in $L$.

On the other hand it fails to generate $aaaaaac$, which should be in $L$.

And it generates $acbbbbbbb$, which it shouldn't -- perhaps you've overlooked that the condition was $m\le 1$, not $m\ge 0$.

---

"It seemed like right-linear" looks like you're misunderstanding something. Right-linearity is a property of grammars, not of languages. At the point where you say that, you have only a language and not yet a grammar.

---

Since a right-linear grammar is basically the same thing as an NFA, perhaps it would be easier to start by drawing an NFA for the language and then write it down in grammar form afterwards?