# Finding a correct regex for the strings with at least two $0s$

I am learning CFGs and before that I've made a RE (Regular Expression) for the language of "all strings with at least two $$0$$'s over the alphabet $$\Sigma = \{0,1\}$$."

I made this: $$(0+1)^*0(0+1)^*0(0+1)^*$$

I checked the answer and it is: $$1^*01^*0(0+1)^*$$

Is there any difference between the two?

If mine is also correct, what should be the CFG for it?

## 1 Answer

Your answer is also correct. Regular languages do not have unique regexes. For example, $$0^\ast$$, $$0^\ast 0^\ast$$, and $$0^\ast 0^\ast 0^\ast$$ are different regexes, all representing the language of strings containing only zeroes.

The problem of deciding whether two regexes are equivalent (i.e., whether they represent the same language) is actually very hard, as mentioned in this answer. (Spoiler: it is $$\mathbf{PSPACE}$$-complete.)

As to your other question (regarding a CFG for the language), here is a hint: divide and conquer. Split the regex in multiple "chunks" and try to generate each chunk separately, then pack everything together with the grammar's start symbol.