# Regular grammar with at most one c

I am attempting to make a regular grammar over alphabet {a, b, c} where there is at most one c. So far, I have the regular expression ((a|b)*|c)(a|b)* but am unsure where to go from here; my previous attempts have ended up allowing multiple c's.

The solution I has gives (N={s,t}, T={a,b,c}, s, R), s→є, s→as, s→bs, s→ct, t→at, t→bt, t→є, however I do not see how this limits the number of c's generated to at most 1.

## migrated from stackoverflow.comMar 10 at 18:49

This question came from our site for professional and enthusiast programmers.

• Your regular expression doesn't match $aca$. – David Richerby Mar 10 at 20:06
• Seems you want something like prefix c[opt] suffix where prefix and suffix are (a|b)*. It's clear that neither prefix nor suffix contain a c so there can be at most one c from the optional c. – MSalters Mar 11 at 14:09

The rule s->ct can only be done once, becuase after that there is no more s left, and from t you cannot generate more s. Thus at most one c can be generated, because no other rule generates c.

Also the rest of the grammar looks fine.

• Could we apply s→as or s→bs then s→ct to obtain more s, then use these to obtain more c? – GregW Mar 10 at 18:56
• Sorry, I see my obvious mistake now. Thanks. – GregW Mar 10 at 19:03

You should reason: It contains no $$c$$ or one $$c$$.

If no $$c$$, it is $$(a|b)^*$$.

If exactly one $$c$$, it has "no c" before the lonely $$c$$ and "no c" after, i.e., $$(a|b)^*c(a|b)^*$$.

Join them to get $$(a|b)^*|(a|b)^*c(a|b)^*$$. Or you could factorize to give $$(a|b)^*(\epsilon|c(a|b)^*)$$.

• Although the regular expression in the question is wrong, the question itself is asking for a regular grammar, not a regular expression. – David Richerby Mar 15 at 15:32