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 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.