The number of elements in a set

Question

I have a small task, part of my homework, which tends to confuse me because of its simplicity. It makes me think that I am missing something.

I have to find the number of elements in the set {w | w ∈ L(R) and |w| = 10}. I have the regular expression R = (0 ∪ 1)∗0101∗.

My intuitive answer would be that the cardinality of this set is 10, because |w| = 10.

Is this correct and what am I missing if it is not?

thanks

Answer 1

The string is any pattern of length $n$ followed by $010$ followed by $10-n-3$ $1$'s, for $n$ in $(0,7)$.

This amounts to $1+2+4+8+16+32+64+128=255$ strings.

They are all different as for a given suffix ($0101*$) all prefixes are different, and all allowed suffixes are different.

Answer 2

This is incorrect. You seem to be misreading the set notation. In the notation

$$\{w \mid |w| = 10\}$$

$w$ is not the name of the set, $w$ is an element of the set. The notation means "the set of all $w$ such that $|w| = 10$". The set you're dealing with is "the set of all words in $L(R)$ which are of length $10$" (I assume $|w|$ is the length of the word $w$).

Answer 3

1. It is not correct.
2. You are missing the understanding of at least some parts of the definition. Your language contains all the $0-1$-strings that can start with anything, and end with the substring $010$ followed by an arbitrary number of ones. The expression $|w|$ (most probably) denotes the length of the string. For example, $|\{w | w \in L((0 \cup 1)^*), |w| = 10\}|$ would be rather something like $2^{10} = 1024$, and not $10$. Your example is more complicated than that.

You could count the strings as follows:

1. Notice that you can represent your set as disjoint union of sets of strings that have $0,\dots,7$. ones as suffix.
2. Count the ten-symbol strings that end with $k$ ones for $k=0,\dots,7$. Hint: look at my simpler example above.
3. Sum the cardinalities of the disjoint sets.

Notice that you don't need any "verbal handwaving" in your solution, you can just write down the cardinality that you want to find, and then transform the expression until you get a single integer:

\begin{align} |\{w|w\in L(R), |w| = 10\}| &= |\sqcup_{k=0}^7 L((0\cup 1)^{7-k}0101^{k})| \\ &= \sum_{k=0}^7 L((0\cup 1)^{7-k}0101^{k}) \\ &= \dots \end{align}

Here $x^n$ stands for "repeat exactly $n$ times", what one would usually write down as x{n} in code. Adjust it to your own notation.