6 <meta charset="utf-8" />
7 <meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />
9 <title>∂RE — Thun 0.4.1 documentation</title>
10 <link rel="stylesheet" type="text/css" href="../_static/pygments.css" />
11 <link rel="stylesheet" type="text/css" href="../_static/alabaster.css" />
12 <script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script>
13 <script src="../_static/jquery.js"></script>
14 <script src="../_static/underscore.js"></script>
15 <script src="../_static/doctools.js"></script>
16 <link rel="index" title="Index" href="../genindex.html" />
17 <link rel="search" title="Search" href="../search.html" />
18 <link rel="prev" title="The Four Fundamental Operations of Definite Action" href="The_Four_Operations.html" />
20 <link rel="stylesheet" href="../_static/custom.css" type="text/css" />
23 <meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
28 <div class="document">
29 <div class="documentwrapper">
30 <div class="bodywrapper">
33 <div class="body" role="main">
36 <h1>∂RE<a class="headerlink" href="#re" title="Permalink to this headline">¶</a></h1>
37 <section id="brzozowskis-derivatives-of-regular-expressions">
38 <h2>Brzozowski’s Derivatives of Regular Expressions<a class="headerlink" href="#brzozowskis-derivatives-of-regular-expressions" title="Permalink to this headline">¶</a></h2>
40 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>∧ intersection
42 ∘ concatenation (see below)
45 λ singleton set containing just the empty string
46 I set of all letters in alphabet
49 <p>Derivative of a set <code class="docutils literal notranslate"><span class="pre">R</span></code> of strings and a string <code class="docutils literal notranslate"><span class="pre">a</span></code>:</p>
50 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>∂a(R)
58 ∂a(R∘S) → ∂a(R)∘S ∨ δ(R)∘∂a(S)
59 ∂a(R ∧ S) → ∂a(R) ∧ ∂a(S)
60 ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)
65 <p>Auxiliary predicate function <code class="docutils literal notranslate"><span class="pre">δ</span></code> (I call it <code class="docutils literal notranslate"><span class="pre">nully</span></code>) returns either
66 <code class="docutils literal notranslate"><span class="pre">λ</span></code> if <code class="docutils literal notranslate"><span class="pre">λ</span> <span class="pre">⊆</span> <span class="pre">R</span></code> or <code class="docutils literal notranslate"><span class="pre">ϕ</span></code> otherwise:</p>
67 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>δ(a) → ϕ
74 δ(R ∧ S) → δ(R) ∧ δ(S)
75 δ(R ∨ S) → δ(R) ∨ δ(S)
78 <p>Some rules we will use later for “compaction”:</p>
79 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>R ∧ ϕ = ϕ ∧ R = ϕ
92 <p>Concatination of sets: for two sets A and B the set A∘B is defined as:</p>
93 <p>{a∘b for a in A for b in B}</p>
95 <p>{‘a’, ‘b’}∘{‘c’, ‘d’} → {‘ac’, ‘ad’, ‘bc’, ‘bd’}</p>
97 <section id="implementation">
98 <h2>Implementation<a class="headerlink" href="#implementation" title="Permalink to this headline">¶</a></h2>
99 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">functools</span> <span class="kn">import</span> <span class="n">partial</span> <span class="k">as</span> <span class="n">curry</span>
100 <span class="kn">from</span> <span class="nn">itertools</span> <span class="kn">import</span> <span class="n">product</span>
104 <h3><code class="docutils literal notranslate"><span class="pre">ϕ</span></code> and <code class="docutils literal notranslate"><span class="pre">λ</span></code><a class="headerlink" href="#and" title="Permalink to this headline">¶</a></h3>
105 <p>The empty set and the set of just the empty string.</p>
106 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">phi</span> <span class="o">=</span> <span class="nb">frozenset</span><span class="p">()</span> <span class="c1"># ϕ</span>
107 <span class="n">y</span> <span class="o">=</span> <span class="nb">frozenset</span><span class="p">({</span><span class="s1">''</span><span class="p">})</span> <span class="c1"># λ</span>
111 <section id="two-letter-alphabet">
112 <h3>Two-letter Alphabet<a class="headerlink" href="#two-letter-alphabet" title="Permalink to this headline">¶</a></h3>
113 <p>I’m only going to use two symbols (at first) becaase this is enough to
114 illustrate the algorithm and because you can represent any other
115 alphabet with two symbols (if you had to.)</p>
116 <p>I chose the names <code class="docutils literal notranslate"><span class="pre">O</span></code> and <code class="docutils literal notranslate"><span class="pre">l</span></code> (uppercase “o” and lowercase “L”) to
117 look like <code class="docutils literal notranslate"><span class="pre">0</span></code> and <code class="docutils literal notranslate"><span class="pre">1</span></code> (zero and one) respectively.</p>
118 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">syms</span> <span class="o">=</span> <span class="n">O</span><span class="p">,</span> <span class="n">l</span> <span class="o">=</span> <span class="nb">frozenset</span><span class="p">({</span><span class="s1">'0'</span><span class="p">}),</span> <span class="nb">frozenset</span><span class="p">({</span><span class="s1">'1'</span><span class="p">})</span>
122 <section id="representing-regular-expressions">
123 <h3>Representing Regular Expressions<a class="headerlink" href="#representing-regular-expressions" title="Permalink to this headline">¶</a></h3>
124 <p>To represent REs in Python I’m going to use tagged tuples. A <em>regular
125 expression</em> is one of:</p>
126 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">O</span>
127 <span class="n">l</span>
128 <span class="p">(</span><span class="n">KSTAR</span><span class="p">,</span> <span class="n">R</span><span class="p">)</span>
129 <span class="p">(</span><span class="n">NOT</span><span class="p">,</span> <span class="n">R</span><span class="p">)</span>
130 <span class="p">(</span><span class="n">AND</span><span class="p">,</span> <span class="n">R</span><span class="p">,</span> <span class="n">S</span><span class="p">)</span>
131 <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">R</span><span class="p">,</span> <span class="n">S</span><span class="p">)</span>
132 <span class="p">(</span><span class="n">OR</span><span class="p">,</span> <span class="n">R</span><span class="p">,</span> <span class="n">S</span><span class="p">)</span>
135 <p>Where <code class="docutils literal notranslate"><span class="pre">R</span></code> and <code class="docutils literal notranslate"><span class="pre">S</span></code> stand for <em>regular expressions</em>.</p>
136 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">AND</span><span class="p">,</span> <span class="n">CONS</span><span class="p">,</span> <span class="n">KSTAR</span><span class="p">,</span> <span class="n">NOT</span><span class="p">,</span> <span class="n">OR</span> <span class="o">=</span> <span class="s1">'and cons * not or'</span><span class="o">.</span><span class="n">split</span><span class="p">()</span> <span class="c1"># Tags are just strings.</span>
139 <p>Because they are formed of <code class="docutils literal notranslate"><span class="pre">frozenset</span></code>, <code class="docutils literal notranslate"><span class="pre">tuple</span></code> and <code class="docutils literal notranslate"><span class="pre">str</span></code> objects
140 only, these datastructures are immutable.</p>
142 <section id="string-representation-of-re-datastructures">
143 <h3>String Representation of RE Datastructures<a class="headerlink" href="#string-representation-of-re-datastructures" title="Permalink to this headline">¶</a></h3>
144 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">stringy</span><span class="p">(</span><span class="n">re</span><span class="p">):</span>
145 <span class="sd">'''</span>
146 <span class="sd"> Return a nice string repr for a regular expression datastructure.</span>
147 <span class="sd"> '''</span>
148 <span class="k">if</span> <span class="n">re</span> <span class="o">==</span> <span class="n">I</span><span class="p">:</span> <span class="k">return</span> <span class="s1">'.'</span>
149 <span class="k">if</span> <span class="n">re</span> <span class="ow">in</span> <span class="n">syms</span><span class="p">:</span> <span class="k">return</span> <span class="nb">next</span><span class="p">(</span><span class="nb">iter</span><span class="p">(</span><span class="n">re</span><span class="p">))</span>
150 <span class="k">if</span> <span class="n">re</span> <span class="o">==</span> <span class="n">y</span><span class="p">:</span> <span class="k">return</span> <span class="s1">'^'</span>
151 <span class="k">if</span> <span class="n">re</span> <span class="o">==</span> <span class="n">phi</span><span class="p">:</span> <span class="k">return</span> <span class="s1">'X'</span>
153 <span class="k">assert</span> <span class="nb">isinstance</span><span class="p">(</span><span class="n">re</span><span class="p">,</span> <span class="nb">tuple</span><span class="p">),</span> <span class="nb">repr</span><span class="p">(</span><span class="n">re</span><span class="p">)</span>
154 <span class="n">tag</span> <span class="o">=</span> <span class="n">re</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
156 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">KSTAR</span><span class="p">:</span>
157 <span class="n">body</span> <span class="o">=</span> <span class="n">stringy</span><span class="p">(</span><span class="n">re</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
158 <span class="k">if</span> <span class="ow">not</span> <span class="n">body</span><span class="p">:</span> <span class="k">return</span> <span class="n">body</span>
159 <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">body</span><span class="p">)</span> <span class="o">></span> <span class="mi">1</span><span class="p">:</span> <span class="k">return</span> <span class="s1">'('</span> <span class="o">+</span> <span class="n">body</span> <span class="o">+</span> <span class="s2">")*"</span>
160 <span class="k">return</span> <span class="n">body</span> <span class="o">+</span> <span class="s1">'*'</span>
162 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">NOT</span><span class="p">:</span>
163 <span class="n">body</span> <span class="o">=</span> <span class="n">stringy</span><span class="p">(</span><span class="n">re</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span>
164 <span class="k">if</span> <span class="ow">not</span> <span class="n">body</span><span class="p">:</span> <span class="k">return</span> <span class="n">body</span>
165 <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">body</span><span class="p">)</span> <span class="o">></span> <span class="mi">1</span><span class="p">:</span> <span class="k">return</span> <span class="s1">'('</span> <span class="o">+</span> <span class="n">body</span> <span class="o">+</span> <span class="s2">")'"</span>
166 <span class="k">return</span> <span class="n">body</span> <span class="o">+</span> <span class="s2">"'"</span>
168 <span class="n">r</span><span class="p">,</span> <span class="n">s</span> <span class="o">=</span> <span class="n">stringy</span><span class="p">(</span><span class="n">re</span><span class="p">[</span><span class="mi">1</span><span class="p">]),</span> <span class="n">stringy</span><span class="p">(</span><span class="n">re</span><span class="p">[</span><span class="mi">2</span><span class="p">])</span>
169 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">CONS</span><span class="p">:</span> <span class="k">return</span> <span class="n">r</span> <span class="o">+</span> <span class="n">s</span>
170 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">OR</span><span class="p">:</span> <span class="k">return</span> <span class="s1">'</span><span class="si">%s</span><span class="s1"> | </span><span class="si">%s</span><span class="s1">'</span> <span class="o">%</span> <span class="p">(</span><span class="n">r</span><span class="p">,</span> <span class="n">s</span><span class="p">)</span>
171 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">AND</span><span class="p">:</span> <span class="k">return</span> <span class="s1">'(</span><span class="si">%s</span><span class="s1">) & (</span><span class="si">%s</span><span class="s1">)'</span> <span class="o">%</span> <span class="p">(</span><span class="n">r</span><span class="p">,</span> <span class="n">s</span><span class="p">)</span>
173 <span class="k">raise</span> <span class="ne">ValueError</span>
178 <h3><code class="docutils literal notranslate"><span class="pre">I</span></code><a class="headerlink" href="#i" title="Permalink to this headline">¶</a></h3>
179 <p>Match anything. Often spelled “.”</p>
180 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">I</span> <span class="o">=</span> <span class="p">(</span><span class="mi">0</span><span class="o">|</span><span class="mi">1</span><span class="p">)</span><span class="o">*</span>
183 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">I</span> <span class="o">=</span> <span class="p">(</span><span class="n">KSTAR</span><span class="p">,</span> <span class="p">(</span><span class="n">OR</span><span class="p">,</span> <span class="n">O</span><span class="p">,</span> <span class="n">l</span><span class="p">))</span>
186 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="nb">print</span> <span class="n">stringy</span><span class="p">(</span><span class="n">I</span><span class="p">)</span>
189 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">.</span>
194 <h3><code class="docutils literal notranslate"><span class="pre">(.111.)</span> <span class="pre">&</span> <span class="pre">(.01</span> <span class="pre">+</span> <span class="pre">11*)'</span></code><a class="headerlink" href="#id1" title="Permalink to this headline">¶</a></h3>
195 <p>The example expression from Brzozowski:</p>
196 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&</span> <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">+</span> <span class="mi">11</span><span class="o">*</span><span class="p">)</span><span class="s1">'</span>
197 <span class="n">a</span> <span class="o">&</span> <span class="p">(</span><span class="n">b</span> <span class="o">+</span> <span class="n">c</span><span class="p">)</span><span class="s1">'</span>
200 <p>Note that it contains one of everything.</p>
201 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="o">=</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">I</span><span class="p">,</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="n">I</span><span class="p">))))</span>
202 <span class="n">b</span> <span class="o">=</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">I</span><span class="p">,</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">O</span><span class="p">,</span> <span class="n">l</span><span class="p">))</span>
203 <span class="n">c</span> <span class="o">=</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">l</span><span class="p">,</span> <span class="p">(</span><span class="n">KSTAR</span><span class="p">,</span> <span class="n">l</span><span class="p">))</span>
204 <span class="n">it</span> <span class="o">=</span> <span class="p">(</span><span class="n">AND</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="p">(</span><span class="n">NOT</span><span class="p">,</span> <span class="p">(</span><span class="n">OR</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="n">c</span><span class="p">)))</span>
207 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="nb">print</span> <span class="n">stringy</span><span class="p">(</span><span class="n">it</span><span class="p">)</span>
210 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">11</span><span class="o">*</span><span class="p">)</span><span class="s1">')</span>
215 <h3><code class="docutils literal notranslate"><span class="pre">nully()</span></code><a class="headerlink" href="#nully" title="Permalink to this headline">¶</a></h3>
216 <p>Let’s get that auxiliary predicate function <code class="docutils literal notranslate"><span class="pre">δ</span></code> out of the way.</p>
217 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">nully</span><span class="p">(</span><span class="n">R</span><span class="p">):</span>
218 <span class="sd">'''</span>
219 <span class="sd"> δ - Return λ if λ ⊆ R otherwise ϕ.</span>
220 <span class="sd"> '''</span>
222 <span class="c1"># δ(a) → ϕ</span>
223 <span class="c1"># δ(ϕ) → ϕ</span>
224 <span class="k">if</span> <span class="n">R</span> <span class="ow">in</span> <span class="n">syms</span> <span class="ow">or</span> <span class="n">R</span> <span class="o">==</span> <span class="n">phi</span><span class="p">:</span>
225 <span class="k">return</span> <span class="n">phi</span>
227 <span class="c1"># δ(λ) → λ</span>
228 <span class="k">if</span> <span class="n">R</span> <span class="o">==</span> <span class="n">y</span><span class="p">:</span>
229 <span class="k">return</span> <span class="n">y</span>
231 <span class="n">tag</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
233 <span class="c1"># δ(R*) → λ</span>
234 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">KSTAR</span><span class="p">:</span>
235 <span class="k">return</span> <span class="n">y</span>
237 <span class="c1"># δ(¬R) δ(R)≟ϕ → λ</span>
238 <span class="c1"># δ(¬R) δ(R)≟λ → ϕ</span>
239 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">NOT</span><span class="p">:</span>
240 <span class="k">return</span> <span class="n">phi</span> <span class="k">if</span> <span class="n">nully</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> <span class="k">else</span> <span class="n">y</span>
242 <span class="c1"># δ(R∘S) → δ(R) ∧ δ(S)</span>
243 <span class="c1"># δ(R ∧ S) → δ(R) ∧ δ(S)</span>
244 <span class="c1"># δ(R ∨ S) → δ(R) ∨ δ(S)</span>
245 <span class="n">r</span><span class="p">,</span> <span class="n">s</span> <span class="o">=</span> <span class="n">nully</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">]),</span> <span class="n">nully</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">2</span><span class="p">])</span>
246 <span class="k">return</span> <span class="n">r</span> <span class="o">&</span> <span class="n">s</span> <span class="k">if</span> <span class="n">tag</span> <span class="ow">in</span> <span class="p">{</span><span class="n">AND</span><span class="p">,</span> <span class="n">CONS</span><span class="p">}</span> <span class="k">else</span> <span class="n">r</span> <span class="o">|</span> <span class="n">s</span>
250 <section id="no-compaction">
251 <h3>No “Compaction”<a class="headerlink" href="#no-compaction" title="Permalink to this headline">¶</a></h3>
252 <p>This is the straightforward version with no “compaction”. It works fine,
253 but does waaaay too much work because the expressions grow each
255 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">D</span><span class="p">(</span><span class="n">symbol</span><span class="p">):</span>
257 <span class="k">def</span> <span class="nf">derv</span><span class="p">(</span><span class="n">R</span><span class="p">):</span>
259 <span class="c1"># ∂a(a) → λ</span>
260 <span class="k">if</span> <span class="n">R</span> <span class="o">==</span> <span class="p">{</span><span class="n">symbol</span><span class="p">}:</span>
261 <span class="k">return</span> <span class="n">y</span>
263 <span class="c1"># ∂a(λ) → ϕ</span>
264 <span class="c1"># ∂a(ϕ) → ϕ</span>
265 <span class="c1"># ∂a(¬a) → ϕ</span>
266 <span class="k">if</span> <span class="n">R</span> <span class="o">==</span> <span class="n">y</span> <span class="ow">or</span> <span class="n">R</span> <span class="o">==</span> <span class="n">phi</span> <span class="ow">or</span> <span class="n">R</span> <span class="ow">in</span> <span class="n">syms</span><span class="p">:</span>
267 <span class="k">return</span> <span class="n">phi</span>
269 <span class="n">tag</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
271 <span class="c1"># ∂a(R*) → ∂a(R)∘R*</span>
272 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">KSTAR</span><span class="p">:</span>
273 <span class="k">return</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">]),</span> <span class="n">R</span><span class="p">)</span>
275 <span class="c1"># ∂a(¬R) → ¬∂a(R)</span>
276 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">NOT</span><span class="p">:</span>
277 <span class="k">return</span> <span class="p">(</span><span class="n">NOT</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">]))</span>
279 <span class="n">r</span><span class="p">,</span> <span class="n">s</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">:]</span>
281 <span class="c1"># ∂a(R∘S) → ∂a(R)∘S ∨ δ(R)∘∂a(S)</span>
282 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">CONS</span><span class="p">:</span>
283 <span class="n">A</span> <span class="o">=</span> <span class="p">(</span><span class="n">CONS</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">r</span><span class="p">),</span> <span class="n">s</span><span class="p">)</span> <span class="c1"># A = ∂a(R)∘S</span>
284 <span class="c1"># A ∨ δ(R) ∘ ∂a(S)</span>
285 <span class="c1"># A ∨ λ ∘ ∂a(S) → A ∨ ∂a(S)</span>
286 <span class="c1"># A ∨ ϕ ∘ ∂a(S) → A ∨ ϕ → A</span>
287 <span class="k">return</span> <span class="p">(</span><span class="n">OR</span><span class="p">,</span> <span class="n">A</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">s</span><span class="p">))</span> <span class="k">if</span> <span class="n">nully</span><span class="p">(</span><span class="n">r</span><span class="p">)</span> <span class="k">else</span> <span class="n">A</span>
289 <span class="c1"># ∂a(R ∧ S) → ∂a(R) ∧ ∂a(S)</span>
290 <span class="c1"># ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)</span>
291 <span class="k">return</span> <span class="p">(</span><span class="n">tag</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">r</span><span class="p">),</span> <span class="n">derv</span><span class="p">(</span><span class="n">s</span><span class="p">))</span>
293 <span class="k">return</span> <span class="n">derv</span>
297 <section id="compaction-rules">
298 <h3>Compaction Rules<a class="headerlink" href="#compaction-rules" title="Permalink to this headline">¶</a></h3>
299 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">_compaction_rule</span><span class="p">(</span><span class="n">relation</span><span class="p">,</span> <span class="n">one</span><span class="p">,</span> <span class="n">zero</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">):</span>
300 <span class="k">return</span> <span class="p">(</span>
301 <span class="n">b</span> <span class="k">if</span> <span class="n">a</span> <span class="o">==</span> <span class="n">one</span> <span class="k">else</span> <span class="c1"># R*1 = 1*R = R</span>
302 <span class="n">a</span> <span class="k">if</span> <span class="n">b</span> <span class="o">==</span> <span class="n">one</span> <span class="k">else</span>
303 <span class="n">zero</span> <span class="k">if</span> <span class="n">a</span> <span class="o">==</span> <span class="n">zero</span> <span class="ow">or</span> <span class="n">b</span> <span class="o">==</span> <span class="n">zero</span> <span class="k">else</span> <span class="c1"># R*0 = 0*R = 0</span>
304 <span class="p">(</span><span class="n">relation</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">)</span>
305 <span class="p">)</span>
308 <p>An elegant symmetry.</p>
309 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="c1"># R ∧ I = I ∧ R = R</span>
310 <span class="c1"># R ∧ ϕ = ϕ ∧ R = ϕ</span>
311 <span class="n">_and</span> <span class="o">=</span> <span class="n">curry</span><span class="p">(</span><span class="n">_compaction_rule</span><span class="p">,</span> <span class="n">AND</span><span class="p">,</span> <span class="n">I</span><span class="p">,</span> <span class="n">phi</span><span class="p">)</span>
313 <span class="c1"># R ∨ ϕ = ϕ ∨ R = R</span>
314 <span class="c1"># R ∨ I = I ∨ R = I</span>
315 <span class="n">_or</span> <span class="o">=</span> <span class="n">curry</span><span class="p">(</span><span class="n">_compaction_rule</span><span class="p">,</span> <span class="n">OR</span><span class="p">,</span> <span class="n">phi</span><span class="p">,</span> <span class="n">I</span><span class="p">)</span>
317 <span class="c1"># R∘λ = λ∘R = R</span>
318 <span class="c1"># R∘ϕ = ϕ∘R = ϕ</span>
319 <span class="n">_cons</span> <span class="o">=</span> <span class="n">curry</span><span class="p">(</span><span class="n">_compaction_rule</span><span class="p">,</span> <span class="n">CONS</span><span class="p">,</span> <span class="n">y</span><span class="p">,</span> <span class="n">phi</span><span class="p">)</span>
323 <section id="memoizing">
324 <h3>Memoizing<a class="headerlink" href="#memoizing" title="Permalink to this headline">¶</a></h3>
325 <p>We can save re-processing by remembering results we have already
326 computed. RE datastructures are immutable and the <code class="docutils literal notranslate"><span class="pre">derv()</span></code> functions
327 are <em>pure</em> so this is fine.</p>
328 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">class</span> <span class="nc">Memo</span><span class="p">(</span><span class="nb">object</span><span class="p">):</span>
330 <span class="k">def</span> <span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">f</span><span class="p">):</span>
331 <span class="bp">self</span><span class="o">.</span><span class="n">f</span> <span class="o">=</span> <span class="n">f</span>
332 <span class="bp">self</span><span class="o">.</span><span class="n">calls</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">hits</span> <span class="o">=</span> <span class="mi">0</span>
333 <span class="bp">self</span><span class="o">.</span><span class="n">mem</span> <span class="o">=</span> <span class="p">{}</span>
335 <span class="k">def</span> <span class="fm">__call__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">key</span><span class="p">):</span>
336 <span class="bp">self</span><span class="o">.</span><span class="n">calls</span> <span class="o">+=</span> <span class="mi">1</span>
337 <span class="k">try</span><span class="p">:</span>
338 <span class="n">result</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">mem</span><span class="p">[</span><span class="n">key</span><span class="p">]</span>
339 <span class="bp">self</span><span class="o">.</span><span class="n">hits</span> <span class="o">+=</span> <span class="mi">1</span>
340 <span class="k">except</span> <span class="ne">KeyError</span><span class="p">:</span>
341 <span class="n">result</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">mem</span><span class="p">[</span><span class="n">key</span><span class="p">]</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">f</span><span class="p">(</span><span class="n">key</span><span class="p">)</span>
342 <span class="k">return</span> <span class="n">result</span>
346 <section id="with-compaction">
347 <h3>With “Compaction”<a class="headerlink" href="#with-compaction" title="Permalink to this headline">¶</a></h3>
348 <p>This version uses the rules above to perform compaction. It keeps the
349 expressions from growing too large.</p>
350 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">D_compaction</span><span class="p">(</span><span class="n">symbol</span><span class="p">):</span>
352 <span class="nd">@Memo</span>
353 <span class="k">def</span> <span class="nf">derv</span><span class="p">(</span><span class="n">R</span><span class="p">):</span>
355 <span class="c1"># ∂a(a) → λ</span>
356 <span class="k">if</span> <span class="n">R</span> <span class="o">==</span> <span class="p">{</span><span class="n">symbol</span><span class="p">}:</span>
357 <span class="k">return</span> <span class="n">y</span>
359 <span class="c1"># ∂a(λ) → ϕ</span>
360 <span class="c1"># ∂a(ϕ) → ϕ</span>
361 <span class="c1"># ∂a(¬a) → ϕ</span>
362 <span class="k">if</span> <span class="n">R</span> <span class="o">==</span> <span class="n">y</span> <span class="ow">or</span> <span class="n">R</span> <span class="o">==</span> <span class="n">phi</span> <span class="ow">or</span> <span class="n">R</span> <span class="ow">in</span> <span class="n">syms</span><span class="p">:</span>
363 <span class="k">return</span> <span class="n">phi</span>
365 <span class="n">tag</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span>
367 <span class="c1"># ∂a(R*) → ∂a(R)∘R*</span>
368 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">KSTAR</span><span class="p">:</span>
369 <span class="k">return</span> <span class="n">_cons</span><span class="p">(</span><span class="n">derv</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">]),</span> <span class="n">R</span><span class="p">)</span>
371 <span class="c1"># ∂a(¬R) → ¬∂a(R)</span>
372 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">NOT</span><span class="p">:</span>
373 <span class="k">return</span> <span class="p">(</span><span class="n">NOT</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">]))</span>
375 <span class="n">r</span><span class="p">,</span> <span class="n">s</span> <span class="o">=</span> <span class="n">R</span><span class="p">[</span><span class="mi">1</span><span class="p">:]</span>
377 <span class="c1"># ∂a(R∘S) → ∂a(R)∘S ∨ δ(R)∘∂a(S)</span>
378 <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">CONS</span><span class="p">:</span>
379 <span class="n">A</span> <span class="o">=</span> <span class="n">_cons</span><span class="p">(</span><span class="n">derv</span><span class="p">(</span><span class="n">r</span><span class="p">),</span> <span class="n">s</span><span class="p">)</span> <span class="c1"># A = ∂a(r)∘s</span>
380 <span class="c1"># A ∨ δ(R) ∘ ∂a(S)</span>
381 <span class="c1"># A ∨ λ ∘ ∂a(S) → A ∨ ∂a(S)</span>
382 <span class="c1"># A ∨ ϕ ∘ ∂a(S) → A ∨ ϕ → A</span>
383 <span class="k">return</span> <span class="n">_or</span><span class="p">(</span><span class="n">A</span><span class="p">,</span> <span class="n">derv</span><span class="p">(</span><span class="n">s</span><span class="p">))</span> <span class="k">if</span> <span class="n">nully</span><span class="p">(</span><span class="n">r</span><span class="p">)</span> <span class="k">else</span> <span class="n">A</span>
385 <span class="c1"># ∂a(R ∧ S) → ∂a(R) ∧ ∂a(S)</span>
386 <span class="c1"># ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)</span>
387 <span class="n">dr</span><span class="p">,</span> <span class="n">ds</span> <span class="o">=</span> <span class="n">derv</span><span class="p">(</span><span class="n">r</span><span class="p">),</span> <span class="n">derv</span><span class="p">(</span><span class="n">s</span><span class="p">)</span>
388 <span class="k">return</span> <span class="n">_and</span><span class="p">(</span><span class="n">dr</span><span class="p">,</span> <span class="n">ds</span><span class="p">)</span> <span class="k">if</span> <span class="n">tag</span> <span class="o">==</span> <span class="n">AND</span> <span class="k">else</span> <span class="n">_or</span><span class="p">(</span><span class="n">dr</span><span class="p">,</span> <span class="n">ds</span><span class="p">)</span>
390 <span class="k">return</span> <span class="n">derv</span>
395 <section id="lets-try-it-out">
396 <h2>Let’s try it out…<a class="headerlink" href="#lets-try-it-out" title="Permalink to this headline">¶</a></h2>
397 <p>(FIXME: redo.)</p>
398 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">o</span><span class="p">,</span> <span class="n">z</span> <span class="o">=</span> <span class="n">D_compaction</span><span class="p">(</span><span class="s1">'0'</span><span class="p">),</span> <span class="n">D_compaction</span><span class="p">(</span><span class="s1">'1'</span><span class="p">)</span>
399 <span class="n">REs</span> <span class="o">=</span> <span class="nb">set</span><span class="p">()</span>
400 <span class="n">N</span> <span class="o">=</span> <span class="mi">5</span>
401 <span class="n">names</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">product</span><span class="p">(</span><span class="o">*</span><span class="p">(</span><span class="n">N</span> <span class="o">*</span> <span class="p">[(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">)])))</span>
402 <span class="n">dervs</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">product</span><span class="p">(</span><span class="o">*</span><span class="p">(</span><span class="n">N</span> <span class="o">*</span> <span class="p">[(</span><span class="n">o</span><span class="p">,</span> <span class="n">z</span><span class="p">)])))</span>
403 <span class="k">for</span> <span class="n">name</span><span class="p">,</span> <span class="n">ds</span> <span class="ow">in</span> <span class="nb">zip</span><span class="p">(</span><span class="n">names</span><span class="p">,</span> <span class="n">dervs</span><span class="p">):</span>
404 <span class="n">R</span> <span class="o">=</span> <span class="n">it</span>
405 <span class="n">ds</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="n">ds</span><span class="p">)</span>
406 <span class="k">while</span> <span class="n">ds</span><span class="p">:</span>
407 <span class="n">R</span> <span class="o">=</span> <span class="n">ds</span><span class="o">.</span><span class="n">pop</span><span class="p">()(</span><span class="n">R</span><span class="p">)</span>
408 <span class="k">if</span> <span class="n">R</span> <span class="o">==</span> <span class="n">phi</span> <span class="ow">or</span> <span class="n">R</span> <span class="o">==</span> <span class="n">I</span><span class="p">:</span>
409 <span class="k">break</span>
410 <span class="n">REs</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">R</span><span class="p">)</span>
412 <span class="nb">print</span> <span class="n">stringy</span><span class="p">(</span><span class="n">it</span><span class="p">)</span> <span class="p">;</span> <span class="nb">print</span>
413 <span class="nb">print</span> <span class="n">o</span><span class="o">.</span><span class="n">hits</span><span class="p">,</span> <span class="s1">'/'</span><span class="p">,</span> <span class="n">o</span><span class="o">.</span><span class="n">calls</span>
414 <span class="nb">print</span> <span class="n">z</span><span class="o">.</span><span class="n">hits</span><span class="p">,</span> <span class="s1">'/'</span><span class="p">,</span> <span class="n">z</span><span class="o">.</span><span class="n">calls</span>
415 <span class="nb">print</span>
416 <span class="k">for</span> <span class="n">s</span> <span class="ow">in</span> <span class="nb">sorted</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="n">stringy</span><span class="p">,</span> <span class="n">REs</span><span class="p">),</span> <span class="n">key</span><span class="o">=</span><span class="k">lambda</span> <span class="n">n</span><span class="p">:</span> <span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">n</span><span class="p">),</span> <span class="n">n</span><span class="p">)):</span>
417 <span class="nb">print</span> <span class="n">s</span>
420 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">11</span><span class="o">*</span><span class="p">)</span><span class="s1">')</span>
422 <span class="mi">92</span> <span class="o">/</span> <span class="mi">122</span>
423 <span class="mi">92</span> <span class="o">/</span> <span class="mi">122</span>
425 <span class="p">(</span><span class="o">.</span><span class="mi">01</span><span class="p">)</span><span class="s1">'</span>
426 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="p">)</span><span class="s1">'</span>
427 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="o">^</span><span class="p">)</span><span class="s1">'</span>
428 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">'</span>
429 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="p">)</span><span class="s1">')</span>
430 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="o">^</span><span class="p">)</span><span class="s1">')</span>
431 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span> <span class="o">|</span> <span class="mf">1.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span><span class="p">)</span><span class="s1">')</span>
432 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">')</span>
433 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span> <span class="o">|</span> <span class="mf">1.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">')</span>
437 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">11</span><span class="o">*</span><span class="p">)</span><span class="s1">')</span>
439 <span class="mi">92</span> <span class="o">/</span> <span class="mi">122</span>
440 <span class="mi">92</span> <span class="o">/</span> <span class="mi">122</span>
442 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="p">)</span><span class="s1">'</span>
443 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span> <span class="p">)</span><span class="s1">'</span>
444 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="o">^</span> <span class="p">)</span><span class="s1">'</span>
445 <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">'</span>
446 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span> <span class="p">)</span><span class="s1">')</span>
447 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="o">^</span> <span class="p">)</span><span class="s1">')</span>
448 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">')</span>
449 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span> <span class="o">|</span> <span class="mf">1.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="p">)</span><span class="s1">')</span>
450 <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span> <span class="o">|</span> <span class="mf">1.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">')</span>
454 <section id="larger-alphabets">
455 <h2>Larger Alphabets<a class="headerlink" href="#larger-alphabets" title="Permalink to this headline">¶</a></h2>
456 <p>We could parse larger alphabets by defining patterns for e.g. each byte
457 of the ASCII code. Or we can generalize this code. If you study the code
458 above you’ll see that we never use the “set-ness” of the symbols <code class="docutils literal notranslate"><span class="pre">O</span></code>
459 and <code class="docutils literal notranslate"><span class="pre">l</span></code>. The only time Python set operators (<code class="docutils literal notranslate"><span class="pre">&</span></code> and <code class="docutils literal notranslate"><span class="pre">|</span></code>) appear
460 is in the <code class="docutils literal notranslate"><span class="pre">nully()</span></code> function, and there they operate on (recursively
461 computed) outputs of that function, never <code class="docutils literal notranslate"><span class="pre">O</span></code> and <code class="docutils literal notranslate"><span class="pre">l</span></code>.</p>
462 <p>What if we try:</p>
463 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>(OR, O, l)
466 ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)
476 <p>And compare it to:</p>
477 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>{'0', '1')
479 ∂1({'0', '1'))
480 ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)
481 ∂1({'0')) ∨ ∂1({'1'))
483 ϕ ∨ ∂1({'1'))
490 <p>This suggests that we should be able to alter the functions above to
491 detect sets and deal with them appropriately. Exercise for the Reader
494 <section id="state-machine">
495 <h2>State Machine<a class="headerlink" href="#state-machine" title="Permalink to this headline">¶</a></h2>
496 <p>We can drive the regular expressions to flesh out the underlying state
497 machine transition table.</p>
498 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">.</span><span class="mf">111.</span> <span class="o">&</span> <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">+</span> <span class="mi">11</span><span class="o">*</span><span class="p">)</span><span class="s1">'</span>
501 <p>Says, “Three or more 1’s and not ending in 01 nor composed of all 1’s.”</p>
502 <figure class="align-default" id="id2">
503 <img alt="State Machine Graph" src="../_images/omg.svg" /><figcaption>
504 <p><span class="caption-text">State Machine Graph</span><a class="headerlink" href="#id2" title="Permalink to this image">¶</a></p>
507 <p>Start at <code class="docutils literal notranslate"><span class="pre">a</span></code> and follow the transition arrows according to their
508 labels. Accepting states have a double outline. (Graphic generated with
509 <a class="reference external" href="http://www.graphviz.org/">Dot from Graphviz</a>.) You’ll see that only
510 paths that lead to one of the accepting states will match the regular
511 expression. All other paths will terminate at one of the non-accepting
513 <p>There’s a happy path to <code class="docutils literal notranslate"><span class="pre">g</span></code> along 111:</p>
514 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>a→c→e→g
517 <p>After you reach <code class="docutils literal notranslate"><span class="pre">g</span></code> you’re stuck there eating 1’s until you see a 0,
518 which takes you to the <code class="docutils literal notranslate"><span class="pre">i→j→i|i→j→h→i</span></code> “trap”. You can’t reach any
519 other states from those two loops.</p>
520 <p>If you see a 0 before you see 111 you will reach <code class="docutils literal notranslate"><span class="pre">b</span></code>, which forms
521 another “trap” with <code class="docutils literal notranslate"><span class="pre">d</span></code> and <code class="docutils literal notranslate"><span class="pre">f</span></code>. The only way out is another happy
522 path along 111 to <code class="docutils literal notranslate"><span class="pre">h</span></code>:</p>
523 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>b→d→f→h
526 <p>Once you have reached <code class="docutils literal notranslate"><span class="pre">h</span></code> you can see as many 1’s or as many 0’ in a
527 row and still be either still at <code class="docutils literal notranslate"><span class="pre">h</span></code> (for 1’s) or move to <code class="docutils literal notranslate"><span class="pre">i</span></code> (for
528 0’s). If you find yourself at <code class="docutils literal notranslate"><span class="pre">i</span></code> you can see as many 0’s, or
529 repetitions of 10, as there are, but if you see just a 1 you move to
530 <code class="docutils literal notranslate"><span class="pre">j</span></code>.</p>
531 <section id="re-to-fsm">
532 <h3>RE to FSM<a class="headerlink" href="#re-to-fsm" title="Permalink to this headline">¶</a></h3>
533 <p>So how do we get the state machine from the regular expression?</p>
534 <p>It turns out that each RE is effectively a state, and each arrow points
535 to the derivative RE in respect to the arrow’s symbol.</p>
536 <p>If we label the initial RE <code class="docutils literal notranslate"><span class="pre">a</span></code>, we can say:</p>
537 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span>a --0--> ∂0(a)
541 <p>And so on, each new unique RE is a new state in the FSM table.</p>
542 <p>Here are the derived REs at each state:</p>
543 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">11</span><span class="o">*</span><span class="p">)</span><span class="s1">')</span>
544 <span class="n">b</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mf">111.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="p">)</span><span class="s1">')</span>
545 <span class="n">c</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">')</span>
546 <span class="n">d</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="o">^</span><span class="p">)</span><span class="s1">')</span>
547 <span class="n">e</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span> <span class="o">|</span> <span class="mf">1.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">')</span>
548 <span class="n">f</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mf">111.</span> <span class="o">|</span> <span class="mf">11.</span> <span class="o">|</span> <span class="mf">1.</span><span class="p">)</span> <span class="o">&</span> <span class="p">((</span><span class="o">.</span><span class="mi">01</span><span class="p">)</span><span class="s1">')</span>
549 <span class="n">g</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="o">*</span><span class="p">)</span><span class="s1">'</span>
550 <span class="n">h</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mi">01</span><span class="p">)</span><span class="s1">'</span>
551 <span class="n">i</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="mi">1</span><span class="p">)</span><span class="s1">'</span>
552 <span class="n">j</span> <span class="o">=</span> <span class="p">(</span><span class="o">.</span><span class="mi">01</span> <span class="o">|</span> <span class="o">^</span><span class="p">)</span><span class="s1">'</span>
555 <p>You can see the one-way nature of the <code class="docutils literal notranslate"><span class="pre">g</span></code> state and the <code class="docutils literal notranslate"><span class="pre">hij</span></code> “trap”
556 in the way that the <code class="docutils literal notranslate"><span class="pre">.111.</span></code> on the left-hand side of the <code class="docutils literal notranslate"><span class="pre">&</span></code>
557 disappears once it has been matched.</p>
558 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">collections</span> <span class="kn">import</span> <span class="n">defaultdict</span>
559 <span class="kn">from</span> <span class="nn">pprint</span> <span class="kn">import</span> <span class="n">pprint</span>
560 <span class="kn">from</span> <span class="nn">string</span> <span class="kn">import</span> <span class="n">ascii_lowercase</span>
563 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">d0</span><span class="p">,</span> <span class="n">d1</span> <span class="o">=</span> <span class="n">D_compaction</span><span class="p">(</span><span class="s1">'0'</span><span class="p">),</span> <span class="n">D_compaction</span><span class="p">(</span><span class="s1">'1'</span><span class="p">)</span>
567 <section id="explore">
568 <h3><code class="docutils literal notranslate"><span class="pre">explore()</span></code><a class="headerlink" href="#explore" title="Permalink to this headline">¶</a></h3>
569 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">explore</span><span class="p">(</span><span class="n">re</span><span class="p">):</span>
571 <span class="c1"># Don't have more than 26 states...</span>
572 <span class="n">names</span> <span class="o">=</span> <span class="n">defaultdict</span><span class="p">(</span><span class="nb">iter</span><span class="p">(</span><span class="n">ascii_lowercase</span><span class="p">)</span><span class="o">.</span><span class="n">next</span><span class="p">)</span>
574 <span class="n">table</span><span class="p">,</span> <span class="n">accepting</span> <span class="o">=</span> <span class="nb">dict</span><span class="p">(),</span> <span class="nb">set</span><span class="p">()</span>
576 <span class="n">to_check</span> <span class="o">=</span> <span class="p">{</span><span class="n">re</span><span class="p">}</span>
577 <span class="k">while</span> <span class="n">to_check</span><span class="p">:</span>
579 <span class="n">re</span> <span class="o">=</span> <span class="n">to_check</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
580 <span class="n">state_name</span> <span class="o">=</span> <span class="n">names</span><span class="p">[</span><span class="n">re</span><span class="p">]</span>
582 <span class="k">if</span> <span class="p">(</span><span class="n">state_name</span><span class="p">,</span> <span class="mi">0</span><span class="p">)</span> <span class="ow">in</span> <span class="n">table</span><span class="p">:</span>
583 <span class="k">continue</span>
585 <span class="k">if</span> <span class="n">nully</span><span class="p">(</span><span class="n">re</span><span class="p">):</span>
586 <span class="n">accepting</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">state_name</span><span class="p">)</span>
588 <span class="n">o</span><span class="p">,</span> <span class="n">i</span> <span class="o">=</span> <span class="n">d0</span><span class="p">(</span><span class="n">re</span><span class="p">),</span> <span class="n">d1</span><span class="p">(</span><span class="n">re</span><span class="p">)</span>
589 <span class="n">table</span><span class="p">[</span><span class="n">state_name</span><span class="p">,</span> <span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">names</span><span class="p">[</span><span class="n">o</span><span class="p">]</span> <span class="p">;</span> <span class="n">to_check</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">o</span><span class="p">)</span>
590 <span class="n">table</span><span class="p">[</span><span class="n">state_name</span><span class="p">,</span> <span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">names</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="p">;</span> <span class="n">to_check</span><span class="o">.</span><span class="n">add</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
592 <span class="k">return</span> <span class="n">table</span><span class="p">,</span> <span class="n">accepting</span>
595 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">table</span><span class="p">,</span> <span class="n">accepting</span> <span class="o">=</span> <span class="n">explore</span><span class="p">(</span><span class="n">it</span><span class="p">)</span>
596 <span class="n">table</span>
599 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">{(</span><span class="s1">'a'</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">'b'</span><span class="p">,</span>
600 <span class="p">(</span><span class="s1">'a'</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">'c'</span><span class="p">,</span>
601 <span class="p">(</span><span class="s1">'b'</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">'b'</span><span class="p">,</span>
602 <span class="p">(</span><span class="s1">'b'</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">'d'</span><span class="p">,</span>
603 <span class="p">(</span><span class="s1">'c'</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">'b'</span><span class="p">,</span>
604 <span class="p">(</span><span class="s1">'c'</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">'e'</span><span class="p">,</span>
605 <span class="p">(</span><span class="s1">'d'</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">'b'</span><span class="p">,</span>
606 <span class="p">(</span><span class="s1">'d'</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">'f'</span><span class="p">,</span>
607 <span class="p">(</span><span class="s1">'e'</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">'b'</span><span class="p">,</span>
608 <span class="p">(</span><span class="s1">'e'</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">'g'</span><span class="p">,</span>
609 <span class="p">(</span><span class="s1">'f'</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">'b'</span><span class="p">,</span>
610 <span class="p">(</span><span class="s1">'f'</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">'h'</span><span class="p">,</span>
611 <span class="p">(</span><span class="s1">'g'</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">'i'</span><span class="p">,</span>
612 <span class="p">(</span><span class="s1">'g'</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">'g'</span><span class="p">,</span>
613 <span class="p">(</span><span class="s1">'h'</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">'i'</span><span class="p">,</span>
614 <span class="p">(</span><span class="s1">'h'</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">'h'</span><span class="p">,</span>
615 <span class="p">(</span><span class="s1">'i'</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">'i'</span><span class="p">,</span>
616 <span class="p">(</span><span class="s1">'i'</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">'j'</span><span class="p">,</span>
617 <span class="p">(</span><span class="s1">'j'</span><span class="p">,</span> <span class="mi">0</span><span class="p">):</span> <span class="s1">'i'</span><span class="p">,</span>
618 <span class="p">(</span><span class="s1">'j'</span><span class="p">,</span> <span class="mi">1</span><span class="p">):</span> <span class="s1">'h'</span><span class="p">}</span>
621 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">accepting</span>
624 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">{</span><span class="s1">'h'</span><span class="p">,</span> <span class="s1">'i'</span><span class="p">}</span>
628 <section id="generate-diagram">
629 <h3>Generate Diagram<a class="headerlink" href="#generate-diagram" title="Permalink to this headline">¶</a></h3>
630 <p>Once we have the FSM table and the set of accepting states we can
631 generate the diagram above.</p>
632 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">_template</span> <span class="o">=</span> <span class="s1">'''</span><span class="se">\</span>
633 <span class="s1">digraph finite_state_machine {</span>
634 <span class="s1"> rankdir=LR;</span>
635 <span class="s1"> size="8,5"</span>
636 <span class="s1"> node [shape = doublecircle]; </span><span class="si">%s</span><span class="s1">;</span>
637 <span class="s1"> node [shape = circle];</span>
638 <span class="si">%s</span><span class="s1"></span>
639 <span class="s1">}</span>
640 <span class="s1">'''</span>
642 <span class="k">def</span> <span class="nf">link</span><span class="p">(</span><span class="n">fr</span><span class="p">,</span> <span class="n">nm</span><span class="p">,</span> <span class="n">label</span><span class="p">):</span>
643 <span class="k">return</span> <span class="s1">' </span><span class="si">%s</span><span class="s1"> -> </span><span class="si">%s</span><span class="s1"> [ label = "</span><span class="si">%s</span><span class="s1">" ];'</span> <span class="o">%</span> <span class="p">(</span><span class="n">fr</span><span class="p">,</span> <span class="n">nm</span><span class="p">,</span> <span class="n">label</span><span class="p">)</span>
646 <span class="k">def</span> <span class="nf">make_graph</span><span class="p">(</span><span class="n">table</span><span class="p">,</span> <span class="n">accepting</span><span class="p">):</span>
647 <span class="k">return</span> <span class="n">_template</span> <span class="o">%</span> <span class="p">(</span>
648 <span class="s1">' '</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="n">accepting</span><span class="p">),</span>
649 <span class="s1">'</span><span class="se">\n</span><span class="s1">'</span><span class="o">.</span><span class="n">join</span><span class="p">(</span>
650 <span class="n">link</span><span class="p">(</span><span class="n">from_</span><span class="p">,</span> <span class="n">to</span><span class="p">,</span> <span class="n">char</span><span class="p">)</span>
651 <span class="k">for</span> <span class="p">(</span><span class="n">from_</span><span class="p">,</span> <span class="n">char</span><span class="p">),</span> <span class="p">(</span><span class="n">to</span><span class="p">)</span> <span class="ow">in</span> <span class="nb">sorted</span><span class="p">(</span><span class="n">table</span><span class="o">.</span><span class="n">iteritems</span><span class="p">())</span>
652 <span class="p">)</span>
653 <span class="p">)</span>
656 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="nb">print</span> <span class="n">make_graph</span><span class="p">(</span><span class="n">table</span><span class="p">,</span> <span class="n">accepting</span><span class="p">)</span>
659 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">digraph</span> <span class="n">finite_state_machine</span> <span class="p">{</span>
660 <span class="n">rankdir</span><span class="o">=</span><span class="n">LR</span><span class="p">;</span>
661 <span class="n">size</span><span class="o">=</span><span class="s2">"8,5"</span>
662 <span class="n">node</span> <span class="p">[</span><span class="n">shape</span> <span class="o">=</span> <span class="n">doublecircle</span><span class="p">];</span> <span class="n">i</span> <span class="n">h</span><span class="p">;</span>
663 <span class="n">node</span> <span class="p">[</span><span class="n">shape</span> <span class="o">=</span> <span class="n">circle</span><span class="p">];</span>
664 <span class="n">a</span> <span class="o">-></span> <span class="n">b</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"0"</span> <span class="p">];</span>
665 <span class="n">a</span> <span class="o">-></span> <span class="n">c</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"1"</span> <span class="p">];</span>
666 <span class="n">b</span> <span class="o">-></span> <span class="n">b</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"0"</span> <span class="p">];</span>
667 <span class="n">b</span> <span class="o">-></span> <span class="n">d</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"1"</span> <span class="p">];</span>
668 <span class="n">c</span> <span class="o">-></span> <span class="n">b</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"0"</span> <span class="p">];</span>
669 <span class="n">c</span> <span class="o">-></span> <span class="n">e</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"1"</span> <span class="p">];</span>
670 <span class="n">d</span> <span class="o">-></span> <span class="n">b</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"0"</span> <span class="p">];</span>
671 <span class="n">d</span> <span class="o">-></span> <span class="n">f</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"1"</span> <span class="p">];</span>
672 <span class="n">e</span> <span class="o">-></span> <span class="n">b</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"0"</span> <span class="p">];</span>
673 <span class="n">e</span> <span class="o">-></span> <span class="n">g</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"1"</span> <span class="p">];</span>
674 <span class="n">f</span> <span class="o">-></span> <span class="n">b</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"0"</span> <span class="p">];</span>
675 <span class="n">f</span> <span class="o">-></span> <span class="n">h</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"1"</span> <span class="p">];</span>
676 <span class="n">g</span> <span class="o">-></span> <span class="n">i</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"0"</span> <span class="p">];</span>
677 <span class="n">g</span> <span class="o">-></span> <span class="n">g</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"1"</span> <span class="p">];</span>
678 <span class="n">h</span> <span class="o">-></span> <span class="n">i</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"0"</span> <span class="p">];</span>
679 <span class="n">h</span> <span class="o">-></span> <span class="n">h</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"1"</span> <span class="p">];</span>
680 <span class="n">i</span> <span class="o">-></span> <span class="n">i</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"0"</span> <span class="p">];</span>
681 <span class="n">i</span> <span class="o">-></span> <span class="n">j</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"1"</span> <span class="p">];</span>
682 <span class="n">j</span> <span class="o">-></span> <span class="n">i</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"0"</span> <span class="p">];</span>
683 <span class="n">j</span> <span class="o">-></span> <span class="n">h</span> <span class="p">[</span> <span class="n">label</span> <span class="o">=</span> <span class="s2">"1"</span> <span class="p">];</span>
684 <span class="p">}</span>
688 <section id="drive-a-fsm">
689 <h3>Drive a FSM<a class="headerlink" href="#drive-a-fsm" title="Permalink to this headline">¶</a></h3>
690 <p>There are <em>lots</em> of FSM libraries already. Once you have the state
691 transition table they should all be straightforward to use. State
692 Machine code is very simple. Just for fun, here is an implementation in
693 Python that imitates what “compiled” FSM code might look like in an
694 “unrolled” form. Most FSM code uses a little driver loop and a table
695 datastructure, the code below instead acts like JMP instructions
696 (“jump”, or GOTO in higher-level-but-still-low-level languages) to
697 hard-code the information in the table into a little patch of branches.</p>
698 <section id="trampoline-function">
699 <h4>Trampoline Function<a class="headerlink" href="#trampoline-function" title="Permalink to this headline">¶</a></h4>
700 <p>Python has no GOTO statement but we can fake it with a “trampoline”
702 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">trampoline</span><span class="p">(</span><span class="n">input_</span><span class="p">,</span> <span class="n">jump_from</span><span class="p">,</span> <span class="n">accepting</span><span class="p">):</span>
703 <span class="n">I</span> <span class="o">=</span> <span class="nb">iter</span><span class="p">(</span><span class="n">input_</span><span class="p">)</span>
704 <span class="k">while</span> <span class="kc">True</span><span class="p">:</span>
705 <span class="k">try</span><span class="p">:</span>
706 <span class="n">bounce_to</span> <span class="o">=</span> <span class="n">jump_from</span><span class="p">(</span><span class="n">I</span><span class="p">)</span>
707 <span class="k">except</span> <span class="ne">StopIteration</span><span class="p">:</span>
708 <span class="k">return</span> <span class="n">jump_from</span> <span class="ow">in</span> <span class="n">accepting</span>
709 <span class="n">jump_from</span> <span class="o">=</span> <span class="n">bounce_to</span>
713 <section id="stream-functions">
714 <h4>Stream Functions<a class="headerlink" href="#stream-functions" title="Permalink to this headline">¶</a></h4>
715 <p>Little helpers to process the iterator of our data (a “stream” of “1”
716 and “0” characters, not bits.)</p>
717 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">getch</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="nb">int</span><span class="p">(</span><span class="nb">next</span><span class="p">(</span><span class="n">I</span><span class="p">))</span>
720 <span class="k">def</span> <span class="nf">_1</span><span class="p">(</span><span class="n">I</span><span class="p">):</span>
721 <span class="sd">'''Loop on ones.'''</span>
722 <span class="k">while</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">):</span> <span class="k">pass</span>
725 <span class="k">def</span> <span class="nf">_0</span><span class="p">(</span><span class="n">I</span><span class="p">):</span>
726 <span class="sd">'''Loop on zeros.'''</span>
727 <span class="k">while</span> <span class="ow">not</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">):</span> <span class="k">pass</span>
731 <section id="a-finite-state-machine">
732 <h4>A Finite State Machine<a class="headerlink" href="#a-finite-state-machine" title="Permalink to this headline">¶</a></h4>
733 <p>With those preliminaries out of the way, from the state table of
734 <code class="docutils literal notranslate"><span class="pre">.111.</span> <span class="pre">&</span> <span class="pre">(.01</span> <span class="pre">+</span> <span class="pre">11*)'</span></code> we can immediately write down state machine
735 code. (You have to imagine that these are GOTO statements in C or
736 branches in assembly and that the state names are branch destination
738 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="n">a</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">c</span> <span class="k">if</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="k">else</span> <span class="n">b</span>
739 <span class="n">b</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">_0</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="ow">or</span> <span class="n">d</span>
740 <span class="n">c</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">e</span> <span class="k">if</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="k">else</span> <span class="n">b</span>
741 <span class="n">d</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">f</span> <span class="k">if</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="k">else</span> <span class="n">b</span>
742 <span class="n">e</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">g</span> <span class="k">if</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="k">else</span> <span class="n">b</span>
743 <span class="n">f</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">h</span> <span class="k">if</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="k">else</span> <span class="n">b</span>
744 <span class="n">g</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">_1</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="ow">or</span> <span class="n">i</span>
745 <span class="n">h</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">_1</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="ow">or</span> <span class="n">i</span>
746 <span class="n">i</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">_0</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="ow">or</span> <span class="n">j</span>
747 <span class="n">j</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">I</span><span class="p">:</span> <span class="n">h</span> <span class="k">if</span> <span class="n">getch</span><span class="p">(</span><span class="n">I</span><span class="p">)</span> <span class="k">else</span> <span class="n">i</span>
750 <p>Note that the implementations of <code class="docutils literal notranslate"><span class="pre">h</span></code> and <code class="docutils literal notranslate"><span class="pre">g</span></code> are identical ergo
751 <code class="docutils literal notranslate"><span class="pre">h</span> <span class="pre">=</span> <span class="pre">g</span></code> and we could eliminate one in the code but <code class="docutils literal notranslate"><span class="pre">h</span></code> is an
752 accepting state and <code class="docutils literal notranslate"><span class="pre">g</span></code> isn’t.</p>
753 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">acceptable</span><span class="p">(</span><span class="n">input_</span><span class="p">):</span>
754 <span class="k">return</span> <span class="n">trampoline</span><span class="p">(</span><span class="n">input_</span><span class="p">,</span> <span class="n">a</span><span class="p">,</span> <span class="p">{</span><span class="n">h</span><span class="p">,</span> <span class="n">i</span><span class="p">})</span>
757 <div class="highlight-python notranslate"><div class="highlight"><pre><span></span><span class="k">for</span> <span class="n">n</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">2</span><span class="o">**</span><span class="mi">5</span><span class="p">):</span>
758 <span class="n">s</span> <span class="o">=</span> <span class="nb">bin</span><span class="p">(</span><span class="n">n</span><span class="p">)[</span><span class="mi">2</span><span class="p">:]</span>
759 <span class="nb">print</span> <span class="s1">'</span><span class="si">%05s</span><span class="s1">'</span> <span class="o">%</span> <span class="n">s</span><span class="p">,</span> <span class="n">acceptable</span><span class="p">(</span><span class="n">s</span><span class="p">)</span>
762 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span> <span class="mi">0</span> <span class="kc">False</span>
763 <span class="mi">1</span> <span class="kc">False</span>
764 <span class="mi">10</span> <span class="kc">False</span>
765 <span class="mi">11</span> <span class="kc">False</span>
766 <span class="mi">100</span> <span class="kc">False</span>
767 <span class="mi">101</span> <span class="kc">False</span>
768 <span class="mi">110</span> <span class="kc">False</span>
769 <span class="mi">111</span> <span class="kc">False</span>
770 <span class="mi">1000</span> <span class="kc">False</span>
771 <span class="mi">1001</span> <span class="kc">False</span>
772 <span class="mi">1010</span> <span class="kc">False</span>
773 <span class="mi">1011</span> <span class="kc">False</span>
774 <span class="mi">1100</span> <span class="kc">False</span>
775 <span class="mi">1101</span> <span class="kc">False</span>
776 <span class="mi">1110</span> <span class="kc">True</span>
777 <span class="mi">1111</span> <span class="kc">False</span>
778 <span class="mi">10000</span> <span class="kc">False</span>
779 <span class="mi">10001</span> <span class="kc">False</span>
780 <span class="mi">10010</span> <span class="kc">False</span>
781 <span class="mi">10011</span> <span class="kc">False</span>
782 <span class="mi">10100</span> <span class="kc">False</span>
783 <span class="mi">10101</span> <span class="kc">False</span>
784 <span class="mi">10110</span> <span class="kc">False</span>
785 <span class="mi">10111</span> <span class="kc">True</span>
786 <span class="mi">11000</span> <span class="kc">False</span>
787 <span class="mi">11001</span> <span class="kc">False</span>
788 <span class="mi">11010</span> <span class="kc">False</span>
789 <span class="mi">11011</span> <span class="kc">False</span>
790 <span class="mi">11100</span> <span class="kc">True</span>
791 <span class="mi">11101</span> <span class="kc">False</span>
792 <span class="mi">11110</span> <span class="kc">True</span>
793 <span class="mi">11111</span> <span class="kc">False</span>
799 <section id="reversing-the-derivatives-to-generate-matching-strings">
800 <h2>Reversing the Derivatives to Generate Matching Strings<a class="headerlink" href="#reversing-the-derivatives-to-generate-matching-strings" title="Permalink to this headline">¶</a></h2>
801 <p>(UNFINISHED) Brzozowski also shewed how to go from the state machine to
802 strings and expressions…</p>
803 <p>Each of these states is just a name for a Brzozowskian RE, and so, other
804 than the initial state <code class="docutils literal notranslate"><span class="pre">a</span></code>, they can can be described in terms of the
805 derivative-with-respect-to-N of some other state/RE:</p>
806 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">c</span> <span class="o">=</span> <span class="n">d1</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>
807 <span class="n">b</span> <span class="o">=</span> <span class="n">d0</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>
808 <span class="n">b</span> <span class="o">=</span> <span class="n">d0</span><span class="p">(</span><span class="n">c</span><span class="p">)</span>
809 <span class="o">...</span>
810 <span class="n">i</span> <span class="o">=</span> <span class="n">d0</span><span class="p">(</span><span class="n">j</span><span class="p">)</span>
811 <span class="n">j</span> <span class="o">=</span> <span class="n">d1</span><span class="p">(</span><span class="n">i</span><span class="p">)</span>
815 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">c</span> <span class="o">=</span> <span class="n">d1</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>
816 <span class="n">b</span> <span class="o">=</span> <span class="n">d0</span><span class="p">(</span><span class="n">c</span><span class="p">)</span>
820 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">b</span> <span class="o">=</span> <span class="n">d0</span><span class="p">(</span><span class="n">d1</span><span class="p">(</span><span class="n">a</span><span class="p">))</span>
824 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">b</span> <span class="o">=</span> <span class="n">d10</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>
828 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">j</span> <span class="o">=</span> <span class="n">d1</span><span class="p">(</span><span class="n">d0</span><span class="p">(</span><span class="n">j</span><span class="p">))</span>
832 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">j</span> <span class="o">=</span> <span class="n">d1</span><span class="p">(</span><span class="n">d0</span><span class="p">(</span><span class="n">j</span><span class="p">))</span> <span class="o">=</span> <span class="n">d01</span><span class="p">(</span><span class="n">j</span><span class="p">)</span>
835 <p>We have a loop or “fixed point”.</p>
836 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">j</span> <span class="o">=</span> <span class="n">d01</span><span class="p">(</span><span class="n">j</span><span class="p">)</span> <span class="o">=</span> <span class="n">d0101</span><span class="p">(</span><span class="n">j</span><span class="p">)</span> <span class="o">=</span> <span class="n">d010101</span><span class="p">(</span><span class="n">j</span><span class="p">)</span> <span class="o">=</span> <span class="o">...</span>
840 <div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">j</span> <span class="o">=</span> <span class="p">(</span><span class="mi">01</span><span class="p">)</span><span class="o">*</span>
851 <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
852 <div class="sphinxsidebarwrapper">
853 <h1 class="logo"><a href="../index.html">Thun</a></h1>
864 <li class="toctree-l1"><a class="reference internal" href="Intro.html">Thun: Joy in Python</a></li>
865 <li class="toctree-l1"><a class="reference internal" href="../joy.html">Joy Interpreter</a></li>
866 <li class="toctree-l1"><a class="reference internal" href="../stack.html">Stack or Quote or Sequence or List…</a></li>
867 <li class="toctree-l1"><a class="reference internal" href="../parser.html">Parsing Text into Joy Expressions</a></li>
868 <li class="toctree-l1"><a class="reference internal" href="../pretty.html">Tracing Joy Execution</a></li>
869 <li class="toctree-l1"><a class="reference internal" href="../library.html">Function Reference</a></li>
870 <li class="toctree-l1"><a class="reference internal" href="../lib.html">Functions Grouped by, er, Function with Examples</a></li>
871 <li class="toctree-l1"><a class="reference internal" href="../types.html">Type Inference of Joy Expressions</a></li>
872 <li class="toctree-l1 current"><a class="reference internal" href="index.html">Essays about Programming in Joy</a><ul class="current">
873 <li class="toctree-l2"><a class="reference internal" href="Developing.html">Developing a Program in Joy</a></li>
874 <li class="toctree-l2"><a class="reference internal" href="Quadratic.html">Quadratic formula</a></li>
875 <li class="toctree-l2"><a class="reference internal" href="Replacing.html">Replacing Functions in the Dictionary</a></li>
876 <li class="toctree-l2"><a class="reference internal" href="Recursion_Combinators.html">Recursion Combinators</a></li>
877 <li class="toctree-l2"><a class="reference internal" href="Ordered_Binary_Trees.html">Treating Trees I: Ordered Binary Trees</a></li>
878 <li class="toctree-l2"><a class="reference internal" href="Treestep.html">Treating Trees II: <code class="docutils literal notranslate"><span class="pre">treestep</span></code></a></li>
879 <li class="toctree-l2"><a class="reference internal" href="Generator_Programs.html">Using <code class="docutils literal notranslate"><span class="pre">x</span></code> to Generate Values</a></li>
880 <li class="toctree-l2"><a class="reference internal" href="Newton-Raphson.html">Newton’s method</a></li>
881 <li class="toctree-l2"><a class="reference internal" href="Zipper.html">Traversing Datastructures with Zippers</a></li>
882 <li class="toctree-l2"><a class="reference internal" href="Types.html">The Blissful Elegance of Typing Joy</a></li>
883 <li class="toctree-l2"><a class="reference internal" href="TypeChecking.html">Type Checking</a></li>
884 <li class="toctree-l2"><a class="reference internal" href="NoUpdates.html">No Updates</a></li>
885 <li class="toctree-l2"><a class="reference internal" href="Categorical.html">Categorical Programming</a></li>
886 <li class="toctree-l2"><a class="reference internal" href="The_Four_Operations.html">The Four Fundamental Operations of Definite Action</a></li>
887 <li class="toctree-l2 current"><a class="current reference internal" href="#">∂RE</a></li>
892 <div class="relations">
893 <h3>Related Topics</h3>
895 <li><a href="../index.html">Documentation overview</a><ul>
896 <li><a href="index.html">Essays about Programming in Joy</a><ul>
897 <li>Previous: <a href="The_Four_Operations.html" title="previous chapter">The Four Fundamental Operations of Definite Action</a></li>
902 <div id="searchbox" style="display: none" role="search">
903 <h3 id="searchlabel">Quick search</h3>
904 <div class="searchformwrapper">
905 <form class="search" action="../search.html" method="get">
906 <input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
907 <input type="submit" value="Go" />
911 <script>$('#searchbox').show(0);</script>
922 <div class="clearer"></div>
924 <div class="footer" role="contentinfo">
925 <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">
926 <img alt="Creative Commons License" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png" />
929 <span xmlns:dct="http://purl.org/dc/terms/" property="dct:title">Thun Documentation</span> by <a xmlns:cc="http://creativecommons.org/ns#" href="https://joypy.osdn.io/" property="cc:attributionName" rel="cc:attributionURL">Simon Forman</a> is licensed under a <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/">Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License</a>.<br />Based on a work at <a xmlns:dct="http://purl.org/dc/terms/" href="https://osdn.net/projects/joypy/" rel="dct:source">https://osdn.net/projects/joypy/</a>.
930 Created using <a href="http://sphinx-doc.org/">Sphinx</a> 4.3.0.