39
1 Überführung regulärer Ausdrücke in endliche Automaten Der Algorithmus von Glushkov und McNaughton/Yamada Karin Haenelt 14.5.2010

Karin Haenelt 14.5.2010

  • Upload
    rowa

  • View
    38

  • Download
    1

Embed Size (px)

DESCRIPTION

Überführung regulärer Ausdrücke in endliche Automaten Der Algorithmus von Glushkov und McNaughton/Yamada. Karin Haenelt 14.5.2010. Inhalt. Quelle Prinzip des Algorithmus Algorithmus Parsing des regulären Ausdrucks Erkennung Syntaxbaum - PowerPoint PPT Presentation

Citation preview

Page 1: Karin  Haenelt 14.5.2010

1

Überführung regulärer Ausdrücke in endliche Automaten

Der Algorithmus von Glushkov und McNaughton/Yamada

Karin Haenelt

14.5.2010

Page 2: Karin  Haenelt 14.5.2010

Inhalt

Quelle Prinzip des Algorithmus Algorithmus

Parsing des regulären Ausdrucks Erkennung Syntaxbaum Funktionen nullable, firstpos, lastpos und followpos

Konstruktion des Automaten Ein linguistisches Beispiel Implementierung Komplexität

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

2

Page 3: Karin  Haenelt 14.5.2010

Quelle

Der Algorithmus wurde unabhängig entwickelt von Viktor M. Glushkov (1960, 1961) Robert McNaughton und Hisao Yamada (1960)

3© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 4: Karin  Haenelt 14.5.2010

Inhalt

Quelle Prinzip des Algorithmus Algorithmus

Parsing des regulären Ausdrucks Erkennung Syntaxbaum Funktionen nullable, firstpos, lastpos und followpos

Konstruktion des Automaten Ein linguistisches Beispiel Implementierung Komplexität

4© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 5: Karin  Haenelt 14.5.2010

Prinzip des Algorithmus

bestimmte Positionen des regulären Ausdrucksstehen inbestimmten Folgerelationen in den zugehörigen Zeichenketten

die Folgerelationen sind eindeutig bestimmt über die Abfolge und Definition der Operatoren des regulären Ausdrucks

die Folgerelationen legen die Menge der möglichen Zustände und die zeitliche Ordnung der Zustände fest

es geht also darum die Folgerelationen zu berechnen aus dem Ergebnis der Berechnung den DEA zu konstruieren

5© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 6: Karin  Haenelt 14.5.2010

Prinzip des AlgorithmusBeispiel -1-

wie sehen dieZeichenketten aus,die dieser Ausdruck beschreibt?

welchem Zeichen kann welches Zeichen folgen?

6

RE = dete? adje* nomn REp = dete?1 adje*2 nomn3 #4

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 7: Karin  Haenelt 14.5.2010

Prinzip des AlgorithmusBeispiel -2-

mögliche Startpositionen

mögliche Folgepositionen

7

RE = dete? adje* nomn REp = dete?1 adje*2 nomn3 #4

dete1

adje2

nomn3

dete1

adje2

adje2

nomn3

#4

adje2

nomn3

nomn3

dete1

adje2

nomn3

#4

adje2, nomn3

adje2, nomn3

#4

-

dete1

adje2 (da dete1 optional ist)nomn3 (dete1 und adje2 opt.)

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 8: Karin  Haenelt 14.5.2010

Prinzip des AlgorithmusBeispiel -3-

8

RE = dete? adje* nomn REp = dete?1 adje*2 nomn3 #4

dete1

adje2

nomn3

dete1

adje2

adje2

nomn3

#4

adje2

nomn3

nomn3

1,2,3 2,3 4dete1

adje2

adje2

nomn3

nomn3

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 9: Karin  Haenelt 14.5.2010

Prinzip des AlgorithmusBeispiel -4-

Start- und Folgepositionen sind eindeutig bestimmt durch die Semantik der Operatoren

Wenn E= dete? adje* nomn in eine Zeichenkette aus L(E) umgewandelt wird, kann das erste Zeichen der Zeichenkette sein dete weil es vorne steht adje wegen des ?-Operators über dete nomn wegen des Stern-Operators über adje

9

1,2,3

Startzustand aus Positionsmenge {1,2,3}

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 10: Karin  Haenelt 14.5.2010

Prinzip des Algorithmus

Wie berechnet man die Start- und Folgepositionen? Erkennung des Ausdrucks mit dem Algorithmus von

Hopcroft/Ullman 1988 Aufbau eines binären Syntaxbaumes

