Definition:
Let
S
be an alphabet.
1)
e
is a string over
S
2)
if
x
is a string
over
S
and
a
Î
S
then
xa
is
a
string over
S
Example:
Consider
S
= {
0
,
1
}
:
Is string over
S
.
:
:
...
e
0
1
=
0
=
1
1
Note:
e
denotes
the
empty string
that contains no symbols.
e
e
0
0
1
1
0
0
1
1
10
10
0
S
String
Gist:
x
=
a
1
a
2
…
a
n
3/20