presentation

3 files changed, 629 insertions, 0 deletions

diff --git a/resources/literature/04-regulaere-ausdruecke.pdf b/resources/literature/04-regulaere-ausdruecke.pdf
new file mode 100644
index 0000000..fe4e985
--- /dev/null
+++ b/resources/literature/04-regulaere-ausdruecke.pdf
diff --git a/resources/literature/GNfaToDfa.cs b/resources/literature/GNfaToDfa.cs
new file mode 100644
index 0000000..df88b1d
--- /dev/null
+++ b/resources/literature/GNfaToDfa.cs
@@ -0,0 +1,629 @@
+// RegExp -> NFA -> DFA -> Graph in Generic C#

+// This program requires .Net version 2.0.

+// Peter Sestoft (sestoft@dina.kvl.dk) 

+// Java 2000-10-07, GC# 2001-10-23, 2003-09-03, 2004-07-26, 2006-03-05

+

+// This file contains, in order:

+//   * A class Nfa for representing an NFA (a nondeterministic finite 

+//     automaton), and for converting it to a DFA (a deterministic 

+//     finite automaton).  Most complexity is in this class.

+//   * A class Dfa for representing a DFA, a deterministic finite 

+//     automaton, and for writing a dot input file representing the DFA.

+//   * Classes for representing regular expressions, and for building an 

+//     NFA from a regular expression

+//   * A test class that creates an NFA, a DFA, and a dot input file 

+//     for a number of small regular expressions.  The DFAs are 

+//     not minimized.

+

+using System;

+using System.Text;

+using System.Collections;

+using System.Collections.Generic;

+using System.IO;

+

+// A set represented as the collection of keys of a Dictionary

+

+class Set<T> : ICollection<T> {

+  // Only the keys matter; the type bool used for the value is arbitrary

+  private Dictionary<T,bool> dict;

+  public Set() { 

+    dict = new Dictionary<T,bool>();

+  }

+

+  public Set(T x) : this() { 

+    Add(x);

+  }

+

+  public Set(IEnumerable<T> coll) : this() {

+    foreach (T x in coll) 

+      Add(x);

+  }

+

+  public Set(T[] arr) : this() {

+    foreach (T x in arr) 

+      Add(x);

+  }

+

+  public bool Contains(T x) {

+    return dict.ContainsKey(x);

+  }

+

+  public void Add(T x) {

+    if (!Contains(x))

+      dict.Add(x, false);

+  }

+

+  public bool Remove(T x) {

+    return dict.Remove(x);

+  }

+

+  public void Clear() {

+    dict.Clear();

+  }

+

+  public bool IsReadOnly {

+    get { return false; } 

+  }

+  

+  public IEnumerator<T> GetEnumerator() {

+    return dict.Keys.GetEnumerator();

+  }

+

+  IEnumerator IEnumerable.GetEnumerator() {

+    return GetEnumerator();

+  }

+

+  public int Count {

+    get { return dict.Count; }

+  }

+  

+  public void CopyTo(T[] arr, int i) {

+    dict.Keys.CopyTo(arr, i);

+  }

+

+  // Is this set a subset of that?

+  public bool Subset(Set<T> that) { 

+    foreach (T x in this)

+      if (!that.Contains(x))

+        return false;

+    return true;            

+  }

+

+  // Create new set as intersection of this and that

+  public Set<T> Intersection(Set<T> that) { 

+    Set<T> res = new Set<T>();

+    foreach (T x in this)

+      if (that.Contains(x))

+        res.Add(x);

+    return res;

+  }

+

+  // Create new set as union of this and that

+  public Set<T> Union(Set<T> that) { 

+    Set<T> res = new Set<T>(this);

+    foreach (T x in that)

+      res.Add(x);

+    return res;

+  }

+

+  // Compute hash code -- should be cached for efficiency

+  public override int GetHashCode() { 

+    int res = 0;

+    foreach (T x in this)

+      res ^= x.GetHashCode();

+    return res;

+  }

+

+  public override bool Equals(Object that) { 

+    if (that is Set<T>) {

+      Set<T> thatSet = (Set<T>)that;

+      return thatSet.Count == this.Count 

+        && thatSet.Subset(this) && this.Subset(thatSet);

+    } else

+      return false;

+  }

+

+  public override String ToString() {

+    StringBuilder res = new StringBuilder();

+    res.Append("{ ");

+    bool first = true;

+    foreach (T x in this) {

+      if (!first) 

+        res.Append(", ");

+      res.Append(x);

+      first = false;

+    }

+    res.Append(" }");

+    return res.ToString();

+  }

+}

