0
$\begingroup$

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.

$\endgroup$

migrated from stackoverflow.com Mar 10 at 18:49

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

  • $\begingroup$ Your regular expression doesn't match $aca$. $\endgroup$ – David Richerby Mar 10 at 20:06
  • $\begingroup$ 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. $\endgroup$ – MSalters Mar 11 at 14:09
0
$\begingroup$

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.

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

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)^*)$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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