I want to construct a grammar for the following regular expression: $1^*0^*1(1+0)^*$. I did it the following way:

$S \rightarrow AB1C$

$A \rightarrow 1A | \epsilon$

$B \rightarrow 0B | \epsilon$

$C \rightarrow 0C|1C| \epsilon$

Is it correct?

  • $\begingroup$ Well, almost, the last line should be $C\to 0C\,|\,1C\,|\,\epsilon$. $\endgroup$
    – Berci
    Mar 6, 2022 at 21:14
  • $\begingroup$ right, I just forgot that. $\endgroup$
    – Papa
    Mar 6, 2022 at 21:27
  • $\begingroup$ @Berci I have posted another question if you d like to help math.stackexchange.com/questions/4397537/… $\endgroup$
    – Papa
    Mar 6, 2022 at 21:38


You must log in to answer this question.