fauton - npm Package Compare versions

Comparing version 0.0.4 to 0.0.5

dist/libs/FiniteAutomaton.js

@@ -19,47 +19,3 @@ "use strict";
         this.#normalize(finiteAutomaton);
-        if (automatonType === 'non-deterministic' && this.automaton.epsilon_transitions) {
-            this.#expandEpsilonTransitions(this.automaton.alphabets, this.automaton.epsilon_transitions, this.automaton.transitions);
-        }
     }
-    #expandEpsilonTransitions(alphabets, epsilonTransitions, transitions) {
-        alphabets.forEach((alphabet) => {
-            Object.entries(transitions).forEach(([transitionState, transitionsRecord]) => {
-                if (epsilonTransitions[transitionState]) {
-                    const firstPhaseSet = this.#traverseEpsilon(epsilonTransitions, transitionState);
-                    const secondPhaseSet = new Set();
-                    firstPhaseSet.forEach((state) => {
-                        if (transitions[state]) {
-                            transitions[state][alphabet]?.forEach((transitionRecordState) => {
-                                secondPhaseSet.add(transitionRecordState);
-                            });
-                        }
-                    });
-                    const thirdPhaseSet = new Set();
-                    secondPhaseSet.forEach((secondPhaseState) => {
-                        this.#traverseEpsilon(epsilonTransitions, secondPhaseState).forEach((state) => {
-                            thirdPhaseSet.add(state);
-                        });
-                    });
-                    if (transitionsRecord) {
-                        transitionsRecord[alphabet] = Array.from(thirdPhaseSet);
-                    }
-                }
-            });
-        });
-    }
-    #traverseEpsilon(epsilonTransition, state) {
-        const stack = [];
-        const allEpsilonStates = new Set(state);
-        stack.push(state);
-        while (stack.length !== 0) {
-            const currentState = stack.pop();
-            epsilonTransition[currentState]?.forEach((epsilonTransitionState) => {
-                if (!allEpsilonStates.has(epsilonTransitionState)) {
-                    stack.push(epsilonTransitionState);
-                    allEpsilonStates.add(epsilonTransitionState);
-                }
-            });
-        }
-        return allEpsilonStates;
-    }
     #normalize(finiteAutomaton) {
@@ -66,0 +22,0 @@ this.#validate(finiteAutomaton.label ?? '', this.#generatePreNormalizationErrors(finiteAutomaton));

dist/libs/NonDeterministicFiniteAutomaton.d.ts

@@ -1,5 +0,12 @@
-import { InputFiniteAutomaton } from '../types';
+import { IFiniteAutomaton, InputFiniteAutomaton } from '../types';
+import { DeterministicFiniteAutomaton } from './DeterministicFiniteAutomaton';
 import { FiniteAutomaton } from './FiniteAutomaton';
 export declare class NonDeterministicFiniteAutomaton extends FiniteAutomaton {
     constructor(testLogic: (inputString: string) => boolean, automaton: InputFiniteAutomaton, automatonId?: string);
+    convertToRegularNfa(): void;
+    epsilonClosureOfState(state: string): string[];
+    moveAndEpsilonClosureStateSet(states: string[], symbol: string): string[];
+    convertToDeterministicFiniteAutomaton(dfaOptions: Partial<Pick<Pick<IFiniteAutomaton, 'automaton'>['automaton'], 'label' | 'description'> & {
+        separator: string;
+    }>): DeterministicFiniteAutomaton;
 }

dist/libs/NonDeterministicFiniteAutomaton.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
 exports.NonDeterministicFiniteAutomaton = void 0;
+const DeterministicFiniteAutomaton_1 = require("./DeterministicFiniteAutomaton");
 const FiniteAutomaton_1 = require("./FiniteAutomaton");
@@ -8,4 +9,131 @@ class NonDeterministicFiniteAutomaton extends FiniteAutomaton_1.FiniteAutomaton {
         super(testLogic, automaton, 'non-deterministic', automatonId);
+        if (this.automaton.epsilon_transitions) {
+            this.convertToRegularNfa();
+        }
     }
