is also a language on ∑. The strings aabb and aaaabbbb are in the language L,
but the string abb is not in L. This language is infinite. Most interesting
languages are infinite.
Since languages are sets, the union, intersection, and difference of two
languages are immediately defined. The complement of a language is defined
with respect to ∑*; that is, the complement of L is
The reverse of a language is the set of all string reversals, that is,
The concatenation of two languages L 1 and L 2 is the set of all strings obtained by
concatenating any element of L 1 with any element of L 2 ; specifically,
We define L n as L concatenated with itself n times, with the special cases
and
for every language L.
Finally, we define the star-closure of a language as
and the positive closure as
Example 1.10