Regular expression of alternating smaller and bigger digits

Question

How would i go about making a regular expression that alternates between smaller and bigger numbers for an alphabet {0,1,2,3} such as "01032312" or "230102132"

Answer 1

As @BrianO said I think the best way to go is to build a NFA (which is not too hard) and then translate it to a regular expression.

However, if you don't know the translation from NFA to regular expression (I strongly advise you to take a look at it), or if you don't want to use it here is an attempt to directly build the regular expression.

First consider the problem for the alphabet $\{0,1\}$. The only possibility is to alternate between 0 and 1. So the regular expression is $(01)^*$.

Now consider $\{0,1,2\}$. The 2 plays a key role. First it cannot appear in odd position otherwise there are no bigger number to follow. Second, whenever a 2 is in even position there are no restriction on the next letter (apart from: it is not a 2), it is the same as the beginning of the word.

So the regular expression $((0.1)^*.0.2+1.2)^*$ matches your language:

1. After a $0$ in odd position there can be a $1$ or a $2$
2. After a $1$ in odd position there can only be a $2$
3. The are no $2$ in odd position
4. After a $2$ in even position there can be a $0$ or a $1$
5. After a $1$ in even position there can only be a $0$
6. The are no $0$ in even position

Lets get a look at $\{0,1,2,3\}$ now. With the same idea we get:

$$ ((((0.1)^*.0.2)+1.2)^*(03+13)+23)^* $$