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$ – Hendrik Jan Apr 2 '13 at 23:38
  • $\begingroup$ I had thought of that, but I worried that it would not be the minimum possible. Thanks. $\endgroup$ – agent154 Apr 2 '13 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$ – Hendrik Jan Apr 2 '13 at 23:49
  • $\begingroup$ Obligatory hint: build an NFA and convert. Also, any question should contain, well, a question. $\endgroup$ – Raphael Apr 3 '13 at 7:15

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 '13 at 8:05
  • 1
    $\begingroup$ The diagram was made in $\LaTeX$ using the package GasTeX $\endgroup$ – Hendrik Jan Apr 3 '13 at 8:36
  • 2
    $\begingroup$ @avi I have been using this script of mine with TikZ. $\endgroup$ – Raphael Apr 3 '13 at 11:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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