Sankuru

A program space is a language

P is a program, a theorem, a text, satisfying the grammar G.

P is tree of sentences S
S is a collection of words W

The collection of all valid programs/theorems/texts accepted by the grammer G is the program space PP; which can also be called: language L(G).

A translate rule (a compiler) is a program cT that projects the program space PP1 unto the program space PP2 under an equivalence rule F which says that F(P) == F(cT(P)).

A rewrite rule is a program cR that projects the program space PP unto itself under the equivalence rule F which says that F(P)=F(cR(P)).

Note: A theorem is a program that satisfies a grammar G, and in which each sentence can be reduced recursively to a given set of non-reducable programs, called axioms. It is insufficient that the theorem be grammatically correct. It must also satisfy the construction rule applicable to theorems.

A machine executable theorem satisfies the construction rule that each sentence can be reduced to the instruction set of a Turing machine (the machine axioms).

The Kleene program space

The rewrite rule cRE projects the Kleene program space unto itself under the equivalence rule which says that the state transitions contained in the resulting atomic word rules must be the same as the state transitions contained in the fully-fledged word rule.

The world rule a(z(bc)*x[0-3])+d?e is fully fledged, because it contains embedded sentences as well as Kleene operators. The translate rule cRE will project it unto 12 atomic word rules.

cRE{a(z(bc)*x0)+d?e}=

{azx0e
,azbcx0e
,azbcbcx0e
,azx0de
,azbcx0de
,azbcbcx0de
,azx0zx0e
,azbcx0zbcx0e
,azbcbcx0zbcbcx0e
,azx0zx0de
,azbcx0zbcx0de
,azbcbcx0zbcbcx0de}

The resulting word rules are atomic because they do not contain embedded sentences nor Kleene operators.

The translate rule (compiler) cRE operates by applying the reduction rules for Kleene operators:

T{a(xy)*b} = T{ab} + T{axyb} + T{axyxyb}
T{a(xy)+b} = T{axyb} + T{axyxyb}
T{a(xy)?b} = T{ab} + T{axyb}
T{a(x|y)b} = T{axb} + T{ayb}

The reduction rules for Kleene operators maintain the equivalence requirement, which states that state transitions contained in the righthand side expressions must be the same as the ones in the lefthand side expression. Therefore, the compiler cRE recursively reduces the fully-fledged word rules, until they have all been replaced by atomic word rules.

Notes

Currently, most regular expression parsers will use Thompson's algorithm to produce the collection of state transitions for the embedded Kleene's closures, as described in Thompson's 1968 paper "regular expression search algorithm".

My attempt to introduce the cRE reduction rules to do the same, is indeed a relatively ambitious attack on the 1968 seminal paper. I do not guarantee that it will succeed. It all depends on the validity of the reduction rules.

Up till this point in time, I have not discovered any example for which they do not work. However, taking into account Gödel's theorems, we certainly know that they exist. But then again, since they also exist for Thompson, the point must indeed be considered moot.

I do not really think that my reduction rules will be necessarily faster to operate than Thompson's algorithmical approach. My only hope for defeating Thompson, consists in demonstrating that the cRE reduction rules are more Gödel-resistant than Thompson's algorithm.