1 files changed, 94 insertions, 0 deletions
diff --git a/chain/src/plan.org b/chain/src/plan.org
new file mode 100644
index 0000000..8c63492
--- /dev/null
+++ b/chain/src/plan.org
@@ -0,0 +1,94 @@
+#+TITLE: Plan of the package
+#+AUTHOR: Durand
+#+DATE: <2022-11-18 Ven 19:57>
+
+* Things to do [2/7]
+
+- [X] Implement builders for graphs
+- [X] Find sets of the first terminals for each non-terminal, in the
+  grammar module.
+- [-] NFA [4/5]
+  + [X] Add regular expression into NFA.
+  + [X] Convert a set of regular expressions into a nondeterministic
+    finite automaton, where non-terminals denote the indices of
+    regular expressions in the set to substitute.
+  + [X] Convert a grammar into its grammar of left-linear closures of
+    non-temrinals and their derivatives.
+  + [X] Convert nondeterministic finite automata to their null
+    closures.
+  + [ ] Test more grammars to ensure it works correctly.
+- [ ] Define the Atom trait.
+- [ ] Implement virtual nodes for each derivative of each atom: The
+  lack of this step might be the root cause of the failure of the
+  previous version of this package.
+- [ ] Implement languages. [0/2]
+  + [ ] First implement them as doubly labelled (directed acyclic)
+    graphs.
+  + [ ] Implement finding derivatives.
+- [ ] Implement semiring. [0/5]
+  + [ ] Define the trait.
+  + [ ] Implement the boolean semiring.
+  + [ ] Implement the natural number semiring.
+  + [ ] Implement the free semiring.
+  + [ ] Compute and record a semiring value when computing
+    derivatives.
+
+* Atomic Languages
+
+This describes the behaviours of atomic languages.  The atomic
+language consists of the null closure of any non-terminal symbol in
+the grammar, and their deriavtives by terminals and non-terminal.
+
+* Script for creating GIF animation
+
+[[https://gist.github.com/maelvls/5379127][a gist]]
+
+* Derivative Languages
+
+This is the main driving device of the algorithm.  Basically, the
+algorithm works by taking successive derivatives, according to the
+input symbol.  At each step, we calculate the derivative language.  In
+this process, we also compute some semiring value and store in a
+carrier.  The end result of the algorithm is the final semiring
+value.
+
+If one wants simply to determine if the input string belongs to the
+grammar, one chooses the semiring to be the field with two elements,
+the boolean field.  If one wants to find how many ways are there to
+derive a given input string, then one uses the semiring of natural
+numbers instead.  If one wants, moreover, to find all the possible
+ways to derive a particular input string, then one can use the
+free semiring on the set of terminals and non-terminals of the
+grammar.  Here the free semiring is the left-adjoint functor to the
+forgetful functor from the category of semirings to the category of
+sets.
+
+To be more specific, the free semiring on a set is given by sets of
+sequences of elements in the set.  The addition of the semiring is the
+set union operation, and the multiplication is taking the respective
+concatenations.
+
+** Semirings
+
+So we need a module to define the behaviours of semirings, and provide
+some common semirings implementations.  Then in the main driving force
+we can freely substitute different semirings, according to the
+particular needs.
+
+** Languages
+
+Then the main part is to define the behaviour of languages.  This
+should be easy enough, since we already have the mechanism of graphs,
+nondeterministic automata, and semirings.  All we need to do is to
+combine them together.
+
+* Testing ground
+
+I am in a strong need to test things out.  The most important one is
+to visualize each step of the derivation, in a human-friendly manner.
+I need this to examine whether my atomic languages are wrongly
+implemented, or my atomic languages are wrongly derived, or my
+understanding of the main algorithm is plain wrong.
+
+This is the main reason I started this rewrite of the package.
+