+

+// ----------------------------------------------------------------------

+

+// Regular expressions, NFAs, DFAs, and dot graphs

+// sestoft@dina.kvl.dk * 

+// Java 2001-07-10 * C# 2001-10-22 * Gen C# 2001-10-23, 2003-09-03

+

+// In the Generic C# 2.0 version we 

+//  use Queue<int> and Queue<Set<int>> for worklists

+//  use Set<int> for pre-DFA states

+//  use List<Transition> for NFA transition relations

+//  use Dictionary<Set<int>, Dictionary<String, Set<int>>>

+//  and Dictionary<int, Dictionary<String, int>> for DFA transition relations

+

+/* Class Nfa and conversion from NFA to DFA ---------------------------

+

+  A nondeterministic finite automaton (NFA) is represented as a

+  Map from state number (int) to a List of Transitions, a

+  Transition being a pair of a label lab (a String, null meaning

+  epsilon) and a target state (an int).

+

+  A DFA is created from an NFA in two steps:

+

+    (1) Construct a DFA whose each of whose states is composite,

+        namely a set of NFA states (Set of int).  This is done by

+        methods CompositeDfaTrans and EpsilonClose.

+

+    (2) Replace composite states (Set of int) by simple states

+        (int).  This is done by methods Rename and MkRenamer.

+

+  Method CompositeDfaTrans works as follows: 

+

+    Create the epsilon-closure S0 (a Set of ints) of the start

+    state s0, and put it in a worklist (a Queue).  Create an

+    empty DFA transition relation, which is a Map from a

+    composite state (an epsilon-closed Set of ints) to a Map

+    from a label (a non-null String) to a composite state.

+

+    Repeatedly choose a composite state S from the worklist.  If it is

+    not already in the keyset of the DFA transition relation, compute

+    for every non-epsilon label lab the set T of states reachable by

+    that label from some state s in S.  Compute the epsilon-closure

+    Tclose of every such state T and put it on the worklist.  Then add

+    the transition S -lab-> Tclose to the DFA transition relation, for

+    every lab.

+

+  Method EpsilonClose works as follows: 

+

+    Given a set S of states.  Put the states of S in a worklist.

+    Repeatedly choose a state s from the worklist, and consider all

+    epsilon-transitions s -eps-> s' from s.  If s' is in S already,

+    then do nothing; otherwise add s' to S and the worklist.  When the

+    worklist is empty, S is epsilon-closed; return S.

+

+  Method MkRenamer works as follows: 

+

+    Given a Map from Set of int to something, create an

+    injective Map from Set of int to int, by choosing a fresh

+    int for every value of the map.

+

+  Method Rename works as follows:

+

+    Given a Map from Set of int to Map from String to Set of

+    int, use the result of MkRenamer to replace all Sets of ints

+    by ints.

+

+*/

+

+

