{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# ∂RE\n", "\n", "## Brzozowski's Derivatives of Regular Expressions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Legend:\n", "\n", " ∧ intersection\n", " ∨ union\n", " ∘ concatenation (see below)\n", " ¬ complement\n", " ϕ empty set (aka ∅)\n", " λ singleton set containing just the empty string\n", " I set of all letters in alphabet" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Derivative of a set `R` of strings and a string `a`:\n", "\n", " ∂a(R)\n", "\n", " ∂a(a) → λ\n", " ∂a(λ) → ϕ\n", " ∂a(ϕ) → ϕ\n", " ∂a(¬a) → ϕ\n", " ∂a(R*) → ∂a(R)∘R*\n", " ∂a(¬R) → ¬∂a(R)\n", " ∂a(R∘S) → ∂a(R)∘S ∨ δ(R)∘∂a(S)\n", " ∂a(R ∧ S) → ∂a(R) ∧ ∂a(S)\n", " ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)\n", "\n", " ∂ab(R) = ∂b(∂a(R))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Auxiliary predicate function `δ` (I call it `nully`) returns either `λ` if `λ ⊆ R` or `ϕ` otherwise:\n", "\n", " δ(a) → ϕ\n", " δ(λ) → λ\n", " δ(ϕ) → ϕ\n", " δ(R*) → λ\n", " δ(¬R) δ(R)≟ϕ → λ\n", " δ(¬R) δ(R)≟λ → ϕ\n", " δ(R∘S) → δ(R) ∧ δ(S)\n", " δ(R ∧ S) → δ(R) ∧ δ(S)\n", " δ(R ∨ S) → δ(R) ∨ δ(S)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Some rules we will use later for \"compaction\":\n", "\n", " R ∧ ϕ = ϕ ∧ R = ϕ\n", "\n", " R ∧ I = I ∧ R = R\n", "\n", " R ∨ ϕ = ϕ ∨ R = R\n", "\n", " R ∨ I = I ∨ R = I\n", "\n", " R∘ϕ = ϕ∘R = ϕ\n", "\n", " R∘λ = λ∘R = R" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Concatination of sets: for two sets A and B the set A∘B is defined as:\n", "\n", " {a∘b for a in A for b in B}\n", "\n", "E.g.:\n", "\n", " {'a', 'b'}∘{'c', 'd'} → {'ac', 'ad', 'bc', 'bd'}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Implementation" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from functools import partial as curry\n", "from itertools import product" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### `ϕ` and `λ`\n", "The empty set and the set of just the empty string." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "phi = frozenset() # ϕ\n", "y = frozenset({''}) # λ" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Two-letter Alphabet\n", "I'm only going to use two symbols (at first) becaase this is enough to illustrate the algorithm and because you can represent any other alphabet with two symbols (if you had to.)\n", "\n", "I chose the names `O` and `l` (uppercase \"o\" and lowercase \"L\") to look like `0` and `1` (zero and one) respectively." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "syms = O, l = frozenset({'0'}), frozenset({'1'})" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Representing Regular Expressions\n", "To represent REs in Python I'm going to use tagged tuples. A _regular expression_ is one of:\n", "\n", " O\n", " l\n", " (KSTAR, R)\n", " (NOT, R)\n", " (AND, R, S)\n", " (CONS, R, S)\n", " (OR, R, S)\n", "\n", "Where `R` and `S` stand for _regular expressions_." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "AND, CONS, KSTAR, NOT, OR = 'and cons * not or'.split() # Tags are just strings." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Because they are formed of `frozenset`, `tuple` and `str` objects only, these datastructures are immutable." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### String Representation of RE Datastructures" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "def stringy(re):\n", " '''\n", " Return a nice string repr for a regular expression datastructure.\n", " '''\n", " if re == I: return '.'\n", " if re in syms: return next(iter(re))\n", " if re == y: return '^'\n", " if re == phi: return 'X'\n", "\n", " assert isinstance(re, tuple), repr(re)\n", " tag = re[0]\n", "\n", " if tag == KSTAR:\n", " body = stringy(re[1])\n", " if not body: return body\n", " if len(body) > 1: return '(' + body + \")*\"\n", " return body + '*'\n", "\n", " if tag == NOT:\n", " body = stringy(re[1])\n", " if not body: return body\n", " if len(body) > 1: return '(' + body + \")'\"\n", " return body + \"'\"\n", "\n", " r, s = stringy(re[1]), stringy(re[2])\n", " if tag == CONS: return r + s\n", " if tag == OR: return '%s | %s' % (r, s)\n", " if tag == AND: return '(%s) & (%s)' % (r, s)\n", "\n", " raise ValueError" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### `I`\n", "Match anything. Often spelled \".\"\n", "\n", " I = (0|1)*" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "I = (KSTAR, (OR, O, l))" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ ".\n" ] } ], "source": [ "print stringy(I)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### `(.111.) & (.01 + 11*)'`\n", "The example expression from Brzozowski:\n", "\n", " (.111.) & (.01 + 11*)'\n", " a & (b + c)'\n", "\n", "Note that it contains one of everything." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "a = (CONS, I, (CONS, l, (CONS, l, (CONS, l, I))))\n", "b = (CONS, I, (CONS, O, l))\n", "c = (CONS, l, (KSTAR, l))\n", "it = (AND, a, (NOT, (OR, b, c)))" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(.111.) & ((.01 | 11*)')\n" ] } ], "source": [ "print stringy(it)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### `nully()`\n", "Let's get that auxiliary predicate function `δ` out of the way." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "def nully(R):\n", " '''\n", " δ - Return λ if λ ⊆ R otherwise ϕ.\n", " '''\n", "\n", " # δ(a) → ϕ\n", " # δ(ϕ) → ϕ\n", " if R in syms or R == phi:\n", " return phi\n", "\n", " # δ(λ) → λ\n", " if R == y:\n", " return y\n", "\n", " tag = R[0]\n", "\n", " # δ(R*) → λ\n", " if tag == KSTAR:\n", " return y\n", "\n", " # δ(¬R) δ(R)≟ϕ → λ\n", " # δ(¬R) δ(R)≟λ → ϕ\n", " if tag == NOT:\n", " return phi if nully(R[1]) else y\n", "\n", " # δ(R∘S) → δ(R) ∧ δ(S)\n", " # δ(R ∧ S) → δ(R) ∧ δ(S)\n", " # δ(R ∨ S) → δ(R) ∨ δ(S)\n", " r, s = nully(R[1]), nully(R[2])\n", " return r & s if tag in {AND, CONS} else r | s" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### No \"Compaction\"\n", "This is the straightforward version with no \"compaction\".\n", "It works fine, but does waaaay too much work because the\n", "expressions grow each derivation." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "def D(symbol):\n", "\n", " def derv(R):\n", "\n", " # ∂a(a) → λ\n", " if R == {symbol}:\n", " return y\n", "\n", " # ∂a(λ) → ϕ\n", " # ∂a(ϕ) → ϕ\n", " # ∂a(¬a) → ϕ\n", " if R == y or R == phi or R in syms:\n", " return phi\n", " \n", " tag = R[0]\n", "\n", " # ∂a(R*) → ∂a(R)∘R*\n", " if tag == KSTAR:\n", " return (CONS, derv(R[1]), R)\n", "\n", " # ∂a(¬R) → ¬∂a(R)\n", " if tag == NOT:\n", " return (NOT, derv(R[1]))\n", "\n", " r, s = R[1:]\n", "\n", " # ∂a(R∘S) → ∂a(R)∘S ∨ δ(R)∘∂a(S)\n", " if tag == CONS:\n", " A = (CONS, derv(r), s) # A = ∂a(R)∘S\n", " # A ∨ δ(R) ∘ ∂a(S)\n", " # A ∨ λ ∘ ∂a(S) → A ∨ ∂a(S)\n", " # A ∨ ϕ ∘ ∂a(S) → A ∨ ϕ → A\n", " return (OR, A, derv(s)) if nully(r) else A\n", "\n", " # ∂a(R ∧ S) → ∂a(R) ∧ ∂a(S)\n", " # ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)\n", " return (tag, derv(r), derv(s))\n", "\n", " return derv" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Compaction Rules" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "def _compaction_rule(relation, one, zero, a, b):\n", " return (\n", " b if a == one else # R*1 = 1*R = R\n", " a if b == one else\n", " zero if a == zero or b == zero else # R*0 = 0*R = 0\n", " (relation, a, b)\n", " )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "An elegant symmetry." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "# R ∧ I = I ∧ R = R\n", "# R ∧ ϕ = ϕ ∧ R = ϕ\n", "_and = curry(_compaction_rule, AND, I, phi)\n", "\n", "# R ∨ ϕ = ϕ ∨ R = R\n", "# R ∨ I = I ∨ R = I\n", "_or = curry(_compaction_rule, OR, phi, I)\n", "\n", "# R∘λ = λ∘R = R\n", "# R∘ϕ = ϕ∘R = ϕ\n", "_cons = curry(_compaction_rule, CONS, y, phi)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Memoizing\n", "We can save re-processing by remembering results we have already computed. RE datastructures are immutable and the `derv()` functions are _pure_ so this is fine." ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "class Memo(object):\n", "\n", " def __init__(self, f):\n", " self.f = f\n", " self.calls = self.hits = 0\n", " self.mem = {}\n", "\n", " def __call__(self, key):\n", " self.calls += 1\n", " try:\n", " result = self.mem[key]\n", " self.hits += 1\n", " except KeyError:\n", " result = self.mem[key] = self.f(key)\n", " return result" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### With \"Compaction\"\n", "This version uses the rules above to perform compaction. It keeps the expressions from growing too large." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "def D_compaction(symbol):\n", "\n", " @Memo\n", " def derv(R):\n", "\n", " # ∂a(a) → λ\n", " if R == {symbol}:\n", " return y\n", "\n", " # ∂a(λ) → ϕ\n", " # ∂a(ϕ) → ϕ\n", " # ∂a(¬a) → ϕ\n", " if R == y or R == phi or R in syms:\n", " return phi\n", "\n", " tag = R[0]\n", "\n", " # ∂a(R*) → ∂a(R)∘R*\n", " if tag == KSTAR:\n", " return _cons(derv(R[1]), R)\n", "\n", " # ∂a(¬R) → ¬∂a(R)\n", " if tag == NOT:\n", " return (NOT, derv(R[1]))\n", "\n", " r, s = R[1:]\n", "\n", " # ∂a(R∘S) → ∂a(R)∘S ∨ δ(R)∘∂a(S)\n", " if tag == CONS:\n", " A = _cons(derv(r), s) # A = ∂a(r)∘s\n", " # A ∨ δ(R) ∘ ∂a(S)\n", " # A ∨ λ ∘ ∂a(S) → A ∨ ∂a(S)\n", " # A ∨ ϕ ∘ ∂a(S) → A ∨ ϕ → A\n", " return _or(A, derv(s)) if nully(r) else A\n", "\n", " # ∂a(R ∧ S) → ∂a(R) ∧ ∂a(S)\n", " # ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)\n", " dr, ds = derv(r), derv(s)\n", " return _and(dr, ds) if tag == AND else _or(dr, ds)\n", "\n", " return derv" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Let's try it out...\n", "(FIXME: redo.)" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(.111.) & ((.01 | 11*)')\n", "\n", "92 / 122\n", "92 / 122\n", "\n", "(.01)'\n", "(.01 | 1)'\n", "(.01 | ^)'\n", "(.01 | 1*)'\n", "(.111.) & ((.01 | 1)')\n", "(.111. | 11.) & ((.01 | ^)')\n", "(.111. | 11. | 1.) & ((.01)')\n", "(.111. | 11.) & ((.01 | 1*)')\n", "(.111. | 11. | 1.) & ((.01 | 1*)')\n" ] } ], "source": [ "o, z = D_compaction('0'), D_compaction('1')\n", "REs = set()\n", "N = 5\n", "names = list(product(*(N * [(0, 1)])))\n", "dervs = list(product(*(N * [(o, z)])))\n", "for name, ds in zip(names, dervs):\n", " R = it\n", " ds = list(ds)\n", " while ds:\n", " R = ds.pop()(R)\n", " if R == phi or R == I:\n", " break\n", " REs.add(R)\n", "\n", "print stringy(it) ; print\n", "print o.hits, '/', o.calls\n", "print z.hits, '/', z.calls\n", "print\n", "for s in sorted(map(stringy, REs), key=lambda n: (len(n), n)):\n", " print s" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Should match:\n", "\n", " (.111.) & ((.01 | 11*)')\n", " \n", " 92 / 122\n", " 92 / 122\n", " \n", " (.01 )'\n", " (.01 | 1 )'\n", " (.01 | ^ )'\n", " (.01 | 1*)'\n", " (.111.) & ((.01 | 1 )')\n", " (.111. | 11.) & ((.01 | ^ )')\n", " (.111. | 11.) & ((.01 | 1*)')\n", " (.111. | 11. | 1.) & ((.01 )')\n", " (.111. | 11. | 1.) & ((.01 | 1*)')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Larger Alphabets\n", "\n", "We could parse larger alphabets by defining patterns for e.g. each byte of the ASCII code. Or we can generalize this code. If you study the code above you'll see that we never use the \"set-ness\" of the symbols `O` and `l`. The only time Python set operators (`&` and `|`) appear is in the `nully()` function, and there they operate on (recursively computed) outputs of that function, never `O` and `l`.\n", "\n", "\n", "What if we try:\n", "\n", " (OR, O, l)\n", "\n", " ∂1((OR, O, l))\n", " ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)\n", " ∂1(O) ∨ ∂1(l)\n", " ∂a(¬a) → ϕ\n", " ϕ ∨ ∂1(l)\n", " ∂a(a) → λ\n", " ϕ ∨ λ\n", " ϕ ∨ R = R\n", " λ\n", "\n", "And compare it to:\n", "\n", " {'0', '1')\n", " \n", " ∂1({'0', '1'))\n", " ∂a(R ∨ S) → ∂a(R) ∨ ∂a(S)\n", " ∂1({'0')) ∨ ∂1({'1'))\n", " ∂a(¬a) → ϕ\n", " ϕ ∨ ∂1({'1'))\n", " ∂a(a) → λ\n", " ϕ ∨ λ\n", " ϕ ∨ R = R\n", " λ\n", "\n", "This suggests that we should be able to alter the functions above to detect sets and deal with them appropriately. Exercise for the Reader for now." ] }, { "attachments": { "omg.svg": { "image/svg+xml": [ "PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0iVVRGLTgiIHN0YW5kYWxvbmU9Im5vIj8+CjwhRE9DVFlQRSBzdmcgUFVCTElDICItLy9XM0MvL0RURCBTVkcgMS4xLy9FTiIKICJodHRwOi8vd3d3LnczLm9yZy9HcmFwaGljcy9TVkcvMS4xL0RURC9zdmcxMS5kdGQiPgo8IS0tIEdlbmVyYXRlZCBieSBncmFwaHZpeiB2ZXJzaW9uIDIuMzguMCAoMjAxNDA0MTMuMjA0MSkKIC0tPgo8IS0tIFRpdGxlOiBmaW5pdGVfc3RhdGVfbWFjaGluZSBQYWdlczogMSAtLT4KPHN2ZyB3aWR0aD0iNTM0cHQiIGhlaWdodD0iMjcwcHQiCiB2aWV3Qm94PSIwLjAwIDAuMDAgNTM0LjAwIDI3MC4wMCIgeG1sbnM9Imh0dHA6Ly93d3cudzMub3JnLzIwMDAvc3ZnIiB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGluayI+CjxnIGlkPSJncmFwaDAiIGNsYXNzPSJncmFwaCIgdHJhbnNmb3JtPSJzY2FsZSgxIDEpIHJvdGF0ZSgwKSB0cmFuc2xhdGUoNCAyNjYpIj4KPHRpdGxlPmZpbml0ZV9zdGF0ZV9tYWNoaW5lPC90aXRsZT4KPHBvbHlnb24gZmlsbD0id2hpdGUiIHN0cm9rZT0ibm9uZSIgcG9pbnRzPSItNCw0IC00LC0yNjYgNTMwLC0yNjYgNTMwLDQgLTQsNCIvPgo8IS0tIGkgLS0+CjxnIGlkPSJub2RlMSIgY2xhc3M9Im5vZGUiPjx0aXRsZT5pPC90aXRsZT4KPGVsbGlwc2UgZmlsbD0ibm9uZSIgc3Ryb2tlPSJibGFjayIgY3g9IjMzOCIgY3k9Ii0xNDYiIHJ4PSIxOCIgcnk9IjE4Ii8+CjxlbGxpcHNlIGZpbGw9Im5vbmUiIHN0cm9rZT0iYmxhY2siIGN4PSIzMzgiIGN5PSItMTQ2IiByeD0iMjIiIHJ5PSIyMiIvPgo8dGV4dCB0ZXh0LWFuY2hvcj0ibWlkZGxlIiB4PSIzMzgiIHk9Ii0xNDIuMyIgZm9udC1mYW1pbHk9IlRpbWVzLHNlcmlmIiBmb250LXNpemU9IjE0LjAwIj5pPC90ZXh0Pgo8L2c+CjwhLS0gaSYjNDU7Jmd0O2kgLS0+CjxnIGlkPSJlZGdlMTciIGNsYXNzPSJlZGdlIj48dGl0bGU+aSYjNDU7Jmd0O2k8L3RpdGxlPgo8cGF0aCBmaWxsPSJub25lIiBzdHJva2U9ImJsYWNrIiBkPSJNMzMwLjMxNywtMTY2Ljk5MUMzMjkuMzY5LC0xNzcuMDg3IDMzMS45MywtMTg2IDMzOCwtMTg2IDM0MS44ODksLTE4NiAzNDQuMzM3LC0xODIuMzQyIDM0NS4zNDYsLTE3Ny4wNTkiLz4KPHBvbHlnb24gZmlsbD0iYmxhY2siIHN0cm9rZT0iYmxhY2siIHBvaW50cz0iMzQ4Ljg0NiwtMTc3LjEwMiAzNDUuNjgzLC0xNjYuOTkxIDM0MS44NSwtMTc2Ljg2OCAzNDguODQ2LC0xNzcuMTAyIi8+Cjx0ZXh0IHRleHQtYW5jaG9yPSJtaWRkbGUiIHg9IjMzOCIgeT0iLTE4OS44IiBmb250LWZhbWlseT0iVGltZXMsc2VyaWYiIGZvbnQtc2l6ZT0iMTQuMDAiPjA8L3RleHQ+CjwvZz4KPCEtLSBqIC0tPgo8ZyBpZD0ibm9kZTEwIiBjbGFzcz0ibm9kZSI+PHRpdGxlPmo8L3RpdGxlPgo8ZWxsaXBzZSBmaWxsPSJub25lIiBzdHJva2U9ImJsYWNrIiBjeD0iNDIxIiBjeT0iLTEzNiIgcng9IjE4IiByeT0iMTgiLz4KPHRleHQgdGV4dC1hbmNob3I9Im1pZGRsZSIgeD0iNDIxIiB5PSItMTMyLjMiIGZvbnQtZmFtaWx5PSJUaW1lcyxzZXJpZiIgZm9udC1zaXplPSIxNC4wMCI+ajwvdGV4dD4KPC9nPgo8IS0tIGkmIzQ1OyZndDtqIC0tPgo8ZyBpZD0iZWRnZTE4IiBjbGFzcz0iZWRnZSI+PHRpdGxlPmkmIzQ1OyZndDtqPC90aXRsZT4KPHBhdGggZmlsbD0ibm9uZSIgc3Ryb2tlPSJibGFjayIgZD0iTTM1Ny40NjYsLTEzNS40OTVDMzYzLjc3NSwtMTMyLjQ1MSAzNzEuMDA4LC0xMjkuNTM2IDM3OCwtMTI4IDM4My4yMTMsLTEyNi44NTUgMzg4LjgxMSwtMTI2Ljk4NCAzOTQuMTY3LC0xMjcuNzYzIi8+Cjxwb2x5Z29uIGZpbGw9ImJsYWNrIiBzdHJva2U9ImJsYWNrIiBwb2ludHM9IjM5My40ODcsLTEzMS4xOTcgNDA0LjAwMiwtMTI5Ljg5NCAzOTQuOTcsLTEyNC4zNTUgMzkzLjQ4NywtMTMxLjE5NyIvPgo8dGV4dCB0ZXh0LWFuY2hvcj0ibWlkZGxlIiB4PSIzODEuNSIgeT0iLTEzMS44IiBmb250LWZhbWlseT0iVGltZXMsc2VyaWYiIGZvbnQtc2l6ZT0iMTQuMDAiPjE8L3RleHQ+CjwvZz4KPCEtLSBoIC0tPgo8ZyBpZD0ibm9kZTIiIGNsYXNzPSJub2RlIj48dGl0bGU+aDwvdGl0bGU+CjxlbGxpcHNlIGZpbGw9Im5vbmUiIHN0cm9rZT0iYmxhY2siIGN4PSI1MDQiIGN5PSItODUiIHJ4PSIxOCIgcnk9IjE4Ii8+CjxlbGxpcHNlIGZpbGw9Im5vbmUiIHN0cm9rZT0iYmxhY2siIGN4PSI1MDQiIGN5PSItODUiIHJ4PSIyMiIgcnk9IjIyIi8+Cjx0ZXh0IHRleHQtYW5jaG9yPSJtaWRkbGUiIHg9IjUwNCIgeT0iLTgxLjMiIGZvbnQtZmFtaWx5PSJUaW1lcyxzZXJpZiIgZm9udC1zaXplPSIxNC4wMCI+aDwvdGV4dD4KPC9nPgo8IS0tIGgmIzQ1OyZndDtpIC0tPgo8ZyBpZD0iZWRnZTE1IiBjbGFzcz0iZWRnZSI+PHRpdGxlPmgmIzQ1OyZndDtpPC90aXRsZT4KPHBhdGggZmlsbD0ibm9uZSIgc3Ryb2tlPSJibGFjayIgZD0iTTQ4MS44NjgsLTgzLjQwMjVDNDYxLjAzMywtODIuNjIgNDI4LjY3NiwtODMuNTY0NSA0MDMsLTk0IDM4Ny4yNjcsLTEwMC4zOTQgMzcyLjM3MywtMTEyLjAyOCAzNjAuOTE4LC0xMjIuNjczIi8+Cjxwb2x5Z29uIGZpbGw9ImJsYWNrIiBzdHJva2U9ImJsYWNrIiBwb2ludHM9IjM1OC4zMDYsLTEyMC4zMyAzNTMuNTY5LC0xMjkuODA3IDM2My4xODIsLTEyNS4zNTMgMzU4LjMwNiwtMTIwLjMzIi8+Cjx0ZXh0IHRleHQtYW5jaG9yPSJtaWRkbGUiIHg9IjQyMSIgeT0iLTk3LjgiIGZvbnQtZmFtaWx5PSJUaW1lcyxzZXJpZiIgZm9udC1zaXplPSIxNC4wMCI+MDwvdGV4dD4KPC9nPgo8IS0tIGgmIzQ1OyZndDtoIC0tPgo8ZyBpZD0iZWRnZTE2IiBjbGFzcz0iZWRnZSI+PHRpdGxlPmgmIzQ1OyZndDtoPC90aXRsZT4KPHBhdGggZmlsbD0ibm9uZSIgc3Ryb2tlPSJibGFjayIgZD0iTTQ5Ni4zMTcsLTEwNS45OTFDNDk1LjM2OSwtMTE2LjA4NyA0OTcuOTMsLTEyNSA1MDQsLTEyNSA1MDcuODg5LC0xMjUgNTEwLjMzNywtMTIxLjM0MiA1MTEuMzQ2LC0xMTYuMDU5Ii8+Cjxwb2x5Z29uIGZpbGw9ImJsYWNrIiBzdHJva2U9ImJsYWNrIiBwb2ludHM9IjUxNC44NDYsLTExNi4xMDIgNTExLjY4MywtMTA1Ljk5MSA1MDcuODUsLTExNS44NjggNTE0Ljg0NiwtMTE2LjEwMiIvPgo8dGV4dCB0ZXh0LWFuY2hvcj0ibWlkZGxlIiB4PSI1MDQiIHk9Ii0xMjguOCIgZm9udC1mYW1pbHk9IlRpbWVzLHNlcmlmIiBmb250LXNpemU9IjE0LjAwIj4xPC90ZXh0Pgo8L2c+CjwhLS0gYSAtLT4KPGcgaWQ9Im5vZGUzIiBjbGFzcz0ibm9kZSI+PHRpdGxlPmE8L3RpdGxlPgo8ZWxsaXBzZSBmaWxsPSJub25lIiBzdHJva2U9ImJsYWNrIiBjeD0iMTgiIGN5PSItMTI4IiByeD0iMTgiIHJ5PSIxOCIvPgo8dGV4dCB0ZXh0LWFuY2hvcj0ibWlkZGxlIiB4PSIxOCIgeT0iLTEyNC4zIiBmb250LWZhbWlseT0iVGltZXMsc2VyaWYiIGZvbnQtc2l6ZT0iMTQuMDAiPmE8L3RleHQ+CjwvZz4KPCEtLSBiIC0tPgo8ZyBpZD0ibm9kZTQiIGNsYXNzPSJub2RlIj48dGl0bGU+YjwvdGl0bGU+CjxlbGxpcHNlIGZpbGw9Im5vbmUiIHN0cm9rZT0iYmxhY2siIGN4PSIyNTUiIGN5PSItMTEzIiByeD0iMTgiIHJ5PSIxOCIvPgo8dGV4dCB0ZXh0LWFuY2hvcj0ibWlkZGxlIiB4PSIyNTUiIHk9Ii0xMDkuMyIgZm9udC1mYW1pbHk9IlRpbWVzLHNlcmlmIiBmb250LXNpemU9IjE0LjAwIj5iPC90ZXh0Pgo8L2c+CjwhLS0gYSYjNDU7Jmd0O2IgLS0+CjxnIGlkPSJlZGdlMSIgY2xhc3M9ImVkZ2UiPjx0aXRsZT5hJiM0NTsmZ3Q7YjwvdGl0bGU+CjxwYXRoIGZpbGw9Im5vbmUiIHN0cm9rZT0iYmxhY2siIGQ9Ik0zNi4yODAxLC0xMjYuODk3Qzc2Ljc4MTYsLTEyNC4zMTIgMTc4LjA5MSwtMTE3Ljg0NSAyMjYuODksLTExNC43MyIvPgo8cG9seWdvbiBmaWxsPSJibGFjayIgc3Ryb2tlPSJibGFjayIgcG9pbnRzPSIyMjcuMjU1LC0xMTguMjE0IDIzNy4wMTEsLTExNC4wODQgMjI2LjgwOSwtMTExLjIyOSAyMjcuMjU1LC0xMTguMjE0Ii8+Cjx0ZXh0IHRleHQtYW5jaG9yPSJtaWRkbGUiIHg9IjEzNi41IiB5PSItMTIzLjgiIGZvbnQtZmFtaWx5PSJUaW1lcyxzZXJpZiIgZm9udC1zaXplPSIxNC4wMCI+MDwvdGV4dD4KPC9nPgo8IS0tIGMgLS0+CjxnIGlkPSJub2RlNSIgY2xhc3M9Im5vZGUiPjx0aXRsZT5jPC90aXRsZT4KPGVsbGlwc2UgZmlsbD0ibm9uZSIgc3Ryb2tlPSJibGFjayIgY3g9Ijk3IiBjeT0iLTE1NSIgcng9IjE4IiByeT0iMTgiLz4KPHRleHQgdGV4dC1hbmNob3I9Im1pZGRsZSIgeD0iOTciIHk9Ii0xNTEuMyIgZm9udC1mYW1pbHk9IlRpbWVzLHNlcmlmIiBmb250LXNpemU9IjE0LjAwIj5jPC90ZXh0Pgo8L2c+CjwhLS0gYSYjNDU7Jmd0O2MgLS0+CjxnIGlkPSJlZGdlMiIgY2xhc3M9ImVkZ2UiPjx0aXRsZT5hJiM0NTsmZ3Q7YzwvdGl0bGU+CjxwYXRoIGZpbGw9Im5vbmUiIHN0cm9rZT0iYmxhY2siIGQ9Ik0zNS4zMjk3LC0xMzMuNzI2QzQ1LjQzNjQsLTEzNy4yNyA1OC42MzUsLTE0MS44OTggNzAuMTM5OCwtMTQ1LjkzMiIvPgo8cG9seWdvbiBmaWxsPSJibGFjayIgc3Ryb2tlPSJibGFjayIgcG9pbnRzPSI2OS4wOTksLTE0OS4yNzYgNzkuNjkzOCwtMTQ5LjI4MiA3MS40MTUzLC0xNDIuNjcgNjkuMDk5LC0xNDkuMjc2Ii8+Cjx0ZXh0IHRleHQtYW5jaG9yPSJtaWRkbGUiIHg9IjU3LjUiIHk9Ii0xNDUuOCIgZm9udC1mYW1pbHk9IlRpbWVzLHNlcmlmIiBmb250LXNpemU9IjE0LjAwIj4xPC90ZXh0Pgo8L2c+CjwhLS0gYiYjNDU7Jmd0O2IgLS0+CjxnIGlkPSJlZGdlMyIgY2xhc3M9ImVkZ2UiPjx0aXRsZT5iJiM0NTsmZ3Q7YjwvdGl0bGU+CjxwYXRoIGZpbGw9Im5vbmUiIHN0cm9rZT0iYmxhY2siIGQ9Ik0yNDguMjY2LC0xMzAuMDM3QzI0Ni44OTIsLTEzOS44NTggMjQ5LjEzNywtMTQ5IDI1NSwtMTQ5IDI1OC42NjUsLTE0OSAyNjAuOTE2LC0xNDUuNDI5IDI2MS43NTMsLTE0MC4zNTMiLz4KPHBvbHlnb24gZmlsbD0iYmxhY2siIHN0cm9rZT0iYmxhY2siIHBvaW50cz0iMjY1LjI1MiwtMTQwLjAzMSAyNjEuNzM0LC0xMzAuMDM3IDI1OC4yNTIsLTE0MC4wNDQgMjY1LjI1MiwtMTQwLjAzMSIvPgo8dGV4dCB0ZXh0LWFuY2hvcj0ibWlkZGxlIiB4PSIyNTUiIHk9Ii0xNTIuOCIgZm9udC1mYW1pbHk9IlRpbWVzLHNlcmlmIiBmb250LXNpemU9IjE0LjAwIj4wPC90ZXh0Pgo8L2c+CjwhLS0gZCAtLT4KPGcgaWQ9Im5vZGU2IiBjbGFzcz0ibm9kZSI+PHRpdGxlPmQ8L3RpdGxlPgo8ZWxsaXBzZSBmaWxsPSJub25lIiBzdHJva2U9ImJsYWNrIiBjeD0iMzM4IiBjeT0iLTc5IiByeD0iMTgiIHJ5PSIxOCIvPgo8dGV4dCB0ZXh0LWFuY2hvcj0ibWlkZGxlIiB4PSIzMzgiIHk9Ii03NS4zIiBmb250LWZhbWlseT0iVGltZXMsc2VyaWYiIGZvbnQtc2l6ZT0iMTQuMDAiPmQ8L3RleHQ+CjwvZz4KPCEtLSBiJiM0NTsmZ3Q7ZCAtLT4KPGcgaWQ9ImVkZ2U0IiBjbGFzcz0iZWRnZSI+PHRpdGxlPmImIzQ1OyZndDtkPC90aXRsZT4KPHBhdGggZmlsbD0ibm9uZSIgc3Ryb2tlPSJibGFjayIgZD0iTTI3Mi4wMDMsLTEwNi4yODNDMjgzLjMxOSwtMTAxLjUzMyAyOTguNzIyLC05NS4wNjc0IDMxMS42OTMsLTg5LjYyMjciLz4KPHBvbHlnb24gZmlsbD0iYmxhY2siIHN0cm9rZT0iYmxhY2siIHBvaW50cz0iMzEzLjE2NCwtOTIuODAxIDMyMS4wMywtODUuNzAzNCAzMTAuNDU1LC04Ni4zNDY2IDMxMy4xNjQsLTkyLjgwMSIvPgo8dGV4dCB0ZXh0LWFuY2hvcj0ibWlkZGxlIiB4PSIyOTQuNSIgeT0iLTEwMS44IiBmb250LWZhbWlseT0iVGltZXMsc2VyaWYiIGZvbnQtc2l6ZT0iMTQuMDAiPjE8L3RleHQ+CjwvZz4KPCEtLSBjJiM0NTsmZ3Q7YiAtLT4KPGcgaWQ9ImVkZ2U1IiBjbGFzcz0iZWRnZSI+PHRpdGxlPmMmIzQ1OyZndDtiPC90aXRsZT4KPHBhdGggZmlsbD0ibm9uZSIgc3Ryb2tlPSJibGFjayIgZD0iTTExNC44NjIsLTE1MC42NTNDMTM4LjI2OSwtMTQ0LjU5MyAxODEuOTE3LC0xMzMuMiAyMTksLTEyMyAyMjEuNzk5LC0xMjIuMjMgMjI0LjcyMSwtMTIxLjQxNCAyMjcuNjMxLC0xMjAuNTk0Ii8+Cjxwb2x5Z29uIGZpbGw9ImJsYWNrIiBzdHJva2U9ImJsYWNrIiBwb2ludHM9IjIyOC42MjMsLTEyMy45NTEgMjM3LjI4NCwtMTE3Ljg0OSAyMjYuNzA4LC0xMTcuMjE4IDIyOC42MjMsLTEyMy45NTEiLz4KPHRleHQgdGV4dC1hbmNob3I9Im1pZGRsZSIgeD0iMTc2IiB5PSItMTQyLjgiIGZvbnQtZmFtaWx5PSJUaW1lcyxzZXJpZiIgZm9udC1zaXplPSIxNC4wMCI+MDwvdGV4dD4KPC9nPgo8IS0tIGUgLS0+CjxnIGlkPSJub2RlNyIgY2xhc3M9Im5vZGUiPjx0aXRsZT5lPC90aXRsZT4KPGVsbGlwc2UgZmlsbD0ibm9uZSIgc3Ryb2tlPSJibGFjayIgY3g9IjE3NiIgY3k9Ii0yMDYiIHJ4PSIxOCIgcnk9IjE4Ii8+Cjx0ZXh0IHRleHQtYW5jaG9yPSJtaWRkbGUiIHg9IjE3NiIgeT0iLTIwMi4zIiBmb250LWZhbWlseT0iVGltZXMsc2VyaWYiIGZvbnQtc2l6ZT0iMTQuMDAiPmU8L3RleHQ+CjwvZz4KPCEtLSBjJiM0NTsmZ3Q7ZSAtLT4KPGcgaWQ9ImVkZ2U2IiBjbGFzcz0iZWRnZSI+PHRpdGxlPmMmIzQ1OyZndDtlPC90aXRsZT4KPHBhdGggZmlsbD0ibm9uZSIgc3Ryb2tlPSJibGFjayIgZD0iTTExMi40ODMsLTE2NC41OTNDMTIzLjY2OCwtMTcyLjAwMSAxMzkuMzU2LC0xODIuMzkyIDE1Mi4yMTksLTE5MC45MTEiLz4KPHBvbHlnb24gZmlsbD0iYmxhY2siIHN0cm9rZT0iYmxhY2siIHBvaW50cz0iMTUwLjMxMiwtMTkzLjg0NiAxNjAuNTgyLC0xOTYuNDUgMTU0LjE3NywtMTg4LjAxIDE1MC4zMTIsLTE5My44NDYiLz4KPHRleHQgdGV4dC1hbmNob3I9Im1pZGRsZSIgeD0iMTM2LjUiIHk9Ii0xODUuOCIgZm9udC1mYW1pbHk9IlRpbWVzLHNlcmlmIiBmb250LXNpemU9IjE0LjAwIj4xPC90ZXh0Pgo8L2c+CjwhLS0gZCYjNDU7Jmd0O2IgLS0+CjxnIGlkPSJlZGdlNyIgY2xhc3M9ImVkZ2UiPjx0aXRsZT5kJiM0NTsmZ3Q7YjwvdGl0bGU+CjxwYXRoIGZpbGw9Im5vbmUiIHN0cm9rZT0iYmxhY2siIGQ9Ik0zMjAuMjA1LC03NC44NzYzQzMxMS4yMDgsLTczLjQ5MTEgMzAwLjEzMSwtNzMuMTQyNCAyOTEsLTc3IDI4NC4wOTQsLTc5LjkxNzUgMjc3Ljg3OSwtODQuOTM3NiAyNzIuNjY5LC05MC4zMTgzIi8+Cjxwb2x5Z29uIGZpbGw9ImJsYWNrIiBzdHJva2U9ImJsYWNrIiBwb2ludHM9IjI2OS42OTQsLTg4LjQwNjcgMjY1Ljc5MSwtOTguMjU2OCAyNzQuOTg1LC05Mi45OTAyIDI2OS42OTQsLTg4LjQwNjciLz4KPHRleHQgdGV4dC1hbmNob3I9Im1pZGRsZSIgeD0iMjk0LjUiIHk9Ii04MC44IiBmb250LWZhbWlseT0iVGltZXMsc2VyaWYiIGZvbnQtc2l6ZT0iMTQuMDAiPjA8L3RleHQ+CjwvZz4KPCEtLSBmIC0tPgo8ZyBpZD0ibm9kZTgiIGNsYXNzPSJub2RlIj48dGl0bGU+ZjwvdGl0bGU+CjxlbGxpcHNlIGZpbGw9Im5vbmUiIHN0cm9rZT0iYmxhY2siIGN4PSIxNzYiIGN5PSItNDYiIHJ4PSIxOCIgcnk9IjE4Ii8+Cjx0ZXh0IHRleHQtYW5jaG9yPSJtaWRkbGUiIHg9IjE3NiIgeT0iLTQyLjMiIGZvbnQtZmFtaWx5PSJUaW1lcyxzZXJpZiIgZm9udC1zaXplPSIxNC4wMCI+ZjwvdGV4dD4KPC9nPgo8IS0tIGQmIzQ1OyZndDtmIC0tPgo8ZyBpZD0iZWRnZTgiIGNsYXNzPSJlZGdlIj48dGl0bGU+ZCYjNDU7Jmd0O2Y8L3RpdGxlPgo8cGF0aCBmaWxsPSJub25lIiBzdHJva2U9ImJsYWNrIiBkPSJNMzE5LjkyMywtNzUuNDc4QzI5Mi4wOTgsLTY5LjczODkgMjM2Ljc2OCwtNTguMzI3MSAyMDMuNzA4LC01MS41MDg2Ii8+Cjxwb2x5Z29uIGZpbGw9ImJsYWNrIiBzdHJva2U9ImJsYWNrIiBwb2ludHM9IjIwNC4zMjEsLTQ4LjA2MTQgMTkzLjgyLC00OS40NjkyIDIwMi45MDcsLTU0LjkxNzEgMjA0LjMyMSwtNDguMDYxNCIvPgo8dGV4dCB0ZXh0LWFuY2hvcj0ibWlkZGxlIiB4PSIyNTUiIHk9Ii02OS44IiBmb250LWZhbWlseT0iVGltZXMsc2VyaWYiIGZvbnQtc2l6ZT0iMTQuMDAiPjE8L3RleHQ+CjwvZz4KPCEtLSBlJiM0NTsmZ3Q7YiAtLT4KPGcgaWQ9ImVkZ2U5IiBjbGFzcz0iZWRnZSI+PHRpdGxlPmUmIzQ1OyZndDtiPC90aXRsZT4KPHBhdGggZmlsbD0ibm9uZSIgc3Ryb2tlPSJibGFjayIgZD0iTTE5MC4yNDEsLTE5NC43OTZDMTk4LjkwOCwtMTg3LjEzNiAyMTAuMjEyLC0xNzYuNTAzIDIxOSwtMTY2IDIyNi41MDcsLTE1Ny4wMjggMjMzLjgwMywtMTQ2LjM4OSAyMzkuNzc0LC0xMzcuMDA3Ii8+Cjxwb2x5Z29uIGZpbGw9ImJsYWNrIiBzdHJva2U9ImJsYWNrIiBwb2ludHM9IjI0Mi43NTksLTEzOC44MzQgMjQ1LjA1NiwtMTI4LjQ5MSAyMzYuODEsLTEzNS4xNDQgMjQyLjc1OSwtMTM4LjgzNCIvPgo8dGV4dCB0ZXh0LWFuY2hvcj0ibWlkZGxlIiB4PSIyMTUuNSIgeT0iLTE3Ni44IiBmb250LWZhbWlseT0iVGltZXMsc2VyaWYiIGZvbnQtc2l6ZT0iMTQuMDAiPjA8L3RleHQ+CjwvZz4KPCEtLSBnIC0tPgo8ZyBpZD0ibm9kZTkiIGNsYXNzPSJub2RlIj48dGl0bGU+ZzwvdGl0bGU+CjxlbGxpcHNlIGZpbGw9Im5vbmUiIHN0cm9rZT0iYmxhY2siIGN4PSIyNTUiIGN5PSItMjExIiByeD0iMTgiIHJ5PSIxOCIvPgo8dGV4dCB0ZXh0LWFuY2hvcj0ibWlkZGxlIiB4PSIyNTUiIHk9Ii0yMDcuMyIgZm9udC1mYW1pbHk9IlRpbWVzLHNlcmlmIiBmb250LXNpemU9IjE0LjAwIj5nPC90ZXh0Pgo8L2c+CjwhLS0gZSYjNDU7Jmd0O2cgLS0+CjxnIGlkPSJlZGdlMTAiIGNsYXNzPSJlZGdlIj48dGl0bGU+ZSYjNDU7Jmd0O2c8L3RpdGxlPgo8cGF0aCBmaWxsPSJub25lIiBzdHJva2U9ImJsYWNrIiBkPSJNMTk0LjA4OSwtMjA3LjExQzIwMy42NTksLTIwNy43MzEgMjE1LjgxNywtMjA4LjUyMSAyMjYuNjc3LC0yMDkuMjI2Ii8+Cjxwb2x5Z29uIGZpbGw9ImJsYWNrIiBzdHJva2U9ImJsYWNrIiBwb2ludHM9IjIyNi43NTMsLTIxMi43MzggMjM2Ljk1OSwtMjA5Ljg5MyAyMjcuMjA3LC0yMDUuNzUzIDIyNi43NTMsLTIxMi43MzgiLz4KPHRleHQgdGV4dC1hbmNob3I9Im1pZGRsZSIgeD0iMjE1LjUiIHk9Ii0yMTEuOCIgZm9udC1mYW1pbHk9IlRpbWVzLHNlcmlmIiBmb250LXNpemU9IjE0LjAwIj4xPC90ZXh0Pgo8L2c+CjwhLS0gZiYjNDU7Jmd0O2ggLS0+CjxnIGlkPSJlZGdlMTIiIGNsYXNzPSJlZGdlIj48dGl0bGU+ZiYjNDU7Jmd0O2g8L3RpdGxlPgo8cGF0aCBmaWxsPSJub25lIiBzdHJva2U9ImJsYWNrIiBkPSJNMTg5LjAyLC0zMy4xODY0QzIwMy4xNTEsLTE5LjU3NTQgMjI3Ljk5NSwtMCAyNTQsLTAgMjU0LC0wIDI1NCwtMCA0MjIsLTAgNDUzLjYzMiwtMCA0NzYuNjc3LC0zMS4yMzExIDQ4OS45MjQsLTU1LjgzMTQiLz4KPHBvbHlnb24gZmlsbD0iYmxhY2siIHN0cm9rZT0iYmxhY2siIHBvaW50cz0iNDg2Ljg2MiwtNTcuNTMyNSA0OTQuNTE4LC02NC44NTYyIDQ5My4xLC01NC4zNTY2IDQ4Ni44NjIsLTU3LjUzMjUiLz4KPHRleHQgdGV4dC1hbmNob3I9Im1pZGRsZSIgeD0iMzM4IiB5PSItMy44IiBmb250LWZhbWlseT0iVGltZXMsc2VyaWYiIGZvbnQtc2l6ZT0iMTQuMDAiPjE8L3RleHQ+CjwvZz4KPCEtLSBmJiM0NTsmZ3Q7YiAtLT4KPGcgaWQ9ImVkZ2UxMSIgY2xhc3M9ImVkZ2UiPjx0aXRsZT5mJiM0NTsmZ3Q7YjwvdGl0bGU+CjxwYXRoIGZpbGw9Im5vbmUiIHN0cm9rZT0iYmxhY2siIGQ9Ik0xOTAuODM0LC01Ni43Njg5QzE5OS4xMywtNjMuMzMxOSAyMDkuODE3LC03MS45NzQyIDIxOSwtODAgMjI0LjAzNCwtODQuNDAwMSAyMjkuMzQzLC04OS4yNzU3IDIzNC4yNjIsLTkzLjg5OSIvPgo8cG9seWdvbiBmaWxsPSJibGFjayIgc3Ryb2tlPSJibGFjayIgcG9pbnRzPSIyMzEuOTE3LC05Ni40OTg1IDI0MS41NzYsLTEwMC44NTIgMjM2Ljc0LC05MS40MjUyIDIzMS45MTcsLTk2LjQ5ODUiLz4KPHRleHQgdGV4dC1hbmNob3I9Im1pZGRsZSIgeD0iMjE1LjUiIHk9Ii04My44IiBmb250LWZhbWlseT0iVGltZXMsc2VyaWYiIGZvbnQtc2l6ZT0iMTQuMDAiPjA8L3RleHQ+CjwvZz4KPCEtLSBnJiM0NTsmZ3Q7aSAtLT4KPGcgaWQ9ImVkZ2UxMyIgY2xhc3M9ImVkZ2UiPjx0aXRsZT5nJiM0NTsmZ3Q7aTwvdGl0bGU+CjxwYXRoIGZpbGw9Im5vbmUiIHN0cm9rZT0iYmxhY2siIGQ9Ik0yNjkuNzQxLC0xOTkuOTc0QzI4MS40MzcsLTE5MC41ODcgMjk4LjUyNCwtMTc2Ljg3NiAzMTIuNTQ4LC0xNjUuNjIyIi8+Cjxwb2x5Z29uIGZpbGw9ImJsYWNrIiBzdHJva2U9ImJsYWNrIiBwb2ludHM9IjMxNC43NzgsLTE2OC4zMiAzMjAuMzg3LC0xNTkuMzMxIDMxMC4zOTcsLTE2Mi44NiAzMTQuNzc4LC0xNjguMzIiLz4KPHRleHQgdGV4dC1hbmNob3I9Im1pZGRsZSIgeD0iMjk0LjUiIHk9Ii0xODUuOCIgZm9udC1mYW1pbHk9IlRpbWVzLHNlcmlmIiBmb250LXNpemU9IjE0LjAwIj4wPC90ZXh0Pgo8L2c+CjwhLS0gZyYjNDU7Jmd0O2cgLS0+CjxnIGlkPSJlZGdlMTQiIGNsYXNzPSJlZGdlIj48dGl0bGU+ZyYjNDU7Jmd0O2c8L3RpdGxlPgo8cGF0aCBmaWxsPSJub25lIiBzdHJva2U9ImJsYWNrIiBkPSJNMjQ4LjI2NiwtMjI4LjAzN0MyNDYuODkyLC0yMzcuODU4IDI0OS4xMzcsLTI0NyAyNTUsLTI0NyAyNTguNjY1LC0yNDcgMjYwLjkxNiwtMjQzLjQyOSAyNjEuNzUzLC0yMzguMzUzIi8+Cjxwb2x5Z29uIGZpbGw9ImJsYWNrIiBzdHJva2U9ImJsYWNrIiBwb2ludHM9IjI2NS4yNTIsLTIzOC4wMzEgMjYxLjczNCwtMjI4LjAzNyAyNTguMjUyLC0yMzguMDQ0IDI2NS4yNTIsLTIzOC4wMzEiLz4KPHRleHQgdGV4dC1hbmNob3I9Im1pZGRsZSIgeD0iMjU1IiB5PSItMjUwLjgiIGZvbnQtZmFtaWx5PSJUaW1lcyxzZXJpZiIgZm9udC1zaXplPSIxNC4wMCI+MTwvdGV4dD4KPC9nPgo8IS0tIGomIzQ1OyZndDtpIC0tPgo8ZyBpZD0iZWRnZTE5IiBjbGFzcz0iZWRnZSI+PHRpdGxlPmomIzQ1OyZndDtpPC90aXRsZT4KPHBhdGggZmlsbD0ibm9uZSIgc3Ryb2tlPSJibGFjayIgZD0iTTQwMy4zNCwtMTM5LjhDMzk3LjU2MSwtMTQwLjk5MyAzOTEuMDIxLC0xNDIuMjA1IDM4NSwtMTQzIDM4MC4zMjEsLTE0My42MTggMzc1LjM1NywtMTQ0LjExIDM3MC40ODgsLTE0NC41MDIiLz4KPHBvbHlnb24gZmlsbD0iYmxhY2siIHN0cm9rZT0iYmxhY2siIHBvaW50cz0iMzY5Ljg2NCwtMTQxLjAzNiAzNjAuMTI2LC0xNDUuMjA5IDM3MC4zNDEsLTE0OC4wMiAzNjkuODY0LC0xNDEuMDM2Ii8+Cjx0ZXh0IHRleHQtYW5jaG9yPSJtaWRkbGUiIHg9IjM4MS41IiB5PSItMTQ2LjgiIGZvbnQtZmFtaWx5PSJUaW1lcyxzZXJpZiIgZm9udC1zaXplPSIxNC4wMCI+MDwvdGV4dD4KPC9nPgo8IS0tIGomIzQ1OyZndDtoIC0tPgo8ZyBpZD0iZWRnZTIwIiBjbGFzcz0iZWRnZSI+PHRpdGxlPmomIzQ1OyZndDtoPC90aXRsZT4KPHBhdGggZmlsbD0ibm9uZSIgc3Ryb2tlPSJibGFjayIgZD0iTTQzNi44NTcsLTEyNi42NDZDNDQ3Ljg0MSwtMTE5LjczIDQ2My4xLC0xMTAuMTIyIDQ3Ni4xOTQsLTEwMS44NzgiLz4KPHBvbHlnb24gZmlsbD0iYmxhY2siIHN0cm9rZT0iYmxhY2siIHBvaW50cz0iNDc4LjIzNywtMTA0LjcyNyA0ODQuODM1LC05Ni40Mzc1IDQ3NC41MDcsLTk4LjgwMzggNDc4LjIzNywtMTA0LjcyNyIvPgo8dGV4dCB0ZXh0LWFuY2hvcj0ibWlkZGxlIiB4PSI0NjAuNSIgeT0iLTExNi44IiBmb250LWZhbWlseT0iVGltZXMsc2VyaWYiIGZvbnQtc2l6ZT0iMTQuMDAiPjE8L3RleHQ+CjwvZz4KPC9nPgo8L3N2Zz4K" ] } }, "cell_type": "markdown", "metadata": {}, "source": [ "## State Machine\n", "We can drive the regular expressions to flesh out the underlying state machine transition table.\n", "\n", " .111. & (.01 + 11*)'\n", "\n", "Says, \"Three or more 1's and not ending in 01 nor composed of all 1's.\"\n", "\n", "![omg.svg](attachment:omg.svg)\n", "\n", "\n", "Start at `a` and follow the transition arrows according to their labels. Accepting states have a double outline. (Graphic generated with [Dot from Graphviz](http://www.graphviz.org/).) You'll see that only paths that lead to one of the accepting states will match the regular expression. All other paths will terminate at one of the non-accepting states.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There's a happy path to `g` along 111:\n", "\n", " a→c→e→g\n", "\n", "After you reach `g` you're stuck there eating 1's until you see a 0, which takes you to the `i→j→i|i→j→h→i` \"trap\". You can't reach any other states from those two loops.\n", "\n", "If you see a 0 before you see 111 you will reach `b`, which forms another \"trap\" with `d` and `f`. The only way out is another happy path along 111 to `h`:\n", "\n", " b→d→f→h\n", "\n", "Once you have reached `h` you can see as many 1's or as many 0' in a row and still be either still at `h` (for 1's) or move to `i` (for 0's). If you find yourself at `i` you can see as many 0's, or repetitions of 10, as there are, but if you see just a 1 you move to `j`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### RE to FSM\n", "So how do we get the state machine from the regular expression?\n", "\n", "It turns out that each RE is effectively a state, and each arrow points to the derivative RE in respect to the arrow's symbol.\n", "\n", "If we label the initial RE `a`, we can say:\n", "\n", " a --0--> ∂0(a)\n", " a --1--> ∂1(a)\n", "\n", "And so on, each new unique RE is a new state in the FSM table." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here are the derived REs at each state:\n", "\n", " a = (.111.) & ((.01 | 11*)')\n", " b = (.111.) & ((.01 | 1)')\n", " c = (.111. | 11.) & ((.01 | 1*)')\n", " d = (.111. | 11.) & ((.01 | ^)')\n", " e = (.111. | 11. | 1.) & ((.01 | 1*)')\n", " f = (.111. | 11. | 1.) & ((.01)')\n", " g = (.01 | 1*)'\n", " h = (.01)'\n", " i = (.01 | 1)'\n", " j = (.01 | ^)'\n", "\n", "You can see the one-way nature of the `g` state and the `hij` \"trap\" in the way that the `.111.` on the left-hand side of the `&` disappears once it has been matched." ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "from collections import defaultdict\n", "from pprint import pprint\n", "from string import ascii_lowercase" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "d0, d1 = D_compaction('0'), D_compaction('1')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### `explore()`" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [], "source": [ "def explore(re):\n", "\n", " # Don't have more than 26 states...\n", " names = defaultdict(iter(ascii_lowercase).next)\n", "\n", " table, accepting = dict(), set()\n", "\n", " to_check = {re}\n", " while to_check:\n", "\n", " re = to_check.pop()\n", " state_name = names[re]\n", "\n", " if (state_name, 0) in table:\n", " continue\n", "\n", " if nully(re):\n", " accepting.add(state_name)\n", "\n", " o, i = d0(re), d1(re)\n", " table[state_name, 0] = names[o] ; to_check.add(o)\n", " table[state_name, 1] = names[i] ; to_check.add(i)\n", "\n", " return table, accepting" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{('a', 0): 'b',\n", " ('a', 1): 'c',\n", " ('b', 0): 'b',\n", " ('b', 1): 'd',\n", " ('c', 0): 'b',\n", " ('c', 1): 'e',\n", " ('d', 0): 'b',\n", " ('d', 1): 'f',\n", " ('e', 0): 'b',\n", " ('e', 1): 'g',\n", " ('f', 0): 'b',\n", " ('f', 1): 'h',\n", " ('g', 0): 'i',\n", " ('g', 1): 'g',\n", " ('h', 0): 'i',\n", " ('h', 1): 'h',\n", " ('i', 0): 'i',\n", " ('i', 1): 'j',\n", " ('j', 0): 'i',\n", " ('j', 1): 'h'}" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "table, accepting = explore(it)\n", "table" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'h', 'i'}" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "accepting" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Generate Diagram\n", "Once we have the FSM table and the set of accepting states we can generate the diagram above." ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [], "source": [ "_template = '''\\\n", "digraph finite_state_machine {\n", " rankdir=LR;\n", " size=\"8,5\"\n", " node [shape = doublecircle]; %s;\n", " node [shape = circle];\n", "%s\n", "}\n", "'''\n", "\n", "def link(fr, nm, label):\n", " return ' %s -> %s [ label = \"%s\" ];' % (fr, nm, label)\n", "\n", "\n", "def make_graph(table, accepting):\n", " return _template % (\n", " ' '.join(accepting),\n", " '\\n'.join(\n", " link(from_, to, char)\n", " for (from_, char), (to) in sorted(table.iteritems())\n", " )\n", " )" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "digraph finite_state_machine {\n", " rankdir=LR;\n", " size=\"8,5\"\n", " node [shape = doublecircle]; i h;\n", " node [shape = circle];\n", " a -> b [ label = \"0\" ];\n", " a -> c [ label = \"1\" ];\n", " b -> b [ label = \"0\" ];\n", " b -> d [ label = \"1\" ];\n", " c -> b [ label = \"0\" ];\n", " c -> e [ label = \"1\" ];\n", " d -> b [ label = \"0\" ];\n", " d -> f [ label = \"1\" ];\n", " e -> b [ label = \"0\" ];\n", " e -> g [ label = \"1\" ];\n", " f -> b [ label = \"0\" ];\n", " f -> h [ label = \"1\" ];\n", " g -> i [ label = \"0\" ];\n", " g -> g [ label = \"1\" ];\n", " h -> i [ label = \"0\" ];\n", " h -> h [ label = \"1\" ];\n", " i -> i [ label = \"0\" ];\n", " i -> j [ label = \"1\" ];\n", " j -> i [ label = \"0\" ];\n", " j -> h [ label = \"1\" ];\n", "}\n", "\n" ] } ], "source": [ "print make_graph(table, accepting)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Drive a FSM\n", "There are _lots_ of FSM libraries already. Once you have the state transition table they should all be straightforward to use. State Machine code is very simple. Just for fun, here is an implementation in Python that imitates what \"compiled\" FSM code might look like in an \"unrolled\" form. Most FSM code uses a little driver loop and a table datastructure, the code below instead acts like JMP instructions (\"jump\", or GOTO in higher-level-but-still-low-level languages) to hard-code the information in the table into a little patch of branches." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Trampoline Function\n", "Python has no GOTO statement but we can fake it with a \"trampoline\" function." ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [], "source": [ "def trampoline(input_, jump_from, accepting):\n", " I = iter(input_)\n", " while True:\n", " try:\n", " bounce_to = jump_from(I)\n", " except StopIteration:\n", " return jump_from in accepting\n", " jump_from = bounce_to" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Stream Functions\n", "Little helpers to process the iterator of our data (a \"stream\" of \"1\" and \"0\" characters, not bits.)" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": [ "getch = lambda I: int(next(I))\n", "\n", "\n", "def _1(I):\n", " '''Loop on ones.'''\n", " while getch(I): pass\n", "\n", "\n", "def _0(I):\n", " '''Loop on zeros.'''\n", " while not getch(I): pass" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### A Finite State Machine\n", "With those preliminaries out of the way, from the state table of `.111. & (.01 + 11*)'` we can immediately write down state machine code. (You have to imagine that these are GOTO statements in C or branches in assembly and that the state names are branch destination labels.)" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [], "source": [ "a = lambda I: c if getch(I) else b\n", "b = lambda I: _0(I) or d\n", "c = lambda I: e if getch(I) else b\n", "d = lambda I: f if getch(I) else b\n", "e = lambda I: g if getch(I) else b\n", "f = lambda I: h if getch(I) else b\n", "g = lambda I: _1(I) or i\n", "h = lambda I: _1(I) or i\n", "i = lambda I: _0(I) or j\n", "j = lambda I: h if getch(I) else i" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that the implementations of `h` and `g` are identical ergo `h = g` and we could eliminate one in the code but `h` is an accepting state and `g` isn't." ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [], "source": [ "def acceptable(input_):\n", " return trampoline(input_, a, {h, i})" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 0 False\n", " 1 False\n", " 10 False\n", " 11 False\n", " 100 False\n", " 101 False\n", " 110 False\n", " 111 False\n", " 1000 False\n", " 1001 False\n", " 1010 False\n", " 1011 False\n", " 1100 False\n", " 1101 False\n", " 1110 True\n", " 1111 False\n", "10000 False\n", "10001 False\n", "10010 False\n", "10011 False\n", "10100 False\n", "10101 False\n", "10110 False\n", "10111 True\n", "11000 False\n", "11001 False\n", "11010 False\n", "11011 False\n", "11100 True\n", "11101 False\n", "11110 True\n", "11111 False\n" ] } ], "source": [ "for n in range(2**5):\n", " s = bin(n)[2:]\n", " print '%05s' % s, acceptable(s)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Reversing the Derivatives to Generate Matching Strings\n", "(UNFINISHED)\n", "Brzozowski also shewed how to go from the state machine to strings and expressions..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Each of these states is just a name for a Brzozowskian RE, and so, other than the initial state `a`, they can can be described in terms of the derivative-with-respect-to-N of some other state/RE:\n", "\n", " c = d1(a)\n", " b = d0(a)\n", " b = d0(c)\n", " ...\n", " i = d0(j)\n", " j = d1(i)\n", "\n", "Consider:\n", "\n", " c = d1(a)\n", " b = d0(c)\n", "\n", "Substituting:\n", "\n", " b = d0(d1(a))\n", "\n", "Unwrapping:\n", "\n", "\n", " b = d10(a)\n", "\n", "'''\n", "\n", " j = d1(d0(j))\n", "\n", "Unwrapping:\n", "\n", " j = d1(d0(j)) = d01(j)\n", "\n", "We have a loop or \"fixed point\".\n", "\n", " j = d01(j) = d0101(j) = d010101(j) = ...\n", "\n", "hmm...\n", "\n", " j = (01)*\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.12" } }, "nbformat": 4, "nbformat_minor": 2 }