23
Endliche Automaten Einführung in den Themenbereich 1 Karin Haenelt 18.04.2010

Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

  • Upload
    vobao

  • View
    217

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Endliche Automaten

Einführung in den Themenbereich

1

Karin Haenelt

18.04.2010

Page 2: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Inhalt

� Informelle Einführung: Was sind endliche Automaten?� Abstrakte Automaten� Endliche abstrakte Automaten� Beispiele� Typen endlicher Automaten

� Akzeptoren, Transduktoren� Akzeptoren, Transduktoren� deterministisch, nicht-deterministisch, stochastisch

� Definitionen� Abstrakte Automaten als mathematische Strukturen� Endliche abstrakte Automaten

� Einordnung endlicher Automaten� Automatentheorie: Art des Speichers� Theorie formaler Sprachen: Strukturelle Komplexität

2© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 3: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Informelle EinführungAbstrakter Automat

� ein abstrakter Automat ist ein mathematisches Modell für einfache Maschinen/Programme, die bestimmte Probleme lösen

� beschreibt nicht einen bestimmten Automaten, sondern gemeinsame Grundprinzipien einer Klasse von Automaten

� Grundlegende Komponenten� Grundlegende Komponenten� Zustände� Eingabesymbole� Zustandsübergänge: reagiert auf Eingaben durch Übergang

in einen anderen Zustand

3

Zustände des Automaten

Eingabe Ausgabe

© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 4: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Informelle EinführungEndlicher abstrakter Automat

� Ein abstrakter Automat ist ein „endlicher Automat“, wenn die Anzahl der Zustände, der Eingaben u. der Ausgaben endlich ist

� Komponenten der Modelle� endliche Menge von Zuständen (Q)

� interne Konfigurationen, in denen sich ein System befinden kann

� zeitliche Ordnung (δ)� definiert die möglichen Sequenzen von Zuständen

� endliche Menge von Eingaben (Σ)� endliche Menge von Ausgaben (Reaktionen) (∆)

� System zeigt abhängig vom aktuellen Zustand eine bestimmte Reaktion und geht in einen Folgezustand über

4© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 5: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Endliche Automaten: BeispieleKippschalter und Lexikon

anausStart

drücken

drücken drücken aus an an aus

Schalter

d e m n r s 0 1 1 2 2 3 3 3 4 3 f 4 f 5 5 6 6 7 7 f

5

drücken

d0 1

e2

m3

nr

5s

4 s 7e

6 n

Lexikon

© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 6: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

� Akzeptoren� Automaten ohne Ausgabe

� Transduktoren� Automaten mit Ausgabe

� deterministisch

Typen endlicher Automaten

o

qi

p →

qoi

p → :

� deterministisch� jedem Paar [p,i] ist ein Paar [o,q]

eindeutig zugeordnet� nicht-deterministisch

� einem Paar [p,i] können mehreremögliche Paare [o,q] zugeordnet sein

� stochastisch� jedem Paar [p,i] ist für ein Paar [o,q]

ein Wahrscheinlichkeitsmaß zugeordnet

6

p qio

pq2

q1

io2/w2

io1/w1

pq2

q1

io2

io1

© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 7: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Typen endlicher AutomatenBeispiele

Akzeptor Transduktordeterministisch

nicht-deterministisch

0 1[ʃ]S q

[t]t 2 3

[a]a dt

4[t] tt

ε0 1S qt 2 3a

6

d 4

t 7

5t

t

© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

7

stochastisch

nicht-deterministisch

0 1S/1 qt/1 2 3a/1

6

d/.65 4

t/.35 7

5t/1

t/1[t]

0 1[ʃ]

S/1 q[t]t/1 2 3

[a]a/1

6

[t]d/.65 4

t/.35 7

5t/1

t/1ε

ε

01S

7

t 2 3a

9

d 4

tS t a6 8 10

5t

t0 1[ʃ]S q

[t]t 2 3

[a]a

6

[t]d 4

t 7

5t

ε[t]

