TheoInf - Zusammenfassung PDF

Preview

Summary

Zusammenfassung...

Description

Zusammenfassung – Theoretische Informatik WS17/18 Folie01 Wörter und Sprachen

• • • • • •

Alphabet: nicht-leere endliche Menge Symbol: Element eines Alphabets Wort über Alphabet Σ: endliche Folge von Symbolen aus Σ Leeres Wort: aus 0 Symbolen bestehende Folge, wird mit ε bezeichnet Menge aller Wörter über Alphabet Σ wird mit Σ* bezeichnet (Σ+ = Σ* - {ε}) Sprache über einem Alphabet Σ ist eine Teilmenge von Σ*

Operationen auf Wörtern

• • •

Länge eines Wortes w ist die Länge der Folge der Symbole Länge des Wortes w wird mit |w| bezeichnet Konkatenation: Seien x und y Wörter über dem Alphabet. Dann bezeichnet x ∘ y das Wort, das durch Hintereinanderschreiben von x und y entsteht. Statt x ∘ y schreibt man meist nur xy. Beispiel: kupfer ∘ kessel = kupferkessel Für alle Wörter u, v, w gilt: w ∘ ε = ε ∘w = w (u ∘ v) ∘ w = u ∘ (v ∘ w)

• • •

v ist Teilwort eines Wortes w, wenn es Wörter x und y gibt, so dass w = xvy v ist Präfix eines Wortes w, wenn es ein Wort y gibt, so dass w = vy v ist Suffix eines Wortes w, wenn es ein Wort x gibt, so dass w = xv

•

wn bezeichnet die n-te Potenz von w Beispiel: (da)3 = dadada

•

wR bezeichnet die Spiegelung von w Beispiel: (magdeburg)R = grubedgam

Operationen auf Sprachen

• • • •

Vereinigung ∪: = {x | x ∈ A ∨ x ∈ B} Schnitt ∩ : = {x | x ∈ A ∧ x ∈ B} Differenz - : = {x | x ∈ A ∧ x ∉ B} Komplement L einer Sprache L über Σ enthält genau die Wörter aus Σ*, die nicht zu L gehören

•

Konkatenation: Seien L1 und L2 Sprachen über Σ. Dann ist L1 ∘ L2 = L1 L2 = {w ∈ Σ* | es gibt x ∈L1 und y ∈L2, so dass w = xy} die Konkatenation von L1 und L2.

•

n-te Potenz der Sprache: Ln = {w ∈ Σ* | es gibt w1,w2,...,wn ∈L, so dass w = w1w2...wn} L0 = {ε}

•

Spiegelung einer Sprache: LR = {wR | w ∈L}

•

Kleene Star Abschluss:

Grammatik Eine Grammatik generiert Wörter durch einen Termersetzungsprozess Definition: Eine Grammatik ist ein 4-Tupel (V, Σ, R, S), wobei gilt: • V ≠ ∅ ist eine endlche Menge, die Menge der Nichtterminal(symbol)e oder Variablen • Σ ist ein Alphabet, das Terminalalphabet, Σ ∩ V = ∅ • R ⊂ (V ∪ Σ)+ x (V ∪ Σ)* ist eine endliche Menge von Regeln oder auch Produktionen • S ∈V ist das Startsymbol Falls G = (V, Σ, R, S) eine Grammatik ist und (u,v) ∈R, so schreiben wir u →G v Beispiel: G = ({S}, {a,b}, {(S,ε), (S,SS), (S,aSb)}, S) Regel S ⇒G SS S →G SS ⇒G aSbS S →G aSb ⇒G aSSbS S →G SS ⇒G aSSbaSb S →G aSb ⇒G aaSbSbaSb S →G aSb ⇒G aaSbSbab S →G ε ⇒G aabSbab S →G ε aabaSbbab S →G aSb ⇒G ⇒G aababbab S →G ε

Folie02 Chomsky-Hierarchie Klassifikation von Grammatiken: (und daraus resultierend Klassifikation von formalen Sprachen) • Typ 0 allgemeine Grammatiken • Typ 1 kontextsensitive Grammatiken • Typ 2 kontextfreie Grammatiken • Typ 3 reguläre Grammatiken Mengenlehre Eine Menge ist eine Zusammenfassung von verschiedenen Objekten zu einer Gesamtheit. Die Objekte in einer Menge werden Elemente der Menge genannt. Die Elemente sind ungeordnet, aber wohlunterschieden. Falls x ein Element einer Menge M ist, schreiben wir x ∈ M, sonst x ∉ M.

• • • • •

Eine Menge A heißt Teilmenge einer Menge B (A ⊆B), falls jedes Element von A auch ein Element von B ist. Eine Menge A heißt Obermenge einer Menge B (A ⊇B), genau dann wenn B ⊆A. Zwei Mengen A und B heißen gleich (A = B), genau dann wenn A ⊆B und B ⊆A gilt. Eine Menge A heißt echte Teilmenge einer Menge B (A ⊂B), genau dann wenn A ⊆B und A ≠ B. 2A = {M | M ⊆A}, die Menge aller Teilmengen von A, heißt Potenzmenge von A.

