How to write a grammar that every 0 is followed by at lease one 1 in Discrete math

Question

How to write a grammar that every $0$ is followed by at lease one $1$. I can't quit figure it out. By the way, what does $S\rightarrow(0?1)$* do? especially the question mark? Thank you !!

Answer 1

Here is a context-free grammar for the language you describe, assuming the alphabet is $\{0,1\}$: \begin{gather} S \rightarrow ST1\ |\ \epsilon\\ T \rightarrow 0\ |\ \epsilon\\ \end{gather}

This allows you to recursively build any string, by beginning with the variable $S$. Variable $S$ can be replaced with an empty string, or $S$ followed by $T$ followed by $1$. It's easy to see that if the string does contain a $0$, that $0$ will be directly followed by a $1$. Note that $\epsilon$ represents the empty string.

This context-free-grammar corresponds to the regular expression L = (0?1)*. The ? mark means that there is at most one occurrence of the previous character (zero or one 0s). The * operator means that the expression within parentheses is repeated zero or more times. This regular expression describes exactly what you did in your question: the language of strings for which all occurrences of 0s are followed by at least one 1.