[Solved]: Regular expression for odd binary numbers without leading zeros

Problem Detail: 

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.

Asked By : agent154

Answered By : Hendrik Jan

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10983