Page 8: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Inhalt

� Informelle Einführung: Was sind endliche Automaten?� Abstrakte Automaten� Endliche abstrakte Automaten� Beispiele� Typen endlicher Automaten

� Akzeptoren, Transduktoren� Akzeptoren, Transduktoren� deterministisch, nicht-deterministisch, stochastisch

� Definitionen� Abstrakte Automaten als mathematische Strukturen� Endliche abstrakte Automaten

� Einordnung endlicher Automaten� Automatentheorie: Art des Speichers� Theorie formaler Sprachen: Strukturelle Komplexität

8© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 9: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Definitionen Abstrakte Automaten als mathematische Strukturen: Historie

� David A. Huffman (1954), George H. Mealy (1955) und Edward F. Moore (1956)� untersuchten Schaltkreise� beschrieben voneinander unabhängig den konventionellen

deterministischen Automaten in ähnlichen Variantendeterministischen Automaten in ähnlichen Varianten� Huffman entwickelte den Begriff des abstrakten Automaten� Mealy und Moore führten abstrakte Automaten als

mathematische Strukturen ein.

9© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 10: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

DefinitionenMathematische Struktur

� Eine Struktur S ist eine Zusammenfassung einer Menge und ausgewählter interessanter Eigenschaften dieser Menge

� Relationen, Funktionen und/oder � ausgezeichnete Elemente

� die Eigenschaften definieren eine Struktur auf der Menge� Darstellung als Tupel S = (Menge,

Relation1, …, Relationo,ausgezeichnetes Element1, .., Ep)

� Beispiel (ℕ, +,×, 0,1)� Name dieser Beispielstruktur in der abstrakten Algebra: Semiring� Semiringe spielen in der Theorie endlicher Automaten eine

grundlegende Rolle

10© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 11: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

DefinitionenDeterminierter abstrakter AutomatMengentheoretische Definition (Version: Starke 1.1)

determinierter abstrakter Automat (Starke 1969: 22)A = (X, Y, Z, γ) heißt determinierter abstrakter Automat, falls

a) X, Y, Z beliebige nichtleere Mengen sind, undb) γ eine auf Z × X definierte Funktion ist, deren Werte in Y

× Z liegen. ■× Z liegen. ■

InterpretationX Menge der EingabesymboleY Menge der AusgabesymboleZ Menge der Zustände

11

Z × X

a b

0 Y × Z Y × Z

A 1 B 1

© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 12: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

DefinitionenDeterminierter abstrakter AutomatMengentheoretische Definition(Version: Starke 1.2 = Version Mealy 1955)

determinierter Mealy-Automat (Starke 1969: 22)Ein determinierter Automat A = (X, Y, Z, γ) heißt determinierter

Mealy-Automat, falls für alle x ∈X, z∈Z, γ(z,x) = [λ(z,x),δ(z,x)] ist,

wobei λ die Ergebnis und δ die Überführungsfunktion von A wobei λ die Ergebnis und δ die Überführungsfunktion von A ist. ■

InterpretationX Menge der EingabesymboleY Menge der AusgabesymboleZ Menge der Zustände

12

λ(z,x )

a b

0 A B

δ(z,x )

a b

0 1 1

© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 13: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

DefintionenNichtdeterministischer und stochastischer AutomatMengentheoretische Definition

nichtdeterministischer Automat (Starke 1969: 121)B = (X, Y, Z, h) heißt nicht-deterministischer Automat, falls

a) X, Y, Z nichtleere Mengen sind, undb) h eine eindeutige Abbildung von Z × X in P*(Z × Y) ist. ■

(Starke 1969: 121)

stochastischer Automat (Starke 1969: 211)C = (X, Y, Z, H) heißt stochastischer Automat, wenn

a) X, Y, Z beliebige nichtleere Mengen sind, undb) H eine auf Z × X definierte Funktion ist, die diskrete

Wahrscheinlichkeitsmaße über Y × Z als Werte H(z,x) hat ■

13© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 14: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

