Definice: Nechť S je abeceda.
1) e je řetězec nad abecedou S
2) pokud x je řetězec nad S a a Î S, potom xa je řetězec nad abecedou S
Příklad: Uvažujme S = {0, 1}:
Je řetězec nad S
:
:
...
e
0
1
 =  0
 =  1
1
Pozn.: e značí tzv. prázdný řetězec = neobsahuje žádný symbol.
e
e
0
0
1
1
0
0
1
1
10
10
0
S
Řetězec
Myšlenka: x = a1a2…an
3/20