Satz: Seien A, B und C Mengen. Dann gilt: = A A ∪A = A A∩A = B ∪A A ∪B = B ∩A A∩B = (A ∪ B) ∪ C A ∪ (B ∪ C) = (A ∩ B) ∩ C A ∩ (B ∩ C) = (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C) (A ∪ B) ∩ A = A (A ∩ B) ∪A = A A – (B ∪ C) = (A – B) ∩ (A – C) = (A – B) ∪ (A – C) A – (B ∩ C)

Sei R ⊆V x V eine binäre Relation.

• • •

Die reflexive Hülle von R ist die Relation R ∪ {(a,a) | a ∈V} Die transitive Hülle von R ist die Relation R ∪ {(a,b) | a,b ∈V und es gibt einen Pfad positiver Länge von a nach b in R} Die reflexive, transitive Hülle von R ist die Relation R* ∪ {(a,b) | a,b ∈V und es gibt einen Pfad von a nach b in R}

Folie05 Deterministische endliche Automaten Definition: Ein deterministischer endlicher Automat ist ein 5-Tupel (K, Σ, δ, s, F), wobei gilt: • K ist eine endliche Menge von Zuständen, • Σ ist ein Alphabet • s ∈K ist der Startzustand • δ : K x Σ → K ist die Überführungsfunktion oder auch Übergangsfunktion • F ⊆K ist die Menge der Endzustände Beispiel:

Konfiguration:

(q0, ababbab)

⊢M ⊢M ⊢M ⊢M ⊢M ⊢M ⊢M

(q0, babbab) (q1, abbab) (q1, bbab) (q0, bab) (q1, ab) (q1, b) (q0, ε)

Definition: Eine Sprache L heißt regulär, wenn es einen endlichen Automaten M gibt mit L = L(M).

Nichtdeterminismus

Wir erlauben nun, • dass es mehr als einen Nachfolgezustand für ein Symbol gibt • dass es keinen Nachfolgezustand für ein Symbol gibt • dass es Übergänge gibt, ohne dass ein Symbol gelesen wird Nichtdeterministische endliche Automaten Definition: Ein nichtdeterministischer endlicher Automat ist ein 5-Tupel (K, Σ, Δ, s, F), wobei gilt: • K ist eine endliche Menge von Zuständen, • Σ ist ein Alphabet • s ∈K ist der Startzustand • Δ ⊆K x (Σ ∪ {ε}) x K ist die Überführungsrelation oder auch Übergangsrelation • F ⊆K ist die Menge der Endzustände Beispiel:

Folie06 Äquivalenz von NEA und DEA Zwei endliche Automaten M1 und M2 heißen äquivalent genau dann wenn L(M1) = L(M2). Satz: [Rabin, Scott] Zu jedem nichtdeterministischen endlichen Automaten gibt es einen äquivalenten deterministischen endlichen Automaten. Beispiel aus Übung:

Folie07 Abschlusseigenschaften Eine Menge M heißt abgeschlossen unter einer Operation, falls die Operation angewandt auf Elemente aus M stets wieder Elemente aus M ergibt, Satz: Die Klasse der von endlichen Automaten akzeptierten Sprachen ist abgeschlossen unter • Vereinigung • Konkatenation • Kleene Star • Komplement • Schnitt Reguläre Ausdrücke Definition: Sei Σ ein Alphabet mit {(, ), ∅, ∪, *} ∩ Σ = ∅. Ein regulärer Ausdruck über einem Alphabet Σ ist ein Wort über dem Alphabet Σ ∪ {(, ), ∅, ∪, *}, das wie folgt erzeugt werden kann: (1) (2) (3) (4) (5)

Jedes Element von Σ ist ein regulärer Ausdruck ∅ist ein regulärer Ausdruck Falls α und β reguläre Ausdrücke sind, dann ist (αβ) ein regulärer Ausdruck Falls α und β reguläre Ausdrücke sind, dann ist (α ∪β) ein regulärer Ausdruck Falls α ein regulärer Ausdruck ist, dann ist α* ein regulärer Ausdruck

Jeder reguläre Ausdruck repräsentiert eine Sprache: Sei L(α) die durch den Ausdruck α repräsentierte Sprache. L ist wie folgt definiert: (1) (2) (3) (4) (5)

L(σ) = {σ} für alle σ ∈ Σ L(∅) = ∅ Falls α und β reguläre Ausdrücke sind, dann ist L((αβ)) = L(α)L(β) Falls α und β reguläre Ausdrücke sind, dann ist L((α ∪β)) = L(α) ∪L(β) Falls α ein regulärer Ausdruck ist, dann ist L(α*) = L(α)*

Beispiel:

Solange der Ausdruck eindeutig bleibt, können wir Klammern weglassen. Dazu vereinbaren wir, dass Kleene Star höchste Priorität und Konkatenation Vorrang vor Vereinigung hat.

Weiter Beispiele:

Reguläre Ausdrücke und reguläre Sprachen Satz: [Kleene] Die Klasse der durch reguläre Ausdrücke beschreibbaren Sprachen ist genau die Klasse der regulären Sprachen....