DHARMINTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 169The set of all possible strings over Σ is denoted by Σ, where operator is called as
Kleeny-closure operator and the meaning of Σ is given by,
Σ = Σ^0 ∪ Σ^1 ∪ Σ^2 ∪.....................
For example, if Σ = {0, 1}, then using the previous definitions of Σ^0 , Σ^1 , Σ^2 , ....
we have,
Σ = {∈} ∪ {0, 1} ∪ {00, 01, 10, 11} ∪ {000, 001, 010, 011, 011,...} ∪....
= {∈, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 011, ...........................}
(this set contains infinite many strings)
From the set Σ, if we exclude the empty string (∈) then we have a set of nonempty
strings over alphabet Σ. That we denoted by Σ+ (where + is called Positive-closure operator).
Therefore,
Σ+ = Σ – {∈}[∴Σ^1 ∪ Σ^2 ∪ ..................... ]
Conversely, we say Σ = Σ+ ∪ {∈}
7.1.4 Languages
A language is the set of strings chosen from Σ, for any alphabet Σ. If L is the language over Σ
then L ⊆ Σ. Hence, language L may contains infinite many strings. Since languages are set of
strings, thus new languages can be constructed using set operations viz., union, intersections,
difference, and complement. For example, the complement of the language L over alphabet Σ
is given by
L′ = Σ – L,
where Σ contains all possible set of strings formed over Σ that we take the universal set.
Hence, set L′ contains all those strings of Σ that are not in the set L.
A new language can also be constructed using concatenation operation over strings. Let
x and y are two strings then concatenation of x and y is the string xy, that is ‘string x followed
by string y’. For example, let x is the string of n symbols i.e., a 1 a 2 a 3 ........an and y is the string
of m symbols i.e., b 1 b 2 .........bm, then xy is the string of (n + m) symbols i.e., a 1 a 2 a 3 ........an b 1
b 2 .........bm. Note that concatenation is not commutative, such that xy ≠ yx until x ≠ y. On the
other side concatenation is associative, such that for any strings x, y, and z, (xy)z = x(yz). This
allows us to concatenate the strings without restricting the order in which various concatenation
operations are to be performed.
We can also apply the concatenation operation over set of strings called languages. For
example, let languages are L 1 ⊆ Σ and L 2 ⊆ Σ*, then there concatenation is L 1 L 2 , i.e.,
L 1 L 2 = {xy/x ∈ L 1 and y ∈ L 2 }
Consider an example, Let L 1 = {∈} and L 2 = {00, 01, 10, 11}, then
L 1 L 2 = {∈} {00, 01, 10, 11} = {∈ 00, ∈ 01, ∈ 10, ∈ 11}
= {00, 01, 10, 11} [Q ∈ x = x, for any string x]
· Remember, concatenation of two null strings or language containing null strings only
is a null string, i.e.,
∈. ∈ = ∈
· If language set L 1 is empty i.e., L 1 = { } or ∅, then concatenation of L 1 L 2 will remain
empty for any language L 2. For example, let L 2 = {ab, bc, abc}, then
L 1 L 2 = ∅ {ab, bc, abc} = { } or ∅
· If both, L 1 = ∅ and L 2 = ∅, then L 1 L 2 = Ø.