+ All Categories
Home > Documents > 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines...

3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines...

Date post: 02-Jan-2020
Category:
Upload: others
View: 2 times
Download: 0 times
Share this document with a friend
41
Grundlagen der Theoretischen Informatik 3. Endliche Automaten 30.04.2015 Viorica Sofronie-Stokkermans Matthias Horbach e-mail: [email protected], [email protected] 1
Transcript
Page 1: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Grundlagen der Theoretischen Informatik

3. Endliche Automaten

30.04.2015

Viorica Sofronie-Stokkermans

Matthias Horbach

e-mail: [email protected], [email protected]

1

Page 2: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Bis jetzt

1. Motivation

2. Terminologie

3. Endliche Automaten und regulare Sprachen

4. Kellerautomaten und kontextfreie Sprachen

5. Turingmaschinen und rekursiv aufzahlbare Sprachen

6. Berechenbarkeit, (Un-)Entscheidbarkeit

7. Komplexitatsklassen P und NP

2

Page 3: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Jetzt

1. Motivation

2. Terminologie

3. Endliche Automaten und regulare Sprachen

4. Kellerautomaten und kontextfreie Sprachen

5. Turingmaschinen und rekursiv aufzahlbare Sprachen

6. Berechenbarkeit, (Un-)Entscheidbarkeit

7. Komplexitatsklassen P und NP

3

Page 4: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

3. Endliche Automaten

4

Page 5: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

3. Endliche Automaten

Inhalt von Teil 3

• Vereinfachtes Modell eines Computers: endlicher Automat

5

Page 6: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

3. Endliche Automaten

Inhalt von Teil 3

• Vereinfachtes Modell eines Computers: endlicher Automat

• Die von endlichen Automaten erkannten “rationalen” Sprachen sind

genau die Typ-3-Sprachen (rechtslinear, regular)

6

Page 7: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

3. Endliche Automaten

Inhalt von Teil 3

• Vereinfachtes Modell eines Computers: endlicher Automat

• Die von endlichen Automaten erkannten “rationalen” Sprachen sind

genau die Typ-3-Sprachen (rechtslinear, regular)

• Determinierte und indeterminierte endliche Automaten sind aquivalent

7

Page 8: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

3. Endliche Automaten

Inhalt von Teil 3

• Vereinfachtes Modell eines Computers: endlicher Automat

• Die von endlichen Automaten erkannten “rationalen” Sprachen sind

genau die Typ-3-Sprachen (rechtslinear, regular)

• Determinierte und indeterminierte endliche Automaten sind aquivalent

• Pumping Lemma erlaubt, eine Sprache als nicht rational nachzuweisen.

8

Page 9: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

3. Endliche Automaten

Inhalt von Teil 3

• Vereinfachtes Modell eines Computers: endlicher Automat

• Die von endlichen Automaten erkannten “rationalen” Sprachen sind

genau die Typ-3-Sprachen (rechtslinear, regular)

• Determinierte und indeterminierte endliche Automaten sind aquivalent

• Pumping Lemma erlaubt, eine Sprache als nicht rational nachzuweisen.

• Es gibt Algorithmen, die Probleme uber endlichen Automaten bzw.

Typ-3-Sprachen losen.

9

Page 10: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

3. Endliche Automaten

Inhalt von Teil 3

• Vereinfachtes Modell eines Computers: endlicher Automat

• Die von endlichen Automaten erkannten “rationalen” Sprachen sind

genau die Typ-3-Sprachen (rechtslinear, regular)

• Determinierte und indeterminierte endliche Automaten sind aquivalent

• Pumping Lemma erlaubt, eine Sprache als nicht rational nachzuweisen.

• Es gibt Algorithmen, die Probleme uber endlichen Automaten bzw.

Typ-3-Sprachen losen.

• Typ-3-Sprachen sind genau die, die durch regulare Ausdrucke

beschrieben werden konnen.

10

Page 11: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

3. Endliche Automaten

• Determinierte endliche Automaten (DEAs)

• Indeterminierte endliche Automaten (NDEAs)

• Automaten mit epsilon-Kanten

• Endliche Automaten akzeptieren genau die Typ-3-Sprachen

• Pumping Lemma

• Abschlusseigenschaften und Wortprobleme

• Rational = Regulare Ausdrucke

11

Page 12: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

3. Endliche Automaten

• Determinierte endliche Automaten (DEAs)

• Indeterminierte endliche Automaten (NDEAs)

• Automaten mit epsilon-Kanten

• Endliche Automaten akzeptieren genau die Typ-3-Sprachen

• Pumping Lemma

• Abschlusseigenschaften und Wortprobleme

• Rational = Regulare Ausdrucke

12

Page 13: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Determinierte endliche Automaten (DEAs)

13

Page 14: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Beispiel

Beispiel 1. Die Sprache

L = {aa}{ab}∗{c}

ist regular.

14

Page 15: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Beispiel

Beispiel 1. Die Sprache

L = {aa}{ab}∗{c}

ist regular.

Denn sie wird (z. B.) erzeugt von der rechtslinearen Grammatik