+    convertToRegularNfa() {
+        const { alphabets, epsilon_transitions: epsilonTransitions, transitions } = this.automaton;
+        alphabets.forEach((alphabet) => {
+            Object.entries(transitions).forEach(([transitionState, transitionsRecord]) => {
+                if (epsilonTransitions[transitionState]) {
+                    const firstPhaseSet = this.epsilonClosureOfState(transitionState);
+                    const secondPhaseSet = new Set();
+                    const thirdPhaseSet = new Set();
+                    firstPhaseSet.forEach((state) => {
+                        if (transitions[state]) {
+                            transitions[state][alphabet]?.forEach((transitionRecordState) => {
+                                secondPhaseSet.add(transitionRecordState);
+                            });
+                        }
+                    });
+                    secondPhaseSet.forEach((secondPhaseState) => {
+                        this.epsilonClosureOfState(secondPhaseState).forEach((state) => {
+                            thirdPhaseSet.add(state);
+                        });
+                    });
+                    if (transitionsRecord) {
+                        transitionsRecord[alphabet] = Array.from(thirdPhaseSet);
+                    }
+                }
+            });
+        });
+    }
+    epsilonClosureOfState(state) {
+        const { epsilon_transitions: epsilonTransitions } = this.automaton;
+        const stack = [];
+        const allEpsilonStates = new Set(state);
+        stack.push(state);
+        while (stack.length !== 0) {
+            const currentState = stack.pop();
+            epsilonTransitions[currentState]?.forEach((epsilonTransitionState) => {
+                if (!allEpsilonStates.has(epsilonTransitionState)) {
+                    stack.push(epsilonTransitionState);
+                    allEpsilonStates.add(epsilonTransitionState);
+                }
+            });
+        }
+        return Array.from(allEpsilonStates);
+    }
+    moveAndEpsilonClosureStateSet(states, symbol) {
+        const transitionRecordExtractedStates = new Set();
+        states.forEach((state) => {
+            const statesForSymbol = this.automaton.transitions[state]?.[symbol];
+            if (statesForSymbol) {
+                statesForSymbol.forEach((stateForSymbol) => transitionRecordExtractedStates.add(stateForSymbol));
+            }
+        });
+        const finalStates = new Set(transitionRecordExtractedStates);
+        if (this.automaton.epsilon_transitions) {
+            transitionRecordExtractedStates.forEach((transitionRecordExtractedState) => {
+                const epsilonClosureOfStates = this.epsilonClosureOfState(transitionRecordExtractedState);
+                epsilonClosureOfStates.forEach((epsilonClosureOfState) => {
+                    finalStates.add(epsilonClosureOfState);
+                });
+            });
+        }
+        return Array.from(finalStates);
+    }
+    convertToDeterministicFiniteAutomaton(dfaOptions) {
+        const separator = dfaOptions.separator ?? ',';
+        const startState = this.automaton.start_state;
+        const newStartStates = this.automaton.epsilon_transitions
+            ? this.epsilonClosureOfState(startState)
+            : [this.automaton.start_state];
+        const newStartStateString = newStartStates.sort().join(separator);
+        const newStates = new Set();
+        const unmarkedStates = [newStartStateString];
+        const newTransitionsRecord = {};
+        const totalAlphabets = this.automaton.alphabets.length;
+        const newFinalStates = new Set();
+        newStates.add(newStartStateString);
+        let hasDeadState = false;
+        while (unmarkedStates.length !== 0) {
+            const currentStatesString = unmarkedStates.shift();
+            this.automaton.alphabets.forEach((symbol, symbolIndex) => {
+                const newStateString = this.moveAndEpsilonClosureStateSet(currentStatesString.split(separator), symbol)
+                    .sort()
+                    .join(separator);
+                if (!newStates.has(newStateString) && newStateString) {
+                    newStates.add(newStateString);
+                    unmarkedStates.push(newStateString);
+                }
+                if (!newStateString) {
+                    hasDeadState = true;
+                    newStates.add(`Ø`);
+                }
+                if (!newTransitionsRecord[currentStatesString]) {
+                    newTransitionsRecord[currentStatesString] = new Array(totalAlphabets).fill(null);
+                }
+                if (newStateString)
+                    newTransitionsRecord[currentStatesString][symbolIndex] = [newStateString];
+                else {
+                    newTransitionsRecord[currentStatesString][symbolIndex] = [`Ø`];
+                }
+            });
+        }
+        this.automaton.final_states.forEach((finalState) => {
+            newStates.forEach((newState) => {
+                if (newState.includes(finalState)) {
+                    newFinalStates.add(newState);
+                }
+            });
+        });
+        if (hasDeadState) {
+            newTransitionsRecord['Ø'] = {};
+            this.automaton.alphabets.forEach((symbol) => {
+                newTransitionsRecord['Ø'][symbol] = ['Ø'];
+            });
+        }
+        return new DeterministicFiniteAutomaton_1.DeterministicFiniteAutomaton(this.testLogic, {
+            alphabets: this.automaton.alphabets,
+            final_states: Array.from(newFinalStates),
+            label: dfaOptions?.label ?? this.automaton.label,
+            start_state: newStartStateString,
+            states: Array.from(newStates),
+            transitions: newTransitionsRecord,
+            epsilon_transitions: null,
+            description: dfaOptions?.description ?? this.automaton.description,
+        });
+    }
 }
 exports.NonDeterministicFiniteAutomaton = NonDeterministicFiniteAutomaton;

