I have to write a regular expression that accepts any odd binary number not preceded by a 0. the best I can come up with is $1(0\cup1)^*1$, but that doesn't match just 1. The best it matches is 11.

  • $\begingroup$ just add that single $1$ to your expression as an alternative to what you already have! $\endgroup$ Apr 2, 2013 at 23:38
  • $\begingroup$ I had thought of that, but I worried that it would not be the minimum possible. Thanks. $\endgroup$
    – Mirrana
    Apr 2, 2013 at 23:42
  • 2
    $\begingroup$ Minimal length is not always better than "elegant", or "easy to understand". A short alternative could be $1(0^*1)^*$. That one has nested stars, which is more complex in some respects. $\endgroup$ Apr 2, 2013 at 23:49
  • $\begingroup$ Obligatory hint: build an NFA and convert. Also, any question should contain, well, a question. $\endgroup$
    – Raphael
    Apr 3, 2013 at 7:15

1 Answer 1


First you might just add that single $1$ to your expression as an alternative to what you already have. One obtains $1 \cup 1(0\cup 1)^*1$.

An alternative is $1(0^*1)^*$. That one is shorter, but not necessarily better.

Actually that expression I obtained by starting with the FSA below, and realizing that the rightmost two states could be replaced by iterating $0^*1$.

enter image description here

  • $\begingroup$ sorry for going off-topic here, which tool you have used to draw this beautiful looking DFA ? $\endgroup$
    – avi
    Apr 3, 2013 at 8:05
  • 1
    $\begingroup$ The diagram was made in $\LaTeX$ using the package GasTeX $\endgroup$ Apr 3, 2013 at 8:36
  • 2
    $\begingroup$ @avi I have been using this script of mine with TikZ. $\endgroup$
    – Raphael
    Apr 3, 2013 at 11:15

Your Answer

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

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