+class Nfa {

+  private readonly int startState;

+  private readonly int exitState;    // This is the unique accept state

+  private readonly IDictionary<int,List<Transition>> trans;

+

+  public Nfa(int startState, int exitState) {

+    this.startState = startState; this.exitState = exitState;

+    trans = new Dictionary<int,List<Transition>>();

+    if (!startState.Equals(exitState))

+      trans.Add(exitState, new List<Transition>());

+  }

+

+  public int Start { get { return startState; } }

+

+  public int Exit { get { return exitState; } }

+

+  public IDictionary<int, List<Transition>> Trans { 

+    get { return trans; }

+  }

+

+  public void AddTrans(int s1, String lab, int s2) {

+    List<Transition> s1Trans;

+    if (trans.ContainsKey(s1)) 

+      s1Trans = trans[s1];

+    else {

+      s1Trans = new List<Transition>();

+      trans.Add(s1, s1Trans);

+    }

+    s1Trans.Add(new Transition(lab, s2));

+  }

+

+  public void AddTrans(KeyValuePair<int, List<Transition>> tr) {

+    // Assumption: if tr is in trans, it maps to an empty list (end state)

+    trans.Remove(tr.Key);

+    trans.Add(tr.Key, tr.Value);

+  }

+

+  public override String ToString() {

+    return "NFA start=" + startState + " exit=" + exitState;

+  }

+

+  // Construct the transition relation of a composite-state DFA

+  // from an NFA with start state s0 and transition relation

+  // trans (a Map from int to List of Transition).  The start

+  // state of the constructed DFA is the epsilon closure of s0,

+  // and its transition relation is a Map from a composite state

+  // (a Set of ints) to a Map from label (a String) to a

+  // composite state (a Set of ints).

+

+  static IDictionary<Set<int>, IDictionary<String, Set<int>>>

+    CompositeDfaTrans(int s0, IDictionary<int, List<Transition>> trans) {

+    Set<int> S0 = EpsilonClose(new Set<int>(s0), trans);

+    Queue<Set<int>> worklist = new Queue<Set<int>>();

+    worklist.Enqueue(S0);

+    // The transition relation of the DFA

+    IDictionary<Set<int>, IDictionary<String, Set<int>>> res = 

+      new Dictionary<Set<int>, IDictionary<String, Set<int>>>(); 

+    while (worklist.Count != 0) {

+      Set<int> S = worklist.Dequeue();

+      if (!res.ContainsKey(S)) {

+        // The S -lab-> T transition relation being constructed for a given S

+        IDictionary<String, Set<int>> STrans = 

+	  new Dictionary<String, Set<int>>(); 

+        // For all s in S, consider all transitions s -lab-> t

+	foreach (int s in S) {

+          // For all non-epsilon transitions s -lab-> t, add t to T

+	  foreach (Transition tr in trans[s]) {

+            if (tr.lab != null) {       // Already a transition on lab

+              Set<int> toState; 

+              if (STrans.ContainsKey(tr.lab)) 

+                toState = STrans[tr.lab];

+              else {                    // No transitions on lab yet

+                toState = new Set<int>();

+                STrans.Add(tr.lab, toState);

+              }

+              toState.Add(tr.target);

+            }

+          }

+        }

+        // Epsilon-close all T such that S -lab-> T, and put on worklist

+        Dictionary<String, Set<int>> STransClosed = 

+          new Dictionary<String, Set<int> >();

+	foreach (KeyValuePair<String, Set<int>> entry in STrans) {

+          Set<int> Tclose = EpsilonClose(entry.Value, trans);

+          STransClosed.Add(entry.Key, Tclose);

+          worklist.Enqueue(Tclose);

+        }

+        res.Add(S, STransClosed);

+      }

+    }

+    return res;

+  }  

+

+  // Compute epsilon-closure of state set S in transition relation trans.  

+

+  static Set<int> 

+    EpsilonClose(Set<int> S, IDictionary<int, List<Transition>> trans) {

+    // The worklist initially contains all S members

+    Queue<int> worklist = new Queue<int>(S);

+    Set<int> res = new Set<int>(S);

+    while (worklist.Count != 0) {

+      int s = worklist.Dequeue();

+      foreach (Transition tr in trans[s]) {

+        if (tr.lab == null && !res.Contains(tr.target)) {

+          res.Add(tr.target);

+          worklist.Enqueue(tr.target);

+        }

+      }

+    }

+    return res;

+  }

+

+  // Compute a renamer, which is a Map from Set of int to int

+

+  static IDictionary<Set<int>, int> MkRenamer(ICollection<Set<int>> states) {

+    IDictionary<Set<int>, int> renamer = new Dictionary<Set<int>, int>();

+    int count = 0;

+    foreach (Set<int> k in states) 

+      renamer.Add(k, count++);

+    return renamer;

+  }

+

+  // Using a renamer (a Map from Set of int to int), replace

+  // composite (Set of int) states with simple (int) states in

+  // the transition relation trans, which is assumed to be a Map

+  // from Set of int to Map from String to Set of int.  The

+  // result is a Map from int to Map from String to int.

+

+  static IDictionary<int, IDictionary<String, int>>

+    Rename(IDictionary<Set<int>, int> renamer, 

+           IDictionary<Set<int>, IDictionary<String, Set<int>>> trans) {

+    IDictionary<int, IDictionary<String, int>> newtrans = 

+      new Dictionary<int, IDictionary<String, int>>();

+    foreach (KeyValuePair<Set<int>, IDictionary<String, Set<int>>> entry 

+	     in trans) {

+      Set<int> k = entry.Key;

+      IDictionary<String, int> newktrans = new Dictionary<String, int>();

+      foreach (KeyValuePair<String, Set<int>> tr in entry.Value) 

+        newktrans.Add(tr.Key, renamer[tr.Value]);

+      newtrans.Add(renamer[k], newktrans);

+    }

+    return newtrans;

+  }

+

+  static Set<int> AcceptStates(ICollection<Set<int>> states, 

+			       IDictionary<Set<int>, int> renamer,

+			       int exit) {

+    Set<int> acceptStates = new Set<int>();

+    foreach (Set<int> state in states) 

+      if (state.Contains(exit)) 

+        acceptStates.Add(renamer[state]);

+    return acceptStates;

+  }

+

+  public Dfa ToDfa() {

+    IDictionary<Set<int>, IDictionary<String, Set<int>>> 

+      cDfaTrans = CompositeDfaTrans(startState, trans);

+    Set<int> cDfaStart = EpsilonClose(new Set<int>(startState), trans);

+    ICollection<Set<int>> cDfaStates = cDfaTrans.Keys;

+    IDictionary<Set<int>, int> renamer = MkRenamer(cDfaStates);

+    IDictionary<int, IDictionary<String, int>> simpleDfaTrans = 

+      Rename(renamer, cDfaTrans);

+    int simpleDfaStart = renamer[cDfaStart];

+    Set<int> simpleDfaAccept = AcceptStates(cDfaStates, renamer, exitState);

+    return new Dfa(simpleDfaStart, simpleDfaAccept, simpleDfaTrans);

+  }

+

+  // Nested class for creating distinctly named states when constructing NFAs

+

+  public class NameSource {

+    private static int nextName = 0;

+

+    public int next() { 

+      return nextName++; 

+    }

+  }

+}

