diff options
Diffstat (limited to 'repcore/src/plan.org')
| -rw-r--r-- | repcore/src/plan.org | 59 |
1 files changed, 0 insertions, 59 deletions
diff --git a/repcore/src/plan.org b/repcore/src/plan.org deleted file mode 100644 index 13c2ee0..0000000 --- a/repcore/src/plan.org +++ /dev/null @@ -1,59 +0,0 @@ -#+TITLE: Plan of the package -#+AUTHOR: Durand -#+DATE: <2022-11-18 Ven 19:57> - -* 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. - -* 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. - |