Blätter: Positionen innere Knoten: Operatoren

Berechnung der Abfolgen während der bottom-up-Konstruktion des Syntaxbaumes

Wie erzeugt man den Automaten? auf der Basis der Abfolgeinformation nach dem Algorithmus

von Glushkov bzw. MacNaughton/Yamada

10© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 11: Karin  Haenelt 14.5.2010

Inhalt

Quelle Prinzip des Algorithmus Algorithmus

Parsing des regulären Ausdrucks Erkennung Syntaxbaum Funktionen nullable, firstpos, lastpos und followpos

Konstruktion des Automaten Ein linguistisches Beispiel Implementierung Komplexität

11© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 12: Karin  Haenelt 14.5.2010

Algorithmus

12

Parsing des regulären Ausdrucks

Algorithmus von Hopcroft/Ullman 1988 Erweiterung 1

Konstruktion des Syntaxbaumes

- binärer Baum - bottom-up-Konstruktion - Blätter: Positionen - innere Knoten: Operatoren Erweiterung 2

Funktionen nullable, firstpos, lastpos und followpos

- Berechnung der Positionsfolge über die Struktur des Syntaxbaumes

- bottom-up-Anwendung der Funktionen auf die Operator-Knoten im Syntaxbaum

Erzeugung eines DEA

Algorithmus von Glushkov bzw. McNaughton/Yamada

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 13: Karin  Haenelt 14.5.2010

Der Syntaxbaum

13

(a1|b2)*a3b4b5#6

a b

a

b

b

#

|

*

1 2

3

4

5

6

Aho/Sethi/Ullmann 1986: 139

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 14: Karin  Haenelt 14.5.2010

Die Funktionennullable, firstpos, lastpos und followpos

Der Automat wird aufgebaut aus den Ergebnissen von firstpos(root) und followpos(i)

Zur Ermittlung von followpos(i)wird firstpos(n) und lastpos(n) benötigt

Zur Ermittlung von firstpos(n) und lastpos(n)wird nullable(n) benötigt

nullable(n) ist knotenspezifisch definiert Die Funktionen werden bottom-up auf den Syntaxbaum

angewendet

14© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 15: Karin  Haenelt 14.5.2010

Die Funktionennullable, firstpos, lastpos und followpos

Def Sei E der Teilausdruck, der durch den Syntaxbaum mit Wurzel n repräsentiert wird, und E’ ein regulärer Ausdruck, in dem jedes Symbol durch seine Position ersetzt ist, dann ist

15

nullable(n) die Feststellung, ob auch die leere Kette eine Zeichenkette aus L(E’) sein kann. nullable(n) liefert den Wert true, wenn n nullable ist, andernfalls den Wert false.

firstpos(n) die Menge der Positionen, die am Anfang einer Kette aus L(E’) stehen können

lastpos(n) die Menge der Positionen, die am Ende einer Kette aus L(E’) stehen können

followpos(i) die Menge der Positionen in L(E’), die Position i folgen können. ■

Aho/Sethi/Ullmann 1986: 138

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 16: Karin  Haenelt 14.5.2010

Die Berechnung der Funktionennullable, firstpos, lastpos und followpos

16

Knoten n nullable(n) firstpos(n) lastpos(n) terminaler ε-Knoten

true

terminaler Knoten mit Position i

false {i} {i}

nullable(c1) OR nullable(c2)

firstpos(c1) firstpos(c2)

lastpos(c1) lastpos(c2)

nullable(c1) AND nullable(c2)

if nullable(c1) then firstpos(c1) firstpos(c2) else firstpos(c1)

if nullable(c2) then lastpos(c1) lastpos(c2) else lastpos(c2)

true

firstpos(c1)

lastpos(c1)

c1 c2

|

c1 c2

c1

*

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 17: Karin  Haenelt 14.5.2010

Der annotierte Syntaxbaum

17

(a1|b2)*a3b4b5#6 {1,2,3}

a b

a

b

b

#

|

*

{1} {1}

1 2

3

4

5

6

{2} {2}

{1,2} {1,2}

{3} {3}

{1,2,3} {3}

{4}

{4} {4}

{5}

{5} {5}

{6} {6}

{6}

{1,2} {1,2}

{1,2,3}

{1,2,3}

firstpos lastpos

nullable

Aho/Sethi/Ullmann 1986: 139

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 18: Karin  Haenelt 14.5.2010

Knoten n followpos(i) nur auf Positionen definiert

definiert keine Reihenfolge, keine Auswirkung auf followpos(i)

