Definition: Let x and y be two strings over S;
x is prefix of y if there is a string z over S so
xz = y
Note: if x Ï {e, y} then x is proper prefix of y.
Example: Consider 1010
Task: All prefixes of 1010
Prefixes of 1010
Proper prefixes of 1010
e
1
10
101
1010
Prefix of String
 Gist: x is a prefix of xz
8/20