Definition: Let S* denote the set of all strings
over S. Every subset L Í S* is a language over S.
Note: S+ denote the set S* – {e}.
Set S*
L1, L2, L3, L4 are languages over S
L1 = Æ
L2 = {e}
L4 = {x: 10 is substring of x}
...
L3 = {x: |x| = 1}
Example: Consider S = {0, 1}:
000
e
01
00
10
11
001
010
100
...
011
111
0
1
Languages
 Gist: L Í S*
11/20