Find a CFG for $(0 \cup10)^*(1+\epsilon)$

39 Views Asked by At

I am looking for an CFG generating the following language: $(0 \cup10)^*(1+\epsilon)$. First of all I looked which elements are in the language and found the following: $$(0 \cup 10)^*(1 + \epsilon)=\{\epsilon, 0,1, 0 \dots 0, 0\dots 01,10 \dots 10,10 \dots,101 \}$$ The dots should represent an arbitrary number of $0$ or $10$ i.e. Now I had the idea to define the following: $$S \to \epsilon \,\vert \, 0 \,\vert \,1 \,\vert B \,\vert \, C$$ $$B \to 0A$$ $$ A \to 0B \,\vert \, 1$$ $$C \to 10D$$ $$D \to 10C \,\vert \, 1$$ Can this be an option or do I missed something? Are the furthermore an "algorithm" to find such a CFL? Or should I try like I did... Many thanks for your help!