:)( 1clastposi )()()( 2cfirstposifollowposifollowpos

:)(nlastposi )()()( nfirstposifollowposifollowpos

Berechnung von followpos

18

c1 c2

|

c1 c2

c1

*

n

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 19: Karin  Haenelt 14.5.2010

Beispiel zur Berechnung von followpos:Stern-Knoten

19

a b

|

*

{1} {1}1 2

{2} {2}

{1,2} {1,2}

{1,2} {1,2}n

followpos(1) = {1,2}followpos(2) = {1,2}

followpos(1).addAll( {1,2})followpos(2).addAll ({1,2})

)(nlastposi

:)(nlastposi)()()( nfirstposifollowposifollowpos

)(nfirstpos

(a|b)*

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 20: Karin  Haenelt 14.5.2010

Beispiel zur Berechnung von followpos:Konkatenations-Knoten

20

:)( 1clastposi)()()( 2cfirstposifollowposifollowpos

(a|b)*a

a b

a

|

*

{1} {1}1 2

3

{2} {2}

{1,2} {1,2}

{3} {3}

{3}

{1,2} {1,2}

n{1,2,3} ●

followpos(1) = {1,2,3}followpos(2) = {1,2,3}

followpos(1).addAll( {3})followpos(2).addAll ({3})

)( 1clastposi )( 2cfirstpos

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 21: Karin  Haenelt 14.5.2010

Konstruktion der Automaten aus den followpos-Mengen

21

1,2,3,6

1,2,3

1,2,3,4

1,2,3,5

a

a a a

b b

b b

1

23 4 5 6

ab b #b

ba

a

Knoten followpos 1 {1,2,3} 2 {1,2,3} 3 {4} 4 {5} 5 {6} 6 -

NEA

DEA

Aho/Sethi/Ullmann 1986: 136-140

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 22: Karin  Haenelt 14.5.2010

Algorithmus von Gluskov bzw. McNaughton/Yamada: Konstruktion des DEA

22

Eingabe Ein Syntaxbaum für einen regulären Ausdruck E#, annotiert durch die Funktionen firstpos(n) und followpos(i)

Ausgabe Ein DEA, der L(E) erkennt Methode initial ist firstpos(root) der einzige unmarkierte Zustand in

Dstates while (es gibt einen unmarkierten Zustand T in Dstates) do begin markiere T; for jedes Eingabesymbol a do begin sei U die Menge der Positionen in followpos(p) für eine Position p in T, und das Symbol in Position p ist a if (U ist nicht leer und nicht in Dstates) then füge U als unmarkierten Zustand zu Dstates hinzu Dtran[T,a] := U end end

Aho/Sethi/Ullmann 1986: 141© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 23: Karin  Haenelt 14.5.2010

DStates Position Eingabesymbole a b T0 firstpos(root)

= {1,2,3} 1 (followpos(1) = {1,2,3}) - 2 - (followpos(2) = {1,2,3}) 3 (followpos(3) = {4}) - = {1,2,3,4} = {1,2,3}

T1 {1,2,3,4} 1 (followpos(1) = {1,2,3}) - 2 - (followpos(2) = {1,2,3}) 3 (followpos(3) = {4}) - 4 - followpos(4) = {5}) = {1,2,3,4} = {1,2,3,5}

T2 {1,2,3,5} 1 (followpos(1) = {1,2,3}) - 2 - (followpos(2) = {1,2,3}) 3 (followpos(3) = {4}) - - 5 - (followpos(5) = {6}) = {1,2,3,4} = {1,2,3,6}

T3 {1,2,3,6} 1 (followpos(1) = {1,2,3}) - 2 - (followpos(2) = {1,2,3}) 3 (followpos(3) = {4}) - 6 - - = {1,2,3,4} = {1,2,3}

23© Karin Haenelt,

RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 24: Karin  Haenelt 14.5.2010

24

DStates Pos Eingabesymbole a b T0 first (root)

= {1,2,3} 1 follow (1) = {1,2,3} - 2 - follow (2) = {1,2,3} 3 follow (3) = {4} - = {1,2,3,4} = {1,2,3}

T1 {1,2,3,4} 1 follow (1) = {1,2,3} - 2 - follow (2) = {1,2,3} 3 follow (3) = {4} - 4 - follow (4) = {5} = {1,2,3,4} = {1,2,3,5}

T2 {1,2,3,5} 1 follow (1) = {1,2,3} - 2 - follow (2) = {1,2,3} 3 follow (3) = {4} - - 5 - follow (5) = {6} = {1,2,3,4} = {1,2,3,6}