+

+// Class Transition, a transition from one state to another ----------

+

+  public class Transition {

+    public String lab;

+    public int target;

+    

+    public Transition(String lab, int target) { 

+      this.lab = lab; this.target = target; 

+    }

+    

+    public override String ToString() {

+      return "-" + lab + "-> " + target;

+    }

+  }

+

+// Class Dfa, deterministic finite automata --------------------------

+

+/*

+  A deterministic finite automaton (DFA) is represented as a Map

+  from state number (int) to a Map from label (a String,

+  non-null) to a target state (an int).  

+*/

+

+class Dfa {

+  private readonly int startState;

+  private readonly Set<int> acceptStates;

+  private readonly IDictionary<int, IDictionary<String,int>> trans;

+

+  public Dfa(int startState, Set<int> acceptStates, 

+	     IDictionary<int, IDictionary<String,int>> trans) {

+    this.startState = startState; 

+    this.acceptStates = acceptStates;

+    this.trans = trans;

+  }

+  

+  public int Start { get { return startState; } }

+

+  public Set<int> Accept { get { return acceptStates; } }

+

+  public IDictionary<int, IDictionary<String,int>> Trans { 

+    get { return trans; }

+  }

+

+  public override String ToString() {

+    return "DFA start=" + startState + "\naccept=" + acceptStates;

+  }

+

+  // Write an input file for the dot program.  You can find dot at

+  // http://www.research.att.com/sw/tools/graphviz/

+

+  public void WriteDot(String filename) {

+    TextWriter wr = 

+      new StreamWriter(new FileStream(filename, FileMode.Create, 

+                                      FileAccess.Write));

+    wr.WriteLine("// Format this file as a Postscript file with ");

+    wr.WriteLine("//    dot " + filename + " -Tps -o out.ps\n");

+    wr.WriteLine("digraph dfa {");

+    wr.WriteLine("size=\"11,8.25\";");

+    wr.WriteLine("rotate=90;");

+    wr.WriteLine("rankdir=LR;");

+    wr.WriteLine("n999999 [style=invis];");    // Invisible start node

+    wr.WriteLine("n999999 -> n" + startState); // Edge into start state

+    

+    // Accept states are double circles

+    foreach (int state in trans.Keys) 

+      if (acceptStates.Contains(state))

+        wr.WriteLine("n" + state + " [peripheries=2];");

+

+    // The transitions 

+    foreach (KeyValuePair<int, IDictionary<String, int>> entry in trans) {

+      int s1 = entry.Key;

+      foreach (KeyValuePair<String, int> s1Trans in entry.Value) {

+        String lab = s1Trans.Key;

+        int s2 = s1Trans.Value;

+        wr.WriteLine("n" + s1 + " -> n" + s2 + " [label=\"" + lab + "\"];");

+      }

+    }

+    wr.WriteLine("}");

+    wr.Close();

+  }

+}