DefinitionenEndlicher AutomatMengentheoretische Definition

endlicher determinierter Automat (Starke 1969: 25)Ein determinierter Automat A = [X,Y,Z,δ,λ] heißt X-endlich, Y-

endlich bzw. Z-endlich bzw. (X,Y)-endlich usw., wenn die jeweils angegebenen Mengen endlich sind. (X,Y,Z)-endlicheAutomaten bezeichnen wir schlechthin als endlich ■Automaten bezeichnen wir schlechthin als endlich ■

(X,Y,Z)-endliche nichtdeterministische Automaten …endlich.

(X,Y,Z)-endliche stochastische Automaten … endlich.

14© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 15: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

DefinitionenMengentheoretische Notation endlicher Automaten – eine Standardnotation

p,q ∈ Q Zustände

EA = (Q,q0,F,Σ,∆,R,δ,σ,ρ)

o

Ausgabesymbol

w /

Gewicht

F ⊂ Q Endzustände

q0 ∈ Q Startzustand

15

δ(p,i) = q

σ(p,i,q) = o

i ∈ Σ

o ∈ ∆Eingabesymbole

Ausgabesymbole

Zustandsübergangsfunktion

Ausgabefunktion

p qi

o

Zustand FolgezustandEingabesymbol

w /

w ∈ R Gewichte

ρ(p,i,o,q) = w Gewichtungsfunktion

F ⊂ Q Endzustände

© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 16: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Inhalt

� Informelle Einführung: Was sind endliche Automaten?� Abstrakte Automaten� Endliche abstrakte Automaten� Beispiele� Typen endlicher Automaten

� Akzeptoren, Transduktoren� Akzeptoren, Transduktoren� deterministisch, nicht-deterministisch, stochastisch

� Definitionen� Abstrakte Automaten als mathematische Strukturen� Endliche abstrakte Automaten

� Einordnung endlicher Automaten� Automatentheorie: Art des Speichers� Theorie formaler Sprachen: Strukturelle Komplexität

16© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 17: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Einordnung endlicher AutomatenAutomatentheorieKlassifikation von Algorithmen nach der Art des Spe ichers

• klassifiziert Algorithmen nach der Art des Speichers, der für die Implementierung zum Merken von Zwischergebnissengebraucht wird

Automat Speicher Turingmaschine unendlich großer Speicher

17

Turingmaschine unendlich großer Speicher linear beschränkter Automat endlich großer Speicher Kellerautomat (Push Down Automaton)

Kellerspeicher (Stack)

endlicher Automat kein zusätzlicher Speicher

Speziali-sierungen

© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 18: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Einordnung endlicher AutomatenAutomatentheorieEndliche Automaten haben kein Gedächtnis

� Mengen der Zustände, der Eingabesignale, der Ausgabesignale sind endlich

� kein Gedächtnis zur Speicherung durchlaufener Zustände:� Übergang von Zustand zur Zeit t in Zustand zur Zeit t+1 nur

abhängig von� Zustand zur Zeit t und � Zustand zur Zeit t und � Eingabe im Zustand zur Zeit t

� Vorhergehende Zustände nur dadurch wirksam, dass� sie über eine bestimmte Eingabe in den aktuellen Zustand

geführt haben, und � dieser aktuelle Zustand ein bestimmtes Ergebnis repräsentiert.

18

B Bu Buc BuchStart B u c h

© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 19: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Einordnung endlicher AutomatenTheorie formaler Sprachenmit endlichen Automaten ist die Klasse der reguläre n Sprachen erkennbar und generierbar

Sprachklassen nach struktureller Komplexität (Chomsky-Hierarchie)

Sprachklasse Hierarchie Grammatik Regelformat Automat rekursiv aufzählbare Sprachen

Typ 0 allgemeine Regelgrammatik

βα → εα ≠

Turing-Maschine

kontext- Typ 1 kontextsensitive βαααα →A linear

19

kontext-sensitive Sprachen

Typ 1 kontextsensitive Grammatik