T3 {1,2,3,6} 1 follow (1) = {1,2,3} - 2 - follow (2) = {1,2,3} 3 follow (3) = {4} - 6 - - = {1,2,3,4} = {1,2,3}

Position i

mögliche Nachfolgepositionen follow(i)

a1 {a1,b2,a3} b2 {a1,b2,a3} a3 {b4} b4 {b5} b5 {#6} #6 -

1,2,3,6

1,2,3

1,2,3,4

1,2,3,5

a1,a3

a1,a3

a1,a

3 a1,a3

b2 b2

b2,b4 b2,b5

DEA

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 25: Karin  Haenelt 14.5.2010

Inhalt

Quelle Prinzip des Algorithmus Algorithmus

Parsing des regulären Ausdrucks Erkennung Syntaxbaum Funktionen nullable, firstpos, lastpos und followpos

Konstruktion des Automaten Ein linguistisches Beispiel Implementierung Komplexität

25© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 26: Karin  Haenelt 14.5.2010

Ein linguistisches Beispiel, 1a

{1,2,3}

#

{1}

4

5

*{3} {3}

{1,2,3}

{4}

{4} {4}

{5}

{5} {5}{1,2,3,4}

{1,2,3,4}

ε

|

{1}1

{ } { }

{1,2} {1,2}

dete3

{3} {3}adje

nomn

dete? adje* nomnVariante 1:• Darstellung von a? durch (a|ε)• bei Automatenkonstruktion

werden für ε keine Kanten konstruiert (nur für Eingabe- Symbole a)

2nullablefirstposlastpos

{i}{i}

26© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 27: Karin  Haenelt 14.5.2010

Ein linguistisches Beispiel, 1b

{1,2}

#

{1}

3

4

*{2} {2}

{1,2}

{3}

{3} {3}

{4}

{4} {4}{1,2,3}

{1,2,3}

?

{1}1

{1}

dete2

{2} {2}adje

nomn

dete? adje* nomnVariante 2:direkte Angabe von Regeln für ?: nullable(n) := true firstpos (n) := firstpos(left) lastpos(n) := lastpos(left)

{1}

nullablefirstposlastpos

{i}{i}

27© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 28: Karin  Haenelt 14.5.2010

Ein linguistisches Beispiel, 2a+b

Knoten Symbol followpos Symbole 1 dete1 {2,3} adje2, nomn3 2 adje2 {2,3} adje2, nomn3 3 nomn3 {4} #4 4 #4 - -

dete? adje* nomn

1,2,3

2,3 4start

adje

dete

nomn

nomn

adje

Knoten Symbol followpos Symbole 1 dete1 {3,4} adje3, nomn4 2 ε2 {3,4} adje3, nomn4 3 adje3 {3,4} adje3, nomn4 4 nomn4 {5} #4 5 #5 - -

1,2,3,4

3,4 5start

adje

dete

nomn

nomn

adje

Variante 2 für ? Variante 1 für ?

28© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 29: Karin  Haenelt 14.5.2010

Inhalt

Quelle Prinzip des Algorithmus Algorithmus

Parsing des regulären Ausdrucks Erkennung Syntaxbaum Funktionen nullable, firstpos, lastpos und followpos

Konstruktion des Automaten Ein linguistisches Beispiel Implementierung Komplexität

29© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 30: Karin  Haenelt 14.5.2010

Implementierung

Einfügen der Konstruktionsschritte für einen Parsebaum bzw. Syntaxbaum

Zuordnung von Baumkonstruktoren zu den Elementen des regulären Ausdrucks Terminalsymbole (Zeile 21) Klammern (Zeile 23, 27) unäre Operatoren (*,+,?) (Zeile 31)

binäre Operatoren (·, |) (Zeile 4, 13)

*

|

30© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 31: Karin  Haenelt 14.5.2010

class TreeNode { String info; int type; TreeNode left;

TreeNode right; boolean nullable; HashSet<TreeNode> firstpos; HashSet<TreeNode> lastpos; HashSet<TreeNode> followpos; public TreeNode(int type, TreeNode left, TreeNode right) { this.type = type;

this.left = left; this.right = right; switch(type) { case OR:

nullable = left.nullable() || right.nullable(); firstpos = new HashSet<TreeNode>(left.firstpos()); firstpos.addAll(right.firstpos()); lastpos = new HashSet<TreeNode>(left.lastpos()); lastpos.addAll(right.lastpos()); break;

case … } } }

Implementierung: TreeNode

31© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 32: Karin  Haenelt 14.5.2010

Definition der Knoten, 1

n ist ein Knoten mit Kennung : nullable(n) := false; firstpos(n) := ; lastpos(n) := ; n ist ein Knoten mit Kennung : nullable(n) := true; firstpos(n) := ; lastpos(n) := ; n ist ein Knoten mit Kennung i: nullable(n) := false; firstpos(n) := {i}; lastpos(n) := {i}; followpos(i) := ;

Brüggemann-Klein, 1992

32© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 33: Karin  Haenelt 14.5.2010

Definition der Knoten, 2

n ist ein Knoten mit Kennung | nullable(n) := nullable(left) or nullable(right); firstpos(n) := firstpos(left) firstpos(right); lastpos(n) := lastpos(left) lastpos(right); n ist ein Knoten mit Kennung • nullable(n) := nullable(left) and nullable(right); for each i in lastpos(left) do followpos(i) := followpos(i) firstpos(right); if nullable(left) then firstpos(n) := firstpos(left) firstpos(right); else firstpos(n) := firstpos(left); if nullable(right) then lastpos(n) := lastpos(left) lastpos(right); else lastpos(n) := lastpos(right);

Brüggemann-Klein, 1992

33© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 34: Karin  Haenelt 14.5.2010

Definition der Knoten, 3

n ist ein Knoten mit Kennung * nullable(n) := true; for each i in lastpos(left) do followpos(i) := followpos(i) firstpos(right); firstpos(n) := firstpos(left); lastpos(n) := lastpos(left);

Brüggemann-Klein, 1992

34© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 35: Karin  Haenelt 14.5.2010

Inhalt

Quelle Prinzip des Algorithmus Algorithmus

Parsing des regulären Ausdrucks Erkennung Syntaxbaum Funktionen nullable, firstpos, lastpos und followpos

Konstruktion des Automaten Ein linguistisches Beispiel Implementierung Komplexität

35© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 36: Karin  Haenelt 14.5.2010

Komplexität: Platz

maximale Anzahl der Zustände: 2p+1,p = Anzahl der Positionen

(Anzahl möglicher Teilmengen, die aus p Objekten gebildet werden können, beträgt 2p)

max. Anzahl wird in der Praxis kaum erreicht: der reg. Ausdruck schränkt Anzahl der möglichen

Teilmengen sehr stark ein Algorithmus konstruiert nur die tatsächlich vorkommenden

Teilmengen(lazy implementation der Teilmengen)

minimale Anzahl der Zustände: p+1(falls nur Konkatenation von Symbolen vorkommt)

Glushkov, 1961McNaughton/Yamada, 1960

36© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 37: Karin  Haenelt 14.5.2010

Komplexität: Zeit

Implementierungen mit kubischer Zeit Aho/Sethi/Ullman, 1986 Berry/Sethi, 1986

Implementierung mit quadratischer Zeit für allgemeine Ausdrücke (d.h. auch ambige) Brüggemann-Klein, 1992

Implementierung mit linearer Zeit für deterministische Ausdrücke Brüggemann-Klein, 1992

37© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 38: Karin  Haenelt 14.5.2010

Literatur

Quellen Glushkov, Viktor M.(1961). The abstract theory of automata. In: Russian Mathematical

Surveys 16, S. 1-53. Glushkov, Viktor M.(1960). On Synthesis Algorithm for Abstract Automata, Ukr.

Mathem. Zhurnal, 12(2), S.147-156 (in Russisch) McNaughton, Robert und Hisao Yamada (1960). Regular expressions and state

graphs for automata. In IEEE Transactions on Electronic Computers 9 (1): S. 39-47. Erläuterungen

Aho, Alfred V.; Sethi, Ravi und Jeffrey D. Ullman (1986). Compilers. Principles, Techniques and Tools. Addison-Wesley Publishing Company.

weitere Literatur Berry, Gérard und Ravi Sethi (1986). From regular expressions to deterministic

automata. In: Theoretical Computer Science 48 (3), S. 117-126. Brüggemann-Klein, Anne (1992). Regular Expressions into Finite Automata,

Proceedings of Latin '92, 1st Latin American Symposium on Theoretical Informatics, São Paulo, Brazil, April 6-10, 1992. (Lecture Notes in Computer Science 583) Heidelberg: Springer Verlag.

38© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

Page 39: Karin  Haenelt 14.5.2010

Versionen

14.05.2010, 9.5.2010, 14.09.2007, 05.05.2007, 21.05.2006, 20.03.2005

© Karin Haenelt,RegEx → FSA: Glushkov und MacNaughton/Yamada 14.5.2010

39