# Star notation for context-free language alphabet?

I noticed that some "design-the-grammar" problems say verbally

Alphabet is $$\mathbf{\{0,1\}}$$.

$$\{w \mid w \text{ contains at least three 1s}\}$$

and some problems list it as

$$\{ w ∈ \mathbf{\{0,1\}}^* \mid w \text{ contains at least three 1s} \}$$

So, my question is: Is the in-line notation with the asterisk star '*' (as in "$$\{0,1\}^*$$") equivalent to saying "alphabet is $$\{0,1\}$$", or are those alphabets different?

It is equivalent (usually, otherwise it would be explicitly stated).

The "star-operation" is called a Kleene-star, and it is an operation that basically takes the set and creats the set of all combinations of items from the original set. In the example of $$\{0,1\}$$, we would have that $$\{0,1\}^*=\{0^{k_1}1^{k_2}0^{k_3}\dots\mid k_1,k_2,\dots\in \mathbb{N}\}$$, and intuitively speaking, this is the set of all words created from the alphabet $$\{0,1\}$$. This obviously is also true for any other alphabet $$\Sigma$$ you would want.

There are two different ways to define languages:

• A language over an alphabet $$\Sigma$$ is a collection of words over $$\Sigma$$.
• A language is a collection of words.

While we often think of a language informally just as a collection of words (without an underlying alphabet), the usual definition of finite automata does specify an alphabet, and so the language of an automaton always has an alphabet associated with it.

When we write $$L = \{ w \in \{0,1\}^* \mid \cdots \}$$, we mean that $$L$$ is a language over the alphabet $$\{0,1\}$$ consisting of all words such that "$$\cdots$$". This is just a conventional way to describe the alphabet that the language is defined over.

Wikipedia implicitly uses the first definition. If we want to make the definition more formal, we would define a language as a pair $$(L,\Sigma)$$, where $$\Sigma$$ is an alphabet (a non-empty finite set) and $$L$$ is a subset of $$\Sigma^*$$ (the set of all words over $$\Sigma$$).

While formally a language is a pair $$(L,\Sigma)$$, often the alphabet $$\Sigma$$ is understood from context, and we only talk about $$L$$. This is the same convention used in abstract algebra, where the underlying set stands metonymically for the entire algebraic object.

Given just a collection of words $$L$$, it is impossible to completely reconstruct $$\Sigma$$. For example, the empty language can be viewed as a language over any alphabet, the language $$\{0^n : n \geq 0\}$$ can be viewed as a language over any alphabet containing the symbol $$0$$, and so on. The notation $$L = \{w \in \Sigma^* \mid \cdots\}$$ usually suggests that the underlying alphabet is $$\Sigma$$, but it is not necessarily used consistently in this way.

In most circumstances, not much is lost by not specifying the underlying alphabet explicitly. I suggest ignoring such niceties whenever possible.

The other answer gives, I think, a slightly non-standard definition of the Kleene-star which doesn't emphasise that $$\{0,1\}^*$$ is the set of all finite strings whose characters are all $$0$$ or $$1$$.

For an alphabet $$\Sigma$$, you can define $$\Sigma^*:=\Sigma^0\cup\Sigma^1\cup\Sigma^2\cup\cdots$$, where $$\Sigma^i$$ is the set of strings of length $$i$$ with characters from $$\Sigma$$. (Formally, $$\Sigma^0:=\{\epsilon\}$$, where $$\epsilon$$ is the empty string, and for each $$i\in \mathbb{N}$$ we define $$\Sigma^{i+1}:=\{wx:w\in\Sigma^i\land x\in\Sigma\}$$.) Notice that the empty string, $$\epsilon$$, is contained within the set as it is in $$\Sigma^0$$.

If you've got a mathematics background, you might think of this as the "free monoid over $$\Sigma$$".

In the case you give, yes, the two definitions are therefore the same.

Formally, the version of

$$\{ w ∈ \mathbf{\{0,1\}}^* \mid w \text{ contains at least three 1s} \}$$

does not really say anything about the alphabet of the language. It might be {0,1}, but might also be bigger. Only the (part of the) alphabet, from which the desired strings are constructed is specified.

So while the language specified is the same, its complement might differ. Over an alphabet {0,1,2} the complement would include all strings containing a 2, while over the alphabet {0,1} these do not even exist.

Thus the two statements are not really equivalent in general, although in a context, where the alphabet is already set to {0,1} they are.