In addition to defining the notion of a language itself,
we wanted to find some operations on languages and establish some notation.
We'll illustrate using these two languages over the zero one alphabet.
Since languages are set,
we have the usual operations of union, intersection and complement.
For example, A union B consists of these three strings.
0, from both A and B, 10 from A, and 11 from B.
The intersection contains only those strings in both languages.
Just the string 0 here.
To define the complement of a language we need to make clear
what it is that we're completing.
It's not sufficient just to say that it's everything not in A.
For this particular A that would include strings with characters besides 0 and 1.
Or maybe even infinite sequences of zeros and ones.
Which we don't want.
The complement therefore, is designed so as to complete the set of all strings
over the relevant alphabet, in this case the binary alphabet.
Usually, the alphabet over which the language is defined
will be clear from context.
In this case, the complement of A will be infinite,
including the empty string, not zero however.
It will include 1, it will include 00,
it will include 01, it will not include 10, however.
It will include 11, it will include 000, and so on and so
forth for all longer strings.
In addition to these standard set operations,
we also define an operation for concatenating two languages.
The concatenation of A and B is just all strings that you can form by taking
a string from A, let's say x, and appending to it a string y from B.
In our examples, the set AB would be 0 0.
The first 0 coming from A and the second from B.
011, with the 0 coming from A, and the 11 coming from B, and so forth.
Of course, we can also concatenate a language with itself.
As I've done here in this example.
Instead of writing AA, we often write A squared.
And in general, when want to concatenate a language with itself k times,
we write A to the kth power.
Note that for k equals 0,
this is defined as the language containing exactly the empty string.
When we want to concatenate any number of strings from a language together,
to form a new language.
We use an operator known as Kleene Star.
This can be thought of as the union of all possible powers of the language.
When we want to exclude the empty string, we use the Plus Operator
instead, which insists that at least one string from A be used.
Notice the difference in the starting indices.
For example, this string here is in A*.
There's a way that I can break it up so that each part is in the language A.
Note that A* doesn't include infinite sequences of symbols.
Each individual string from A must be a finite length and
you're only allowed to concatenate a finite number of those together.
For those who have studied regular expressions,
this should seem quite familiar.
In fact, one gets the notation for
regular expressions by treating individual symbols as languages.
For example, 0* is the set of all strings consisting entirely of zeros.
We'll also commonly refer to sigma star meaning all possible strings over
the alphabet sigma.