The lexicographic ordering of all strings over the alphabet {0, 1} is (∈, 0,
1, 00, 01, 10, 11, 000, K ).
Language: Any set of strings over an alphabet Σ is called a language.
The set of all strings, including the empty string over an alphabet Σ is
denoted as Σ
* .
Infinite languages L are denoted as
{
}
L
w
w
P
=
∈ Σ
* : has property
Examples:
(a)
{
}
L
w
w
1
01
=
∈{ , } :
*
has an equal number of 0' s and 1' s
(b)
{
}
L
w
w w
R
2 =
∈
=
Σ
* :
where w
R is the reverse string of w.
Concatenation of Languages: If L 1 and L 2 are languages over Σ, their
concatenation is L = L 1 • L 2 , or simply L = L 1 L 2 , where
{
}
L
w
w x y
x L
y L
=
∈
=
∈
∈
•
Σ
* :
,
for some
and
1
2
Example: Given Σ = { , }
0 1
{
}
L
w
w
1 =
∈ Σ
* : has an even number of 0' s
L
w w
2 =
: starts with a 0 and the rest of the symbols
{
}
are 1' s
then
{
}
L L
w w
1 2 =
: has an odd number of 0' s
Kleene Star: Another language operation is the “Kleene Star” of a language L,
which is denoted by L
* .
L
* is the set of all strings obtained by concatenating zero or more strings
from L.
L
w
w w
w
k
w w
w
L
k
k
*
* :
, , ,
=
∈
=
≥
∈

•
•
Σ
1
1
2
0
K
K
for some
and
some





Example: If L = {01, 1, 100} then 110001110011 ∈ L
* , since 110001110011 =
1• 100• 01• 1• 100 • 1• 1, each of these strings is in L.
Ì Exam ple 0.1.19: Prove that | | | | | |
uv
u v
= + , for any two given strings u
and v.
Introduction
19