4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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