Combinatorics problem involving a regular expression

Question

If formal definition of a regular expression is required, please comment and I'll add it.

I was given the assignment of determining how many words of length $n$ can be produced from a regular expression (or equivalently - how many words of length $n$ are there in the regular language that corresponds to the regular expression).

So let $\sum=\{0,1,2\}$ be our alphabet.
The regular expression is: $(01^*|10^*)(0^+|1^+)(0|1|2)^*$, and I need to determine how many words of length $n$ can be produced from it.

I wrote my answer but later found out it was wrong.
What really bugs me is that I can't seem to find what's wrong with it, and I would really appreciate some help and guidance.

So I first had to use some identities, because I had no idea what to make of it...

$(01^*|10^*)(0^+|1^+)(0|1|2)^*=(01^*|10^*)(00^*|11^*)(0|1|2)^*=(01^*|10^*)(0|1)(0|1|2)^*=(01^*|10^*)(0|1)\sum^*=(01^*|10^*)(0\sum^*|1\sum^*)=(01^*0\sum^*|01^*1\sum^*|10^*0\sum^*|10^*1\sum^*)$

And now it is easier to see that every word of length $n$ must have one of the following patterns:

$0\hspace{1 mm}1^k\hspace{1 mm}0\hspace{1 mm}\sum^m$
$0\hspace{1 mm}1^k\hspace{1 mm}1\hspace{1 mm}\sum^m$
$1\hspace{1 mm}0^k\hspace{1 mm}1\hspace{1 mm}\sum^m$
$1\hspace{1 mm}0^k\hspace{1 mm}0\hspace{1 mm}\sum^m$

Where $0\leq k,m\leq n-2$ and $k+m=n-2$.
So the total number of words of length $n$ is: $4\cdot(\sum_{m=0}^{n-2}3^m)$

Where's the flaw in this answer, and how else should I have approached this?

Answer 1

Calling your four patterns $A_k,B_k,C_k,D_k$ respectively, note that $01101$ is in both $A_2$ and $B_1$, so you are over counting.

You can fix your solution though using inclusion-exclusion

Answer 2

Thanks to @Callus for helping me figure out the flaw in my solution.
After some adjustments, I figured out how to solve it.
My revised answer does not involve inclusion-exclusion (but if anyone is kind enough to write his or her solution using inclusion-exclusion I'll much appreciate it [I will also tag his or her answer as 'answer', of course]).
Here it is:

$(01^*|10^*)(0^+|1^+)(0|1|2)^*=(01^*|10^*)(00^*|11^*)\sum^*=$ $(01^*|10^*)(0|1)\sum^*=(01^*0|01^*1|10^*0|10^*1)\sum^*=$
$(01^*0|011^*|100^*|10^*1)\sum^*=(01^*0|01|10|10^*1)\sum^*=(00|01|10|11)\sum^*$

The last transition is justified by the fact that the case where $01^k0\sum^*$ for $k>0$ is already included in the pattern $01|\sum^*$, the same goes for the case where $10^k1\sum^*$ for $k>0$, which already included in the pattern $10|\sum^*$.

It is now easy to see that there are $4\cdot 3^{n-2}$ words of length $n$.