Definice: Nechť x a y jsou dva
řetězce nad abecedou S; x je prefixem y, pokud
existuje řetězec z nad abecedou S, přičemž platí xz = y.
Pozn.: pokud x Ï {e, y} pak x je vlastní
prefix řetězce y.
Příklad: Uvažujme řetězec 1010
Určeme: Všechny prefixy 1010
Prefixy 1010
Vlastní prefixy 1010
e
1
10
101
1010
Prefix řetězce
Myšlenka: x je
prefixem řetězce xz
8/20