Zeichen: Ein Alphabet ist eine vereinbarte Zeichenmenge

Zeichenfolgen: Wörter, Sätze, Satzgefüge

in der Theorie: Wörter über Alphabet

S ist ein Alphabet

S = {a,b,c,x,k,l,...,z}

S⁺ beschreibt Wörter über S mit mindestens einem Zeichen

S* beschreibt Wörter über S mit mindestens einem Zeichen oder ein leeres Wort (enthält kein Zeichen)

s = s₀ s₁ ... s_n, s_i e S

s = otto (Länge von s ist 4)

= |otto| = 4

x ist die länge von s bezogen auf die Anzahl des Vorkommens des Zeichens x leeres Wort |epsilon| = 0 |0110101|1 = 4 |0110101|0 = 3 |0110101|2 = 0 Konkatenation: Verkettung, Hintereinanderschreiben s = s0 s1 s2 ... sn

= n + 1 t = t0 t1 t2 ... tm

= m + 1 Kat(s,t) = st |st| = n+m+2 Wirkung von Epsilon: Kat(eps, s) = epss = s = seps = Kat(s,eps) Siehe auch •