Zeichen und Zeichenmenge

MathematikQuantoren Quantoren
MathematikPraedikate Prädikate
MathematikMengen Mengen

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}

Mengen

S ist eine Menge

S = {o, t}
o und t sind Elemente der Menge S

s ∈ S
s ist eine Element der Menge S

S⁺
beschreibt Wörter über S mit mindestens einem Zeichen
Beispiele:
s = o
s = t
s = ot
s = to
s = otto

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

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

Länge

s = otto

= 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 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) 2. Zustandsautomaten ZustandsAutomaten Zustandsautomaten allgemein EndlicherAutomat Endliche Zustandsautomaten DetEndlAutomaten Detirministische, endliche (Zustands)automaten (DEA), (SkriptAtfsEck, S. 15) NichtDetEndAutomaten Nichtdetirministische, endliche (Zustands)automaten (NEA), (SkriptAtfsEck, S. 19) FormaleSprachen Formale Sprachen ZustandsautomatenMitAusgabe Zustandsautomaten mit Ausgabe Schoening2008 Siehe auch Notizen und Übungen CategoryStudiumSE Siehe auch •