G = ({S ,A}, {a, b, c},R, S),

mit Regelmenge R:

S → aaA

A → abA | c

15

Page 16: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Beispiel

Beispiel 2. Die Sprache aller durch 3 teilbaren Dezimalzahlen ist regular.

Eine erzeugende Grammatik ist

G = ({S ,S0, S1, S2}, {0, . . . , 9},R, S)

mit der Regelmenge R:

S → 3S0 | 6S0 | 9S0 | 1S1 | 4S1 | 7S1 | 2S2 | 5S2 | 8S2 | 0

S0 → 0S0 | 3S0 | 6S0 | 9S0 | 1S1 | 4S1 | 7S1 | 2S2 | 5S2 | 8S2 | ε

S1 → 0S1 | 3S1 | 6S1 | 9S1 | 1S2 | 4S2 | 7S2 | 2S0 | 5S0 | 8S0

S2 → 0S2 | 3S2 | 6S2 | 9S2 | 1S0 | 4S0 | 7S0 | 2S1 | 5S1 | 8S1

Ohne das ε in der zweiten Regel ware nur die “0” als Terminalwort

herleitbar.

16

Page 17: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Grammatiken und Automaten

Grammatik vs. Automat

Grammatiken erzeugen Worter

Automaten analysieren / erkennen Worter

beide beschreiben / definieren Sprachen

17

Page 18: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Informell

Ein endlicher Automat testet, ob ein gegebenes w ∈ Σ∗ in einer Sprache L liegt.

• Lesekopf erlaubt w zu lesen.

Bewegt sich nur von links nach rechts.

• Endlich viele mogliche interne Zustande,

immer einer davon ist der aktuelle Zustand

• Automat beginnt in einem initialen Zustand.

• Bei jedem gelesenen Buchstaben Ubergang zu neuem aktuellen Zustand,

in Abhangigkeit vom Buchstaben und dem alten Zustand

• Wenn am Ende von w ein finaler Zustand erreicht ist,

ist w akzeptiert als Element von L, sonst nicht.

• Automat stoppt (auf jeden Fall) nach |w | Schritten

18

Page 19: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Modell eines einfachen Computers

Endlicher Automat: Computer mit begrenztem Speicher

• Kann vom Band nur lesen

⇒ kein externer Speicher

• Speichert nur den aktuellen Zustand (≈ Programmzahler)

⇒ stark begrenzter interner Speicher

19

Page 20: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Darstellung als Graph

Darstellung als Graph

• ein Knoten fur jeden moglichen Zustand,

• Kanten sind mit Buchstaben beschriftet: Sie beschreiben Zu-

standsanderungen.

• Initiale Zustande werden mit einem Pfeil gekennzeichnet,

• finale Zustande mit einem doppelten Kreis.

20

Page 21: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Darstellung als Graph

