{"_id":"statemachines","_rev":"3630710","name":"statemachines","description":"Deterministic and Nondeterministic Finite State Machines for JavaScript. The backend for my regex library.","dist-tags":{"latest":"0.1.1"},"maintainers":[{"name":"aaditmshah","email":"aaditmshah@fastmail.fm"}],"time":{"modified":"2024-10-21T04:08:55.000Z","created":"2013-05-15T05:31:40.049Z","0.1.1":"2014-03-28T14:54:15.110Z","0.1.0":"2013-05-15T05:31:40.049Z"},"users":{},"author":{"name":"Aadit M Shah","email":"aaditmshah@fastmail.fm","url":"http://aaditmshah.github.com/"},"repository":{"type":"git","url":"https://github.com/aaditmshah/statemachines.git"},"versions":{"0.1.1":{"name":"statemachines","description":"Deterministic and Nondeterministic Finite State Machines for JavaScript. The backend for my regex library.","version":"0.1.1","keywords":["deterministic","nondeterministic","finite","state","machines","backend","regex"],"author":{"name":"Aadit M Shah","email":"aaditmshah@fastmail.fm","url":"http://aaditmshah.github.com/"},"main":"lib/statemachines.js","maintainers":[{"name":"aaditmshah","email":"aaditmshah@fastmail.fm"}],"contributors":[{"name":"Aadit M Shah","email":"aaditmshah@fastmail.fm","url":"http://aaditmshah.github.com/"}],"bugs":{"url":"https://github.com/aaditmshah/statemachines/issues"},"licenses":[{"type":"MIT","url":"http://opensource.org/licenses/MIT"}],"repositories":[{"type":"git","url":"https://github.com/aaditmshah/statemachines.git"}],"dependencies":{"augment":"3.2.1","sorted-array":"1.1.0"},"homepage":"https://github.com/aaditmshah/statemachines","repository":{"type":"git","url":"https://github.com/aaditmshah/statemachines.git"},"_id":"statemachines@0.1.1","dist":{"shasum":"906b64e20997db17e285eb737dec9fe2338f73cf","size":39970,"noattachment":false,"key":"/statemachines/-/statemachines-0.1.1.tgz","tarball":"http://registry.cnpm.dingdandao.com/statemachines/download/statemachines-0.1.1.tgz"},"_from":".","_npmVersion":"1.3.25","_npmUser":{"name":"aaditmshah","email":"aaditmshah@fastmail.fm"},"directories":{},"_cnpmcore_publish_time":"2021-12-19T11:11:21.742Z","deprecated":"Package no longer supported. Contact Support at https://www.npmjs.com/support for more info.","publish_time":1396018455110,"_cnpm_publish_time":1396018455110},"0.1.0":{"name":"statemachines","description":"Deterministic and Nondeterministic Finite State Machines for JavaScript. The backend for my regex library.","version":"0.1.0","keywords":["deterministic","nondeterministic","finite","state","machines","backend","regex"],"author":{"name":"Aadit M Shah","email":"aaditmshah@myopera.com","url":"http://aaditmshah.github.com/"},"main":"lib/statemachines.js","maintainers":[{"name":"aaditmshah","email":"aaditmshah@fastmail.fm"}],"contributors":[{"name":"Aadit M Shah","email":"aaditmshah@myopera.com","url":"http://aaditmshah.github.com/"}],"bugs":"https://github.com/aaditmshah/statemachines/issues","licenses":[{"type":"MIT","url":"http://opensource.org/licenses/MIT"}],"repositories":[{"type":"git","url":"https://github.com/aaditmshah/statemachines.git"}],"dependencies":{"augment":"3.2.1","sorted-array":"1.1.0"},"homepage":"https://github.com/aaditmshah/statemachines","_id":"statemachines@0.1.0","dist":{"shasum":"b545fd3d8a55280f302b8696f19c0a11c4e33ade","size":40030,"noattachment":false,"key":"/statemachines/-/statemachines-0.1.0.tgz","tarball":"http://registry.cnpm.dingdandao.com/statemachines/download/statemachines-0.1.0.tgz"},"_from":".","_npmVersion":"1.2.18","_npmUser":{"name":"aaditmshah","email":"aaditmshah@myopera.com"},"directories":{},"_cnpmcore_publish_time":"2021-12-19T11:11:20.695Z","deprecated":"Package no longer supported. Contact Support at https://www.npmjs.com/support for more info.","publish_time":1368595900049,"_cnpm_publish_time":1368595900049}},"readme":"# State Machines #\n\nDeterministic and Nondeterministic Finite State Machines for JavaScript. The backend for my regex library.\n\n## Installation ##\n\nState Machines may be installed on [node.js](http://nodejs.org/ \"node.js\") via the [node package manager](https://npmjs.org/ \"npm\") using the command `npm install statemachines`.\n\nYou may also install it on [RingoJS](http://ringojs.org/ \"Home - RingoJS\") using the command `ringo-admin install aaditmshah/statemachines`.\n\nYou may install it as a [component](https://github.com/component/component \"component/component\") for web apps using the command `component install aaditmshah/statemachines`.\n\n## Usage ##\n\nA `StateMachine` is a pattern recognizer. There are two types of state machines - `Deterministic` and `Nondeterministic`. Both are equally powerful.\n\nDeterministic state machines are faster. However nondeterministic state machines are easier to create. Fortunately there's a way to create an equivalent deterministic state machine from a nondeterministic one.\n\nConsider the following nondeterministic state machine:\n\n![Nondeterministic Finite State Machine](https://raw.github.com/aaditmshah/statemachines/master/nfa.png \"Nondeterministic Finite State Machine\")\n\nWe construct it in JavaScript as follows:\n\n```javascript\nvar StateMachine = require(\"statemachines\");\n\nvar nfa = new StateMachine.Nondeterministic([\n    { \"\" : [1, 7] },\n    { \"\" : [2, 4] },\n    { \"a\": [3] },\n    { \"\" : [6] },\n    { \"b\": [5] },\n    { \"\" : [6] },\n    { \"\" : [1, 7] },\n    { \"a\": [8] },\n    { \"b\": [9] },\n    { \"b\": [10] },\n    { }\n], [10]);\n```\n\nThe first parameter to `StateMachine.Nondeterministic` must be the transition table for the nondeterministic state machine. The second parameter must be list of final or accepting states of the state machine.\n\nThe state machine may now be used to `test` input strings as follows:\n\n```javascript\nnfa.test(\"abb\");   // true\nnfa.test(\"aabb\");  // true\nnfa.test(\"babb\");  // true\nnfa.test(\"aaabb\"); // true\nnfa.test(\"ababb\"); // true\nnfa.test(\"abba\");  // false\nnfa.test(\"cabb\");  // false\n```\n\nThe following deterministic state machine is equivalent to the above nondeterministic state machine:\n\n![Deterministic Finite State Machine](https://raw.github.com/aaditmshah/statemachines/master/dfa.png \"Deterministic Finite State Machine\")\n\nWe can construct it in JavaScript as follows:\n\n```javascript\nvar dfa = new StateMachine.Deterministic({\n    {\n        \"a\": 1,\n        \"b\": 2\n    },\n    {\n        \"a\": 1,\n        \"b\": 3\n    },\n    {\n        \"a\": 1,\n        \"b\": 2\n    },\n    {\n        \"a\": 1,\n        \"b\": 4\n    },\n    {\n        \"a\": 1,\n        \"b\": 2\n    }\n}, [4]);\n```\n\nHowever it's more convenient to construct it from the nondeterministic state machine using the `subset` method:\n\n```javascript\nvar dfa = nfa.subset();\n```\n\nThe resulting deterministic state machine accepts the same language as the nondeterministic state machine:\n\n```javascript\ndfa.test(\"abb\");   // true\ndfa.test(\"aabb\");  // true\ndfa.test(\"babb\");  // true\ndfa.test(\"aaabb\"); // true\ndfa.test(\"ababb\"); // true\ndfa.test(\"abba\");  // false\ndfa.test(\"cabb\");  // false\n```\n\nThat's all folks.\n","_attachments":{},"homepage":"https://github.com/aaditmshah/statemachines","bugs":{"url":"https://github.com/aaditmshah/statemachines/issues"}}