VO_Grundlagen_Informatik_1.0

VO Schenke Grundlagen Informatik www.hsmerseburg.de/schenke Buecher: Vossen / Witt, Grundlagen der Theoretischen Informatik Floyd / Beigel, Die Sprache der Maschinen Hopcroft/Motwani/Ullman ; Asteroth/Baier 1.Regulaere Sprachen 1.1 Endliche Automaten Bsp.1.0: Definition: Ein endlicher Automat ist ein 5 Tupel 5 Element; Reihenfolge entscheidend A = X, Z, Delta, z0, F mit: X Ist eine endliche Menge von Aktionen, Eingaben. Z ist auch eine endliche Menge von Zustaenden. ist eine Menge von Tripeln der Form z 1, x z2 mit zi Z, x X. Zustandsueberfuehrungsfunktion: Z X Z z0 Z: Anfangszustand F Z: Endzustand Exkurs: Cartesisches Produkt nach Renè Descartes Cartesisches Koordinatensystem Die endlichen Automaten werden auch NEA genannt NEA = nicht deterministische endliche Automaten. Bsp. 1.1: Fortsetzung von 1.0 Z = laufend, bereit, blockiert X = zuteilen, freigeben, I/O Anfordern, I/O Beenden = bereit, freigeben, laufend, laufend, zuteilen, bereit, blockiert, I/O beenden, bereit, z0 = bereit F = Laufend Bsp.1.2: Zeichenkette erkennen untersuche, ob 101 im gegebenen Text vorkommt. 00010010 = W Baue Automaten A mit : wenn W abgearbeitet ist und 101 gefunden wurde A ist im Endzustand wurde 101 nicht gefunden A ist nicht im Endzustand laufend bereit blockiert zuteilen freigeben I/O Anfordern I/O Beenden
Konstruktion: X = 0, 1 1.1.1 Deterministische endliche Automaten DEA Def.: ein deterministisch endlicher Automat DEA ist ein 5 Tupel A = X, Z, , z0, F mit: X, Z, z0, F wie endliche Automaten ist eine Funktion: : Z X Z heißt partiell definierte Funktion Bemerkung: Sei A ein endlicher Automat zu x X, z Z sei N z, x der nachbereich N z, x = z z, x, z Das ist eine Menge aller Nachfolgezustaende von Z bei Aktion X z.B.: N bereit, zulassen = laufen N laufen, zulassen = Die DEAs unterscheiden sich von allgemein endlichen Automaten dadurch, dass bei den DEAs die Nachbereiche aller Paare hoechstens ein Element enthalten. Wir identifizieren kuenftige DEAs mit solchen endlichen Automaten, mit Nachbereich der Moeglichkeit 0 oder 1 Bsp.1.3: 0 1 0,1 z0 z1 z2 ℇ 1 1 1 0 0 z0 z1 a b a in Ordnung z1 aa nicht in ordnung ab in Ordnung z0
Def.: a Ein Alphabet ist eine endliche Menge von endlichen Buchstaben b Eindliche Folge von Buchstaben ist ein Wort c Eine Sprache ist eine Menge von Woertern Bsp.1.4: 1. 0,1 ist ein Alphabet, ℕ ist unendlich also kein Alphabet 2. 0011 usw. sind Woerter ueber dem Alphabet. 3. 0011, 11111111, 0, 0n, 1n n ℕ = 01,0011,000111, usw sind Sprachen Bem.: Hintereinanderschreiben, Konkatenation ist eine Operation auf Woertern. Schreibweise: z.B.: 0011 00001111 = 001100001111 Untersuchen der Konketenation 1. Konkatenation ist nicht kommutativ haus traum traum haus haus.traum traum.haus 2. Konkatenation ist assoziativ ab cd ef = abcd ef = abcdef = ab cdef = ab cd ef geschrieben auf ab cd ef Def.: Neutrales Element: Seien M eine Menge und eine Verknuepfung auf M, also eine Abbildung: M M M. Ein Element e von M heißt neutrales Element bezueglich , wenn gilt: Fuer alle m M ist m M = m = e M Bsp.1.5: 1. Sein die Verknuepfung , dann ist das neutrale Element die 0. Fuer alle Zahlen Z gilt z 0 = Z = 0 z 2. Bei ist das neutrale Element die 1 3. Bezueglich der Konkartination wird ein neutrales Element postuliert. Dieses wird im Allg. ℇ Epsilon genannt. D.h. Sei w ein Wort. Dann gilt w ℇ = w = ℇ w Def.: Seien M1und M2 zwei Mengen von Woertern dann Sei die Konkatination dieser Menge beschrieben durch M1 M2 m1 m2 m1 M1 und m² m² Bsp.1.6: a, b c, d = a, b; a, d; bc; b, d a, aa a, aa = aa, aaa, aaaa Bem.: Fuer endliche M1, M2 gilt M1 M2 M1M2 Bsp.1.7: M ℇ = M; M = Def.: 1. Sei A ein Alphabet. Dann wird die Menge aller Woerter ueber A mit A bezeichnet. z0 z1 a b z0, ab = z0
Gesamtes Dokument lesen »