-
Notifications
You must be signed in to change notification settings - Fork 13
/
fsa.js
166 lines (144 loc) · 6.9 KB
/
fsa.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
import { UnknownStateError, UnknownSymbolError } from '../util/errors.js'
import { removeDuplicates } from '../util/array.js'
export default class FSA {
/**
* FSA represents a finite state automaton. This can be either an NFA or a DFA.
*
* @param {Array} states The array of states in this FSA (e.g. ['1', '2', '3'])
* @param {Array} alphabet The array of symbols in this FSA (e.g. ['a', 'b'])
* @param {Object} transitions A map of states and symbols to other states (e.g. transitions['1']['a'] => ['2', '3'] means upon the input of symbol a at state 1, an NFA can transition to state 2 or state 3)
* @param {String} startState The name of the start state for this FSA (e.g. '1')
* @param {Array} acceptStates The array of states that an input can be accepted on (e.g. ['1', '3'])
*/
constructor (states, alphabet, transitions, startState, acceptStates) {
this.states = states
this.alphabet = alphabet
this.transitions = transitions
this.startState = startState
this.acceptStates = acceptStates
}
/**
* Clone this FSA into a new object instead of copying its reference
* This is useful for freezing the state of the FSA and passing it to a function
*/
clone () {
return new FSA(JSON.parse(JSON.stringify(this.states)), JSON.parse(JSON.stringify(this.alphabet)), JSON.parse(JSON.stringify(this.transitions)), this.startState, JSON.parse(JSON.stringify(this.acceptStates)))
}
/**
* Remove all of a state's references from the FSA
*
* @param {String} state The name of the state
*/
removeState (state) {
this.states = this.states.filter(s => s !== state)
this.acceptStates = this.acceptStates.filter(s => s !== state)
if (this.startState === state) this.startState = undefined
delete this.transitions[state]
// Remove all transitions that lead to the state
for (const fromState of Object.keys(this.transitions)) {
for (const symbol of Object.keys(this.transitions[fromState])) {
if (this.transitions[fromState][symbol]) {
this.transitions[fromState][symbol] = this.transitions[fromState][symbol].filter(e => e !== state)
if (this.transitions[fromState][symbol].length === 0) { delete this.transitions[fromState][symbol] }
}
}
}
}
/**
* Merge two states into a single state
*
* @param {String} s1 The first state
* @param {String} s2 The second state
*/
mergeStates (s1, s2) {
// Create the new state
const newState = `${s1}+${s2}`
this.states.push(newState)
if (this.acceptStates.includes(s1)) { this.acceptStates.push(newState) }
if (this.startState === s1 || this.startState === s2) { this.startState = newState }
// Add loopback on the new state for every symbol
this.transitions[newState] = {}
for (const symbol of this.alphabet) {
this.transitions[newState][symbol] = [newState]
}
// Add incoming transitions to the new state using the old states' incoming transitions
for (const state of this.states.filter(e => e !== s1 && e !== s2)) {
for (const symbol of this.alphabet) {
if (this.transitions[state][symbol][0] === s1 || this.transitions[state][symbol][0] === s2) {
this.transitions[state][symbol] = [newState]
}
}
}
// Remove the old states
this.removeState(s1)
this.removeState(s2)
}
/**
* Get the array of arrays that describes the powerset of this FSA's states
*
* @example
* console.log(fsa.states)
* // => ['1', '2', '3']
*
* console.log(fsa.getPowersetOfStates())
* // => [['Ø'], ['1'], ['2'], ['1', '2'], ['3'], ['1', '3'], ['2', '3'], ['1', '2', '3']]
*/
getPowersetOfStates () {
const result = []
result.push(['Ø'])
// https://stackoverflow.com/a/42774138 How to find all subsets of a set in JavaScript?
for (let i = 1; i < (1 << this.states.length); i++) {
const subset = []
for (let j = 0; j < this.states.length; j++) { if (i & (1 << j)) subset.push(this.states[j]) }
result.push(subset.sort())
}
return result
}
/**
* This function implements E(R) from the NFA to DFA conversion description:
*
* E(R) = R ∪ { q | there is an r in R with an ε transition to q }
*
* @param {String} fromState The label of the state to find epsilon-reachable states from
* @returns {Array} The array of states that can be reached via an ε-transition
*/
getEpsilonClosureStates (fromState, checkedStates = []) {
if (!this.states.includes(fromState)) throw new UnknownStateError(fromState)
// Ensure fromState has any epsilon transitions
if (!this.transitions[fromState] || !this.transitions[fromState]['ε']) {
return [fromState]
}
const toStates = this.transitions[fromState]['ε']
// Recursively check for epsilon transitions
// Avoid infinite loop by omitting already-checked states
const allEpsilonClosureStates = toStates
.filter(s => checkedStates.indexOf(s) === -1)
.map(s => this.getEpsilonClosureStates(s, [...checkedStates, ...toStates]))
return removeDuplicates([fromState, ...allEpsilonClosureStates].flat())
}
/**
* Find the array of states that are able to be reached by the given state. This includes via ε-transitions
*
* @param {String} fromState The label of the state to find reachable states from
* @param {String} symbol The symbol on which to search the transitions
* @returns {Array} The list of states that can be reached from the given state
*/
getReachableStates (fromState, symbol, list = []) {
if (!this.states.includes(fromState)) throw new UnknownStateError(fromState)
if (symbol !== 'ε' && !this.alphabet.includes(symbol)) throw new UnknownSymbolError(symbol)
if (list.length > 200) throw new Error('There is an infinite transition loop apparent in the NFA')
if (!this.transitions[fromState] || !this.transitions[fromState][symbol]) {
return symbol === 'ε' ? [] : ['Ø']
}
// Add the state's transitions on the given label to the list
list = list.concat(this.transitions[fromState][symbol])
// Check ε-transitions of the states that can be directly reached
for (const s of this.transitions[fromState][symbol]) {
if (this.transitions[s] && this.transitions[s]['ε'] !== undefined) {
// Recursively search for ε-transitions and add them to the list
list = this.getReachableStates(s, 'ε', list)
}
}
return removeDuplicates(list)
}
}