package.json

 {
   "name": "fauton",
-  "version": "0.0.4",
-  "description": "A library to test any finite automaton(FA) with arbitrary alphabets",
+  "version": "0.0.5",
+  "description": "A library to test any finite automaton with arbitrary alphabets",
   "main": "dist/index.js",
@@ -17,2 +17,11 @@ "types": "dist/index.d.ts",
   ],
+  "np": {
+    "branch": "main",
+    "cleanup": false,
+    "tests": false,
+    "yarn": false,
+    "contents": "dist",
+    "testScript": "build",
+    "message": "v%s"
+  },
   "keywords": [
@@ -25,2 +34,4 @@ "dfa",
     "epsilon-nfa",
+    "epsilon-nfa-to-nfa",
+    "regex",
     "automaton"
@@ -48,2 +59,3 @@ ],
     "del-cli": "^4.0.1",
+    "np": "^7.5.0",
     "typescript": "^4.4.4"
@@ -54,2 +66,2 @@ },
   }
-}
+}

readme.md

@@ -7,2 +7,5 @@ <div align="center"> <h1>Fauton</h1> </div>
 <p align="center">
+  <a href="www.npmjs.com/package/fauton">
+    <img src="https://img.shields.io/npm/dw/fauton"/>
+  </a>
   <a href="https://app.codecov.io/gh/Devorein/fauton/branch/master"><img src="https://img.shields.io/codecov/c/github/devorein/fauton?color=blue"/></a>
