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$
$\endgroup$
4
-
$\begingroup$ just add that single $1$ to your expression as an alternative to what you already have! $\endgroup$– Hendrik JanApr 2, 2013 at 23:38
-
$\begingroup$ I had thought of that, but I worried that it would not be the minimum possible. Thanks. $\endgroup$– MirranaApr 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$– Hendrik JanApr 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
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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$.
answered Apr 3, 2013 at 7:42
-
$\begingroup$ sorry for going off-topic here, which tool you have used to draw this beautiful looking DFA ? $\endgroup$– aviApr 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