patternMinor
Star notation for context-free language alphabet?
Viewed 0 times
alphabetstarfreelanguagenotationforcontext
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#138366, answer score: 2
Revisions (0)
No revisions yet.