@@ -15,2 +18,3 @@ <img src="https://img.shields.io/github/commit-activity/m/devorein/fauton?color=yellow" />
 - [Features](#features)
+- [Motivation](#motivation)
 - [Examples](#examples)
@@ -21,3 +25,5 @@ - [Dfa for string that starts with bc](#dfa-for-string-that-starts-with-bc)
   - [ε-nfa to nfa](#ε-nfa-to-nfa)
-  - [Generate and render full graph for a ε-nfa](#generate-and-render-full-graph-for-a-ε-nfa)
+  - [Generate and render full graph for a ε-nfa given a string](#generate-and-render-full-graph-for-a-ε-nfa-given-a-string)
+  - [Conversion from ε-nfa to dfa](#conversion-from-ε-nfa-to-dfa)
+  - [Conversion from nfa to dfa](#conversion-from-nfa-to-dfa)
 - [Conditions for DFA](#conditions-for-dfa)
@@ -48,2 +54,4 @@ - [Transitions Record Transformation](#transitions-record-transformation)
 
+**Please note that I won't be following semver at the initial stages, as there could be a lot of (breaking) changes between each release which will all be patch**
+
 # Features
@@ -55,8 +63,14 @@
 4. ε-nfa to nfa conversion
-5. Generate artifacts files for each automaton
-6. Highly customizable
-7. Full typescript support
-8. Simple concise error messages for invalid finite automaton
-9. Generate full graph for ε-nfa given a string
+5. ε-nfa/nfa to dfa conversion
+6. Generate artifacts files for each automaton
+7. Highly customizable
+8. Full typescript support
+9. Simple concise error messages for invalid finite automaton
+10. Generate full graph for ε-nfa given a string
+11. Generate ε closure of a single state
 
+# Motivation
+
+Its easy to check whether a string should be accepted or rejected using our favourite programming languages, but its a lot harder to transfer the logic to a finite automaton. Even if we are quite sure we can't be 100% sure until and unless we try out all the possible combinations of alphabet of the automata. This is an extremely tedious and error-prone process. Why not automate testing an automaton?
+
 # Examples
@@ -295,3 +309,3 @@
 
-## Generate and render full graph for a ε-nfa
+## Generate and render full graph for a ε-nfa given a string
 
@@ -386,2 +400,118 @@ ```js
 
+## Conversion from ε-nfa to dfa
+
+```js
+const { NonDeterministicFiniteAutomaton } = require('fauton');
+
+const epsilonNfa = new NonDeterministicFiniteAutomaton((_, automatonTest) => automatonTest, {
+	start_state: 0,
+	alphabets: ['a', 'b'],
+	final_states: [10],
+	label: 'sample ε nfa',
+	states: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
+	transitions: {
+		2: [3],
+		4: [null, 5],
+		7: [8],
+		8: [null, 9],
+		9: [null, 10],
+	},
+	epsilon_transitions: {
+		0: [1, 7],
+		1: [2, 4],
+		3: [6],
+		5: [6],
+		6: [1, 7],
+	},
+});
+
+console.log(JSON.stringify(epsilonNfa.convertToDeterministicFiniteAutomaton(), null, 2));
+```
+
+```json
+{
+	"automaton": {
+		"alphabets": ["a", "b"],
+		"final_states": ["0,1,10,2,4,5,6,7"],
+		"label": "sample ε nfa",
+		"start_state": "0,1,2,4,7",
+		"states": ["0,1,2,4,7", "1,2,3,4,6,7,8", "1,2,4,5,6,7", "1,2,4,5,6,7,9", "0,1,10,2,4,5,6,7"],
+		"transitions": {
+			"0,1,2,4,7": {
+				"a": ["1,2,3,4,6,7,8"],
+				"b": ["1,2,4,5,6,7"]
+			},
+			"1,2,3,4,6,7,8": {
+				"a": ["1,2,3,4,6,7,8"],
+				"b": ["1,2,4,5,6,7,9"]
+			},
+			"1,2,4,5,6,7": {
+				"a": ["1,2,3,4,6,7,8"],
+				"b": ["1,2,4,5,6,7"]
+			},
+			"1,2,4,5,6,7,9": {
+				"a": ["1,2,3,4,6,7,8"],
+				"b": ["0,1,10,2,4,5,6,7"]
+			},
+			"0,1,10,2,4,5,6,7": {
+				"a": ["1,2,3,4,6,7,8"],
+				"b": ["1,2,4,5,6,7"]
+			}
+		},
+		"epsilon_transitions": null
+	}
+}
+```
+
+## Conversion from nfa to dfa
+
+```js
+const { NonDeterministicFiniteAutomaton } = require('fauton');
+
+const nfa = new NonDeterministicFiniteAutomaton((_, automatonTest) => automatonTest, {
+	start_state: 'q0',
+	alphabets: ['a', 'b'],
+	final_states: ['q1'],
+	label: 'sample nfa',
+	states: ['q0', 'q1', 'q2'],
+	transitions: {
+		q0: [['q2', 'q1']],
+		q2: [['q2', 'q1'], 'q2'],
+	},
+});
+
+console.log(JSON.stringify(nfa.convertToDeterministicFiniteAutomaton(), null, 2));
+```
+
+```json
+{
+	"automaton": {
+		"alphabets": ["a", "b"],
+		"final_states": ["q1,q2"],
+		"label": "sample nfa",
+		"start_state": "q0",
+		"states": ["q0", "q1,q2", "Ø", "q2"],
+		"transitions": {
+			"q0": {
+				"a": ["q1,q2"],
+				"b": ["Ø"]
+			},
+			"q1,q2": {
+				"a": ["q1,q2"],
+				"b": ["q2"]
+			},
+			"q2": {
+				"a": ["q1,q2"],
+				"b": ["q2"]
+			},
+			"Ø": {
+				"a": ["Ø"],
+				"b": ["Ø"]
+			}
+		},
+		"epsilon_transitions": null
+	}
+}
+```
+
 Take a look at [examples](./examples) folder for more examples.
@@ -393,7 +523,8 @@
 
-1. `transitions` record must contain all the elements of `states` as its key
+1. `transitions` record must contain all the elements of `states` array as its key
 2. Only the items of the `states` can be the key of the `transitions` record
 3. `transitions` record values must either be an array or the string literal `loop`
-4. If its an array its length should be the same `alphabets` array
-5. `transitions` record values can only have `symbols` that are present in the `alphabets` array
+4. If its an array its length should be the same `alphabets` array, where each index represents which state to transition to when encountering a symbol (index of the `alphabets` array)
+5. Also if its an array each item should be a string as for a single symbol a dfa can transition to only one state
+6. `transitions` record values can only have `symbols` that are present in the `alphabets` array
 
@@ -400,0 +531,0 @@ # Transitions Record Transformation

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

79244

increased by11.66%

Lines of code

1043

increased by9.56%

Number of lines in readme file

812

increased by19.24%

Worsened metrics

Dev dependency count

6

increased by20%

No dependency changes