Therefore, (1.6) holds for all u and all υ of length up to n + 1, completing the
inductive step and the argument.
If w is a string, then w n stands for the string obtained by repeating ω n times.
As a special case, we define
for all w.
If ∑ is an alphabet, then we use ∑* to denote the set of strings obtained by
concatenating zero or more symbols from ∑. The set ∑* always contains λ. To
exclude the empty string, we define
While ∑ is finite by assumption, ∑* and ∑ + are always infinite since there is no
limit on the length of the strings in these sets. A language is defined very
generally as a subset of ∑*. A string in a language L will be called a sentence of
L. This definition is quite broad; any set of strings on an alphabet ∑ can be
considered a language. Later we will study methods by which specific languages
can be defined and described; this will enable us to give some structure to this
rather broad concept. For the moment, though, we will just look at a few specific
examples.
Example 1.9
Let ∑ = {a, b}. Then
The set
is a language on ∑. Because it has a finite number of sentences, we call it a finite
language. The set