FGd I1slides - Folien PDF

Preview

Summary

Folien...

Description

Kap. 2: Endliche Automaten

regul¨ are Sprachen

2.1

Regul¨ are Sprachen

Definition 2.1.3

Semantik f¨ ur α 2 REG(Σ ): L(α) ✓ ⇤Σ die durch α bezeichnete regul¨ are Sprache Induktiv/rekursiv u¨ber α 2 REG(Σ ) definiere L(α): (i) L(;) := ;. (ii) L(a) := {a}. (iii) L(α + β) := L(α) [ L(β). (iv) L(αβ) := L(α) · L(β).  ⇤ (v) L(α⇤ ) := L(α) .

Definition Die regul¨aren Σ -Sprachen sind genau die L(α) f¨ ur α 2 REG(Σ )

AFSE (FGdI I)

Winter 2020

Kap. 2: Endliche Automaten

M Otto

regul¨ are Sprachen

51/87

2.1

Die regul¨ aren Σ-Sprachen werden erzeugt aus den Ausgangssprachen ; und {a} f¨ ur a 2 Σ durch die Operationen Vereinigung, Konkatenation und Stern.

AFSE (FGdI I)

Winter 2020

M Otto

52/87

Kap. 2: Endliche Automaten

endliche Automaten

2.2

Endliche Automaten

! Abschnitt 2.2

Transitionssysteme (mit endl. Zustandsmenge)   S= Σ , Q , ∆ mit den Komponenten:

Σ : Alphabet (Kantenbeschriftungen) Q : Zustandsmenge, endlich, 6= ; ∆ ✓ Q ⇥ Σ⇥ Q : Transitionsrelation a

(q, a, q 0 ) 2 ∆ steht f¨ ur die Transition q ! q 0

AFSE (FGdI I)

Winter 2020

Kap. 2: Endliche Automaten

M Otto

endliche Automaten

53/87

2.2

Beispiel: Transitionssystem mit Zusatzstruktur, DFA b b a

/ 0 Y

/ 1 s

modulo-3 Z¨ ahler f¨ u r a, |w |a mod 3.

a

a

2

⇧ U

b

Zusatzstruktur: !: Initialisierung; ur |w|a ⌘ 2 (mod 3) 2 : ausgezeichneter Zustand, hier f¨ deterministisch: ∆ beschreibbar durch Funktion δ : Q ⇥ Σ! Q AFSE (FGdI I)

Winter 2020

M Otto

54/87

Kap. 2: Endliche Automaten

endliche Automaten

2.2

Endliche Automaten, DFA und NFA Idee: Transitionssysteme zur Erkennung von Sprachen deterministische Transitionssysteme/Automaten anstelle der Transitionsrelation

∆ ✓ Q ⇥ Σ⇥ Q δ : Q ⇥ Σ ! Q (q, a) 7! δ(q, a) 2 Q

Transitionsfunktion

jeweils genau ein eindeutig bestimmter Nachfolgezustand kein deadlock, keine Auswahl nicht-deterministische Transitionssysteme/Automaten Transitionsrelation bietet u.U. bei Eingabe a in Zustand q ( kein q 0 mit (q , a, q 0 ) 2 ∆. deadlock verschiedene q 0 mit (q, a, q 0 ) 2 ∆.

AFSE (FGdI I)

Winter 2020

Kap. 2: Endliche Automaten

Auswahl

M Otto

endliche Automaten

55/87

2.2

Deterministische endliche Automaten, DFA   A = ,ΣQ , q0 , δ, A Q endliche, nicht-leere Zustandsmenge q0 2 Q Anfangszustand A✓Q Menge der akzeptierenden Zust¨ ande ¨ Ubergangsfunktion. δ : Q ⇥ Σ! Q Berechnung von A auf w = a1 . . . an 2 ⇤Σ die eindeutige Zustandsfolge q0 , . . . , qn mit qi +1 = δ(qi , ai +1) f¨ ur 0 6 i < n q0

AFSE (FGdI I)

a1

Winter 2020

/ q1

a2

M Otto

/

···

qn1

an

/ qn

56/87

Kap. 2: Endliche Automaten

endliche Automaten

2.2

DFA: L¨ aufe und Berechnungen

Definition 2.2.4

analog zu Berechnung (vom Startzustand q0 aus) definiere Lauf auf w von q 2 Q aus a1

q

/ q0

a2

/

···

f¨ uhrt zu eindeutiger Fortsetzung δˆ von δ: 8 ˆ δ : Q ⇥ ⇤Σ ! Q < der (!) Endzustand des ˆ w) 2 Q (q, w) 7! δ(q, Laufs auf w von q aus : induktiv definiert

Berechnungen sind L¨ aufe von q0 aus; ˆ 0 , w) Endzustand der Berechnung von A auf w: δ(q L¨ aufe beschreiben auch Teilabschnitte von Berechnungen

AFSE (FGdI I)

Winter 2020

Kap. 2: Endliche Automaten

M Otto

endliche Automaten

57/87

2.2

erkannte/akzeptierte Sprache

Definition 2.2.3

DFA: von A erkannte/akzeptierte Sprache w = a1 . . . an mit Berechnung q0 , . . . , qn ( akzeptiert w falls qn 2 A A verwirft w falls qn 62 A

ˆ 0 , w) qn = δ(q

die von A akzeptierte/erkannte Sprache:  L(A) := w 2 ⇤Σ: A akzeptiert w  = w 2 ⇤Σ: ˆ δ(q0 , w) 2 A

AFSE (FGdI I)

Winter 2020

M Otto

58/87

Kap. 2: Endliche Automaten

endliche Automaten

2.2

Nicht-deterministische endliche Automaten, NFA   A = ,ΣQ , q0 , ∆, A Q endliche, nicht-leere Zustandsmenge q0 2 Q Anfangszustand A✓Q Menge der akzeptierenden Zust¨ ande ¨ ∆ ✓ Q ⇥ Σ⇥ Q Ubergangsrelation. Berechnung von A auf w = a1 . . . an 2 ⇤Σ jede (!) Zustandsfolge q0 , . . . , qn mit (qi , ai +1 , qi +1 ) 2 ∆ q0

a1

/ q1

a2

/

···

qn1

an

/ qn

Vorsicht: i.d.R. nicht eindeutig, nicht notwendig existent!

AFSE (FGdI I)

Winter 2020

Kap. 2: Endliche Automaten

M Otto

endliche Automaten

59/87

2.2

erkannte/akzeptierte Sprache

Definition 2.2.6

NFA: von A erkannte/akzeptierte Sprache eine Berechnung q0 , . . . , qn von A auf w = a1 . . . an ist eine akzeptierende Berechnung auf w falls qn 2 A die von A akzeptierte/erkannte Sprache: L(A) :=  w 2 ⇤Σ: A hat eine akzeptierende Berechnung auf w

beachte:

AFSE (FGdI I)

Existenz mindestens einer akzeptierenden Berechnung Asymmetrie bzgl. akzeptieren/verwerfen

Winter 2020

M Otto

60/87

Kap. 2: Endliche Automaten

endliche Automaten

2.2

Beispiele

Σ= {a, b} b

DFA A1

/ 0 o

a

a b

/ 1

" / 2 o

a b

a,b

NFA A2

L(A1 ) = ?

a,b a

/ 0

a

/ 1

/ 2

a

a,b

NFA A3

/ 3

/ 3

L(A2 ) = ?

a,b a

/ 0 a

a

/ 1 

4 U

a

/ 2

a

/ 3

L(A3 ) = ?

/ 5

a,b AFSE (FGdI I)

Winter 2020

Kap. 2: Endliche Automaten

M Otto

endliche Automaten

61/87

2.2

Determinisierung

! Abschnitt 2.2.3

von NFA zu ¨ aquivalentem DFA; Determinisierung deterministische Simulation des NFA durch Potenzmengen-Trick Satz 2.2.9 Zu NFA A l¨asst sich ein DFA Adet (effektiv) konstruieren, der dieselbe Sprache erkennt: L(A) = L(Adet ). Idee:

AFSE (FGdI I)

Zust¨ ande von Adet geben an, in welchen Zust¨anden A sein k¨onnte

Winter 2020

M Otto

62/87...