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

1

Endliche Automaten

Einführung in den Themenbereich

Karin Haenelt

18.04.2010

Inhalt

Informelle Einführung: Was sind endliche Automaten? Abstrakte Automaten Endliche abstrakte Automaten Beispiele T ypen endlicher Automaten

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

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 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

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


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

Endliche Automaten: BeispieleKippschalter und Lexikon

5

anausStart

drücken

drücken drücken aus an an aus

d0 1

e2

m3

nr

5s

4s 7

e6 n

Lexikon

Schalter


Akzeptoren Automaten ohne Ausgabe

Transduktoren Automaten mit Ausgabe

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

Typen endlicher Automaten

6

p qio

qi

p

qoi

p :

pq2

q1

io2/w2

io1/w1

pq2

q1

io2

io1


Typen endlicher AutomatenBeispiele


7

Akzeptor Transduktordeterministisch

stochastisch

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

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

[t]

Inhalt






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 Varianten Huffman entwickelte den Begriff des abstrakten Automaten Mealy und Moore führten abstrakte Automaten als

mathematische Strukturen ein.


DefinitionenMathematische Struktur

Eine Struktur 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 = (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


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, und

b) γ eine auf Z X definierte Funktion ist, deren Werte in Y Z liegen. ■

Interpretation

X Menge der Eingabesymbole

Y Menge der Ausgabesymbole

Z Menge der Zustände

11

Z × X

a b

0 Y × Z Y × Z

A 1 B 1


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, zZ,

γ(z,x) = [λ(z,x),δ(z,x)] ist,wobei λ die Ergebnis und δ die Überführungsfunktion von A ist. ■

Interpretation

X Menge der Eingabesymbole

Y Menge der Ausgabesymbole

Z Menge der Zustände

12

λ(z,x )

a b

0 A B

δ(z,x )

a b

0 1 1


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, und

b) h eine eindeutige Abbildung von Z X in *(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, und

b) H eine auf Z X definierte Funktion ist, die diskrete Wahrscheinlichkeitsmaße über Y Z als Werte H(z,x) hat ■


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)-endliche Automaten bezeichnen wir schlechthin als endlich ■

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

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


DefinitionenMengentheoretische Notation endlicher Automaten – eine Standardnotation

15

p,q Q

δ(p,i) = q

σ(p,i,q) = o

i Σo Δ

Zustände

Eingabesymbole

Ausgabesymbole

Zustandsübergangsfunktion

Ausgabefunktion

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

p qi

o

Zustand FolgezustandEingabesymbol

Ausgabesymbol

w /

Gewicht

w Gewichte

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

F Q Endzustände

q0 Q Startzustand


Inhalt






Einordnung endlicher AutomatenAutomatentheorieKlassifikation von Algorithmen nach der Art des Speichers

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

17

Automat Speicher 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


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 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


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

Sprachklassen nach struktureller Komplexität (Chomsky-Hierarchie)

19

Sprachklasse Hierarchie Grammatik Regelformat Automat rekursiv aufzählbare Sprachen

Typ 0 allgemeine Regelgrammatik

Turing-Maschine

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 ,


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

20

spezifizieren

akzeptieren

sind äquivalent

Reguläre Ausdrücke

de([mnrs]|“ssen“)

d0 1

e2

m3

nr

5s

4s

7e

6n

Endliche Automaten

{dem, den, der, des, dessen}

Reguläre Sprachen


Literatur

Hopcroft, John E. Rajeev Motwani und Jeffrey D. Ullman (2001). Einführung in die Automatentheorie, Formale Sprachen und Komplexität. Pearson Studium engl. 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]

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)


http://www.pearson-studium.de/

http://www.ma.hw.ac.uk/~markl/preprints/Lawson.pdf

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 used for 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 scientific purposes, please include the bibliographic data (author, title, date, page, URL) in your 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.


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

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


Date post:	05-Apr-2015
Category:	Documents
Upload:	hedda-weller
View:	118 times
Download:	8 times

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

Documents