Size of a Language?

297 Views Asked by At

I am trying to understand the model answer for the following question

Given some alphabet $Σ$ and $w ∈ Σ^∗$, the number of string $x ∈ Σ^∗$ are there such that $|x| ≤ |w|$

Solution: $\sum_{i=0}^{|w|} |Σ|^i $

lets assume $|Σ| = 10$ and $|w| = 2$. Does this mean $\sum_{i=0}^{2} (|10|^0 + |10|^1 +|10|^2) $ or does this mean $\sum_{i=0}^{2} (|1|^0 + |2|^1 +|3|^2)$ (the size of the language at that index)

furthermore what is $x$ and $w$ is it a string? a set of strings?

1

There are 1 best solutions below

0
On BEST ANSWER

Both $x$ and $w$ are defined as $\in \Sigma^*$. Thus they are elements of the set of all strings over the alphabet $\Sigma$, which means they are strings.

Thus $|w|$ is the length of the string, not the cardinality of a set.

As @rici has already stated in the comment, the solution means in your example case $\sum_{i=0}^2 (10^i)$ which is $10^0 + 10^1 + 10^2$ (no cardinality for the number 10).

You have $10^0=1$ strings of length zero, the unique empty string.

You have $10^1=10$ strings of length one, those consisting of one of the possible letters.

You have $10^2=100$ strings of length two, because you have ten options for the first position and ten for the second.