Revision [5673]

This is an old revision of AutomatentheorieUndFormaleSprachen made by ToBo on 2008-10-23 17:05:58.

 

Automatentheorie und formale Sprachen


1. Kurze Einführung


Zeichen und Zeichenmenge


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+ 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 = s0 s1 ... sn, si e S

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


Länge


= |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

Valid XHTML :: Valid CSS: :: Powered by WikkaWiki