Beispiel: Sprache {w | #a(w) gerade} ⊂ {a, b}∗

Der folgende endliche Automat erkennt die Sprache

{w | #a(w) gerade} uber Σ = {a, b}

der Worter mit gerader Anzahl von”a“s

21

Page 22: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Darstellung als Graph

Beispiel: Sprache {w | #a(w) gerade} ⊂ {a, b}∗

Der folgende endliche Automat erkennt die Sprache

{w | #a(w) gerade} uber Σ = {a, b}

der Worter mit gerader Anzahl von”a“s

1s

a

a

b b

s0>A :

22

Page 23: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Definition

Definition. Ein endlicher Automat (e.a.) (finite automaton) ist ein Tupel

A = (K , Σ, δ, s0,F ).

Dabei ist

• K eine endliche Menge von Zustanden,

• Σ ein endliches Alphabet (aus dessen Buchstaben die Einga-

beworter bestehen konnen),

• δ : K × Σ → K die totale(!) Ubergangsfunktion,

• s0 ∈ K der Startzustand, und

• F ⊆ K die Menge der finalen Zustande.

23

Page 24: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Ubergangsfunktion

Bedeutung der Ubergangsfunktion

δ(q, a) = q′ bedeutet:

• Der Automat ist im Zustand q,

• liest ein a und

• geht in den Zustand q′ uber.

24

Page 25: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Ubergangsfunktion

Bedeutung der Ubergangsfunktion

δ(q, a) = q′ bedeutet:

• Der Automat ist im Zustand q,

• liest ein a und

• geht in den Zustand q′ uber.

Wir erweitern δ zu δ∗

δ∗ : K × Σ∗ → K ist strukturell rekursiv uber Σ∗ definiert:

δ∗(q, ε) := q

δ∗(q,wa) := δ(δ∗(q,w), a)

Wenn klar ist, was gemeint ist, wird δ∗ auch einfach als δ geschrieben.

25

Page 26: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Beispiel

1s

a

a

b b

s0>A :

Dieser Automat azeptiert die Sprache

{w | #a(w) gerade} ⊂ {a, b}∗ (Beispiel Seite 22)

26

Page 27: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Beispiel

1s

a

a

b b

s0>A :

Formal hat er die Form: A = ({s0, s1}, {a, b}, δ, s0, {s0}) mit

δ(s0, a) = s1 δ(s1, a) = s0

δ(s0, b) = s0 δ(s1, b) = s1

27

Page 28: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Ubergangsfunktion

Beispiel fur δ∗

δ∗(s0, aab) = δ(

δ∗(s0, aa), b)

= δ(

δ(

δ∗(s0, a), a)

, b)

= δ(

δ(

δ(δ∗(s0, ε), a)

, a)

, b)

= δ(

δ(

δ(s0, a), a)

, b)

= δ(

δ(s1, a), b)

= δ(s0, b)

= s0

28

Page 29: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Akzeptierte Sprache

Definition (Von einem endlichen Automaten akzeptierte Sprache)

Die von einem Automaten A akzeptierte Sprache, ist definiert als

L(A) := {w ∈ Σ∗ | δ∗(s0,w) ∈ F}

29

Page 30: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Akzeptierte Sprache

Definition (Von einem endlichen Automaten akzeptierte Sprache)

Die von einem Automaten A akzeptierte Sprache, ist definiert als

L(A) := {w ∈ Σ∗ | δ∗(s0,w) ∈ F}

Definition (Von endlichen Automaten akzeptierte Sprachen)

Die Menge

RAT := {L | es gibt einen endlichen Automaten A mit L = L(A)}

der von endlichen Automaten akzeptierten Sprachen

heißt Menge der rationalen Sprachen

30

Page 31: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: Akzeptierte Sprache

Definition (Von einem endlichen Automaten akzeptierte Sprache)

Die von einem Automaten A akzeptierte Sprache, ist definiert als

L(A) := {w ∈ Σ∗ | δ∗(s0,w) ∈ F}

Definition (Von endlichen Automaten akzeptierte Sprachen)

Die Menge

RAT := {L | es gibt einen endlichen Automaten A mit L = L(A)}

der von endlichen Automaten akzeptierten Sprachen

heißt Menge der rationalen Sprachen

Wir zeigen demnachst: RAT = Menge der regularen Sprachen

31

Page 32: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: UML State Chart

UML State Charts sind eine (erweiterte) Form endlicher Automaten

32

Page 33: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endlicher Automat: UML State ChartUML State Charts sind eine (erweiterte) Form endlicher Automaten

Beispiel:

33

Page 34: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endliche Automate: Weitere Beispiele

Beispiel. Die Sprache aller Worter mit gerader Anzahl von a

uber dem (kleineren) Alphabet Σ = {a} wird akzeptiert von

34

Page 35: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endliche Automate: Weitere Beispiele

Beispiel. Die Sprache aller Worter mit gerader Anzahl von a

uber dem (kleineren) Alphabet Σ = {a} wird akzeptiert von:

a

a

> s0

s1A :

35

Page 36: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endliche Automate: Weitere Beispiele

Beispiel. Die Sprache

L = {w ∈ {0, 1}∗ | w enthalt genau zwei Einsen}

wird akzeptiert von dem folgenden endlichen Automaten:

36

Page 37: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endliche Automate: Weitere Beispiele

Beispiel. Die Sprache

L = {w ∈ {0, 1}∗ | w enthalt genau zwei Einsen}

wird akzeptiert von dem folgenden endlichen Automaten:

0s

s3

0, 1

> s s1 2

0

1

0

1

0

A :

1

37

Page 38: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endliche Automate: Weitere Beispiele

Beispiel

Die Sprache aller durch 3 teilbaren Dezimalzahlen wird akzeptiert durch:

38

Page 39: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Endliche Automate: Weitere Beispiele

Beispiel

Die Sprache aller durch 3 teilbaren Dezimalzahlen wird akzeptiert durch:

s1

s2

0, 3, 6, 9

sacc0

srej

0, 1, ..., 9

0, 1, ..., 9

s>

3, 6, 9

A:

s0

0, 3, 6, 9

1, 4, 7

1, 4, 7

2, 5, 8

2, 5, 8 2, 5, 8

0, 3, 6, 9

2, 5, 81, 4, 7

1, 4, 7

0

39

Page 40: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

3. Endliche Automaten

• Determinierte endliche Automaten (DEAs)

• Indeterminierte endliche Automaten (NDEAs)

• Automaten mit epsilon-Kanten

• Endliche Automaten akzeptieren genau die Typ-3-Sprachen

• Pumping Lemma

• Abschlusseigenschaften und Wortprobleme

• Rational = Regulare Ausdrucke

40

Page 41: 3. Endliche Automaten3. Endliche Automaten Inhalt von Teil 3 • Vereinfachtes Modell eines Computers: endlicher Automat • Die von endlichen Automaten erkannten “rationalen”

Nachste Vorlesung

• Determinierte endliche Automaten (DEAs)

• Indeterminierte endliche Automaten (NDEAs)

• Automaten mit epsilon-Kanten

• Endliche Automaten akzeptieren genau die Typ-3-Sprachen

• Pumping Lemma

• Abschlusseigenschaften und Wortprobleme

• Rational = Regulare Ausdrucke

41


Recommended