I have an language of Σ = {0,1} and need to find the the regular expression of:

  1. Set of strings that have no pairs of consecutive zeros
  2. Set of strings that contain at most one zero

For the first one I tried

(01 + 1)*.(0)

For the second I tried


I kind of feel that this is wrong. I would appreciate your help.

  • $\begingroup$ Can you add a list of samples of what should be matched and what should not please? $\endgroup$ – Jorge Campos May 1 '19 at 16:09
  • $\begingroup$ It's an homework give by the university, it only mentions what i wrote in the question to make the regular expression based on the lanugage $\endgroup$ – Mazhar Khan May 1 '19 at 16:12
  • $\begingroup$ The regular expression for the language L = {0,1} is 0|1, but that's a different language than the two languages you describe in the question. Did you maybe mean "languages over the alphabet Σ = {0, 1}"? $\endgroup$ – sepp2k May 1 '19 at 16:14
  • 1
    $\begingroup$ The first one looks right, but I'm not sure about what the syntax .(0) means in the formalism you are using. It should refer to an optional zero, is that right? Usually written [0] or 0? or (|0) or (ε + 0). $\endgroup$ – Bergi May 1 '19 at 16:40
  • 2
    $\begingroup$ The second one is wrong. Your regex (1*0) matches exactly one zero, and only in the end. $\endgroup$ – Bergi May 1 '19 at 16:40

Your first solution seems fine except for the fact that the last zero has to be optional and that the string 0 has to be accepted as well.

For the second one, you could use 1*0?1*, because if a string contains a zero, it can be anywhere. In (1*0), there has to be exactly one zero and it has to be at the last position.

| cite | improve this answer | |

Here are the regular expressions for the two points,

For Set of strings that have no pairs of consecutive zeros you can use,


Regex Demo 1

For Set of strings that contain at most one zero you can use,


Regex Demo 2

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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