2121 βαααα →A

εβ ≠ linear beschränkter Automat

kontextfreie Sprachen

Typ 2 kontextfreie Grammatik

α→A Kellerautomat

reguläre Sprachen

Typ 3 reguläre Grammatik arrechtsline

wA

wBA

→→

rlinkslineawA

BwA

→→

Endlicher Automat

Kettenterminale w TerminalenNon und Terminalen aus Ketten − α

le SymbolenonterminaBA ,

© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 20: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Äquivalenzen: Endliche Automaten, reguläre Sprachen, reguläre Ausdrücke

Reguläre Ausdrücke

de([mnrs]|“ssen“)

20

spezifizieren

akzeptieren

sind äquivalent

d0 1

e2

m3

nr

5s

4s 7

e6 n

Endliche Automaten

{dem, den, der, des, dessen}

Reguläre Sprachen

© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 21: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Literatur

� Hopcroft, John E. Rajeev Motwani und Jeffrey D. Ullman (2001). Einführung in die Automatentheorie, Formale Sprachen und Komplexität. Pearson Studiumengl. Original: Introduction to Automata Theory, Languages and Computation. Addison-Wesley.

� Hopcroft, John E. und Jeffrey D. Ullman (1988). Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. Bonn u. a.: Addison-Wesley, 1988 (engl. Original Introduction to automata theory, languages and computation). [Anm.: Diese Fassung enthält die Beweise]Fassung enthält die Beweise]

� Huffman, D. A. (1954). The synthesis of sequential switching circuits. J. Franklin Inst. 257: 3-4, S. 161-190 und 275-303

� Lawson, Mark V. (2005). Finite automata. In: Hritsu-Varsakelis, D. und W.S.Levine (Hg).: Handbook of networked and embedded Control Systems.

� Lawson, Mark V. (2004). Finite Automata. In: D. Hristu-Varsakelis and W. S. Levine (eds.): Handbook of networked and embedded control systems

� Mealy, George H. (1955). A method for synthesizing sequential circuits. Bell System Technical Journal 34:5, 1045-1079

� Moore, Edward F. (1956). Gedanken experiments on sequential machines. In: Automata Studies, S. 129-153, Princeton: Princeton University Press

� Starke, Peter H. (1969). Abstrakte Automaten. VEB Deutscher Verlag der Wissenschaften: Berlin (ältere, aber sehr gute mathematische Darstellung)

21© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 22: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Copyright

� © 2009 Karin Haenelt.All rights reserved. The German Urheberrecht shall be applied to these slides. In accordance with these laws these slides are a publication which may be quoted and usedfor non-commercial purposes, if the bibliographic data is included as described below.

� Please quote correctly. If you use the presentation or parts of it for educational and scientificpurposes, please include the bibliographic data (author, title, date, page, URL) in yourpublication (book, paper, course slides, etc.).publication (book, paper, course slides, etc.).

� Deletion or omission of the footer (with name, data and copyright sign) is not permitted� Bibliographic data. Karin Haenelt (2010). Endliche Automaten. Einführung in den

Themenbereich. Kursfolien 18.4.2010 http://kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA-IntroV4.pdf

� Any further use requires the prior permission in writing from the author.� For commercial use: No commercial use is allowed without written permission from the

author. In case you are interested in commercial use please contact the author.

� Court of Jurisdiction is Darmstadt.

22© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010

Page 23: Endliche Automaten Einführung in den Themenbereich …kontext.fraunhofer.de/haenelt/kurs/folien/Haenelt_FSA_Intro_V4.pdf · Informelle Einführung Abstrakter Automat ein abstrakter

Versionen

� v 4.1- 18.04.2010, v 4.0 – 30.03.2009� V03.01 – 16.04.2008� V03.00 – 12.04.2008� V02.03 - 14.04.2007� V02.02 - 11.04.2007� V02.01 - 15.04.2006

23© Karin Haenelt,Endliche Automaten, Einführung, V 4.1, 18.04.2010