The set
[math]\href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*}
[/math] of
strings with
characters in the
alphabet [math]\href{/cs2800/wiki/index.php/%CE%A3}{Σ}
[/math] is
defined inductively by:
[math]\begin{align*}
x &\href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} \href{/cs2800/wiki/index.php/BNF}{::=} \href{/cs2800/wiki/index.php/%CE%95}{ε} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} \href{/cs2800/wiki/index.php?title=Xa&action=edit&redlink=1}{xa} \\
a &\href{/cs2800/wiki/index.php/%E2%88%88}{∈} Σ
\end{align*}
[/math]
[math]\href{/cs2800/wiki/index.php/%CE%95}{ε}
[/math] represents the empty string, while [math]\href{/cs2800/wiki/index.php?title=Xa&action=edit&redlink=1}{xa}
[/math] represents a string with 1 or more characters, starting with the shorter string [math]x
[/math] and ending in the character [math]a
[/math].
For example, if [math]\href{/cs2800/wiki/index.php/%CE%A3}{Σ} = \href{/cs2800/wiki/index.php/Enumerated_set}{\{0,1\}}
[/math], then [math]\href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} = \{ε, ε0, ε1, ε00, ε01, ε10, ε11, ε000, ε001, \dots\}
[/math]
To add further detail, we can show that [math]ε010 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*}
[/math] as follows:
- [math]\href{/cs2800/wiki/index.php/%CE%95}{ε} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*}
[/math] by rule 1
- [math]\href{/cs2800/wiki/index.php/%CE%95}{ε}0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*}
[/math] by rule 2, since [math]\href{/cs2800/wiki/index.php/%CE%95}{ε} \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*}
[/math] and [math]0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%CE%A3}{Σ}
[/math]
- [math]\href{/cs2800/wiki/index.php/%CE%95}{ε}01 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*}
[/math] by rule 2, since [math]\href{/cs2800/wiki/index.php/%CE%95}{ε}0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*}
[/math] and [math]1 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%CE%A3}{Σ}
[/math]
- [math]\href{/cs2800/wiki/index.php/%CE%95}{ε}010 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*}
[/math] by rule 2, since [math]\href{/cs2800/wiki/index.php/%CE%95}{ε}01 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*}
[/math] and [math]0 \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%CE%A3}{Σ}
[/math]
By convention, we leave off the leading "ε" from non-empty strings. For example, we would write "001" instead of "ε001".