+

+// Regular expressions ----------------------------------------------

+//

+// Abstract syntax of regular expressions

+//    r ::= A | r1 r2 | (r1|r2) | r*

+//

+

+abstract class Regex { 

+  abstract public Nfa MkNfa(Nfa.NameSource names);

+}

+

+class Eps : Regex {

+  // The resulting nfa0 has form s0s -eps-> s0e

+

+  public override Nfa MkNfa(Nfa.NameSource names) {

+    int s0s = names.next();

+    int s0e = names.next();

+    Nfa nfa0 = new Nfa(s0s, s0e);

+    nfa0.AddTrans(s0s, null, s0e);

+    return nfa0;

+  }

+}

+

+class Sym : Regex {

+  String sym;

+

+  public Sym(String sym) { 

+    this.sym = sym; 

+  }

+

+  // The resulting nfa0 has form s0s -sym-> s0e

+

+  public override Nfa MkNfa(Nfa.NameSource names) {

+    int s0s = names.next();

+    int s0e = names.next();

+    Nfa nfa0 = new Nfa(s0s, s0e);

+    nfa0.AddTrans(s0s, sym, s0e);

+    return nfa0;

+  }

+}

+

+class Seq : Regex {

+  Regex r1, r2;

+

+  public Seq(Regex r1, Regex r2) {

+    this.r1 = r1; this.r2 = r2;

+  }

+

+  // If   nfa1 has form s1s ----> s1e 

+  // and  nfa2 has form s2s ----> s2e 

+  // then nfa0 has form s1s ----> s1e -eps-> s2s ----> s2e

+

+  public override Nfa MkNfa(Nfa.NameSource names) {

+    Nfa nfa1 = r1.MkNfa(names);

+    Nfa nfa2 = r2.MkNfa(names);

+    Nfa nfa0 = new Nfa(nfa1.Start, nfa2.Exit);

+    foreach (KeyValuePair<int, List<Transition>> entry in nfa1.Trans) 

+      nfa0.AddTrans(entry);

+    foreach (KeyValuePair<int, List<Transition>> entry in nfa2.Trans) 

+      nfa0.AddTrans(entry);

+    nfa0.AddTrans(nfa1.Exit, null, nfa2.Start);

+    return nfa0;

+  }

+}

+

