2
$\begingroup$

I made a right-linear grammar from a regular expression:

The alphabet is:

$Σ = \{a, b, c\} $

Regular expression:

$r = cc^{*}(ba)^{*}bb$

My solution, it seems a little too short like I'm leaving something out. Maybe someone can see where I went wrong on the right-linearity:

$ S \to cA $

$ A \to b a A | B | cA $

$ B \to bb $

$\endgroup$
  • $\begingroup$ did you mean $cc^*(ba)^*bb$ ? $\endgroup$ – Subhayan Oct 6 '13 at 3:42
  • $\begingroup$ Your solution generates $c(c+ba)^*bb$. $\endgroup$ – Yuval Filmus Oct 6 '13 at 3:47
3
$\begingroup$

$A \rightarrow ba \mid A \mid B \mid cA$

under this $bababaccc$ is also legal


You could try something like this...

$S \rightarrow cS|cA$

$A \rightarrow baA|B$

$B \rightarrow bb$

$\endgroup$
  • $\begingroup$ +1 thanks, I also fixed the star-closure that mentioned above. I wasn't sure about the $S \to cS | cA$ because the recursive $S$ seemed like it wouldn't be in syntax for right-linearity. But it makes sense tho. $\endgroup$ – stackuser Oct 6 '13 at 3:58

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.