bla

4 files changed, 0 insertions, 629 deletions

diff --git a/resources/literature/GNfaToDfa.cs b/resources/literature/GNfaToDfa.cs
deleted file mode 100644
index df88b1d..0000000
--- a/resources/literature/GNfaToDfa.cs
+++ /dev/null
@@ -1,629 +0,0 @@
-// 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/RENFADFA.doc b/resources/literature/RENFADFA.doc
deleted file mode 100644
index fb76173..0000000
--- a/resources/literature/RENFADFA.doc
+++ /dev/null
diff --git a/resources/literature/10.1.1.21.1679.pdf b/resources/literature/compactdfa.pdf
index 2b7d75a..2b7d75a 100644
--- a/resources/literature/10.1.1.21.1679.pdf
+++ b/resources/literature/compactdfa.pdf
diff --git a/resources/literature/J00-1005.pdf b/resources/literature/epsilonmoves.pdf
index 90f4704..90f4704 100644
--- a/resources/literature/J00-1005.pdf
+++ b/resources/literature/epsilonmoves.pdf