+class Alt : Regex {

+  Regex r1, r2;

+

+  public Alt(Regex r1, Regex r2) {

+    this.r1 = r1; this.r2 = r2;

+  }

+

+  // If   nfa1 has form s1s ----> s1e 

+  // and  nfa2 has form s2s ----> s2e 

+  // then nfa0 has form s0s -eps-> s1s ----> s1e -eps-> s0e

+  //                    s0s -eps-> s2s ----> s2e -eps-> s0e

+

+  public override Nfa MkNfa(Nfa.NameSource names) {

+    Nfa nfa1 = r1.MkNfa(names);

+    Nfa nfa2 = r2.MkNfa(names);

+    int s0s = names.next();

+    int s0e = names.next();

+    Nfa nfa0 = new Nfa(s0s, s0e);

+    foreach (KeyValuePair<int, List<Transition>> entry in nfa1.Trans) 

+      nfa0.AddTrans(entry);

+    foreach (KeyValuePair<int, List<Transition>> entry in nfa2.Trans) 

+      nfa0.AddTrans(entry);

+    nfa0.AddTrans(s0s, null, nfa1.Start);

+    nfa0.AddTrans(s0s, null, nfa2.Start);

+    nfa0.AddTrans(nfa1.Exit, null, s0e);

+    nfa0.AddTrans(nfa2.Exit, null, s0e);

+    return nfa0;

+  }

+}

+

+class Star : Regex {

+  Regex r;

+

+  public Star(Regex r) {

+    this.r = r; 

+  }

+

+  // If   nfa1 has form s1s ----> s1e 

+  // then nfa0 has form s0s ----> s0s

+  //                    s0s -eps-> s1s

+  //                    s1e -eps-> s0s

+

+  public override Nfa MkNfa(Nfa.NameSource names) {

+    Nfa nfa1 = r.MkNfa(names);

+    int s0s = names.next();

+    Nfa nfa0 = new Nfa(s0s, s0s);

+    foreach (KeyValuePair<int, List<Transition>> entry in nfa1.Trans) 

+      nfa0.AddTrans(entry);

+    nfa0.AddTrans(s0s, null, nfa1.Start);

+    nfa0.AddTrans(nfa1.Exit, null, s0s);

+    return nfa0;

+  }

+}

+

+// Trying the RE->NFA->DFA translation on three regular expressions

+

+class TestNFA {

+  public static void Main(String[] args) {

+    Regex a = new Sym("A");

+    Regex b = new Sym("B");

+    Regex c = new Sym("C");

+    Regex abStar = new Star(new Alt(a, b));

+    Regex bb = new Seq(b, b);

+    Regex r = new Seq(abStar, new Seq(a, b));

+    // The regular expression (a|b)*ab

+    BuildAndShow("dfa1.dot", r);

+    // The regular expression ((a|b)*ab)*

+    BuildAndShow("dfa2.dot", new Star(r));

+    // The regular expression ((a|b)*ab)((a|b)*ab)

+    BuildAndShow("dfa3.dot", new Seq(r, r));

+    // The regular expression (a|b)*abb, from ASU 1986 p 136

+    BuildAndShow("dfa4.dot", new Seq(abStar, new Seq(a, bb)));

+    // SML reals: sign?((digit+(\.digit+)?))([eE]sign?digit+)?

+    Regex d = new Sym("digit");

+    Regex dPlus = new Seq(d, new Star(d));

+    Regex s = new Sym("sign");

+    Regex sOpt = new Alt(s, new Eps());

+    Regex dot = new Sym(".");

+    Regex dotDigOpt = new Alt(new Eps(), new Seq(dot, dPlus));

+    Regex mant = new Seq(sOpt, new Seq(dPlus, dotDigOpt));

+    Regex e = new Sym("e");

+    Regex exp = new Alt(new Eps(), new Seq(e, new Seq(sOpt, dPlus)));

+    Regex smlReal = new Seq(mant, exp);

+    BuildAndShow("dfa5.dot", smlReal);

+  }

+

+  public static void BuildAndShow(String filename, Regex r) {

+    Nfa nfa = r.MkNfa(new Nfa.NameSource());

+    Console.WriteLine(nfa);

+    Console.WriteLine("---");

+    Dfa dfa = nfa.ToDfa();

+    Console.WriteLine(dfa);

+    Console.WriteLine("Writing DFA graph to file " + filename);

+    dfa.WriteDot(filename);

+    Console.WriteLine();

+  }

+}

diff --git a/resources/literature/J00-1005.pdf b/resources/literature/J00-1005.pdf
new file mode 100644
index 0000000..90f4704
--- /dev/null
+++ b/resources/literature/J00-1005.pdf