|
| 1 | +classFiniteAutomaton{ |
| 2 | + #transitionFunction |
| 3 | + #startState |
| 4 | + #acceptStates |
| 5 | + |
| 6 | +constructor({ transitions, startState, acceptStates}){ |
| 7 | +this.#transitionFunction=newTransitionFunction(transitions) |
| 8 | +this.#startState=startState |
| 9 | +this.#acceptStates=[...acceptStates] |
| 10 | +} |
| 11 | + |
| 12 | +isAccepting(string){ |
| 13 | +const{ isAccepting}=this.process(string) |
| 14 | +returnisAccepting |
| 15 | +} |
| 16 | + |
| 17 | +process(string){ |
| 18 | +conststateSequence=[this.#startState] |
| 19 | +letstate=this.#startState |
| 20 | +for(constsymbolofstring){ |
| 21 | +state=this.#transitionFunction.get(state,symbol) |
| 22 | +stateSequence.push(state) |
| 23 | +} |
| 24 | +constisAccepting=this.#isAcceptingState(state) |
| 25 | +return{ isAccepting, stateSequence} |
| 26 | +} |
| 27 | + |
| 28 | + #isAcceptingState(state){ |
| 29 | +returnthis.#acceptStates.includes(state) |
| 30 | +} |
| 31 | + |
| 32 | +states(){ |
| 33 | +returnthis.#transitionFunction.states() |
| 34 | +} |
| 35 | + |
| 36 | +alphabet(){ |
| 37 | +returnthis.#transitionFunction.alphabet() |
| 38 | +} |
| 39 | + |
| 40 | +transitions(){ |
| 41 | +returnthis.#transitionFunction.transitions() |
| 42 | +} |
| 43 | + |
| 44 | +startState(){ |
| 45 | +returnthis.#startState |
| 46 | +} |
| 47 | + |
| 48 | +acceptStates(){ |
| 49 | +return[...this.#acceptStates] |
| 50 | +} |
| 51 | +} |
| 52 | + |
| 53 | +classTransitionFunction{ |
| 54 | + #map |
| 55 | + |
| 56 | +constructor(transitions){ |
| 57 | +this.#map=this.#createTransitionMap(transitions) |
| 58 | +} |
| 59 | + |
| 60 | + #createTransitionMap(transitions){ |
| 61 | +constmap=newMap() |
| 62 | +for(const{ state, symbol, resultState}oftransitions){ |
| 63 | +letsingleStateMap=map.get(state) |
| 64 | +if(!singleStateMap){ |
| 65 | +map.set(state,(singleStateMap=newMap())) |
| 66 | +} |
| 67 | +singleStateMap.set(symbol,resultState) |
| 68 | +} |
| 69 | +returnmap |
| 70 | +} |
| 71 | + |
| 72 | +get(state,symbol){ |
| 73 | +constsingleStateMap=this.#map.get(state) |
| 74 | +returnsingleStateMap.get(symbol) |
| 75 | +} |
| 76 | + |
| 77 | +states(){ |
| 78 | +returnArray.from(this.#map.keys()) |
| 79 | +} |
| 80 | + |
| 81 | +alphabet(){ |
| 82 | +constarbitraryState=this.states()[0] |
| 83 | +constsingleStateMap=this.#map.get(arbitraryState) |
| 84 | +returnArray.from(singleStateMap.keys()) |
| 85 | +} |
| 86 | + |
| 87 | +transitions(){ |
| 88 | +consttransitions=[] |
| 89 | +for(const[state,singleStateMap]ofthis.#map){ |
| 90 | +for(const[symbol,resultState]ofsingleStateMap){ |
| 91 | +transitions.push({ state, symbol, resultState}) |
| 92 | +} |
| 93 | +} |
| 94 | +returntransitions |
| 95 | +} |
| 96 | +} |
| 97 | + |
| 98 | + |
| 99 | +// accepts binary strings that contains an even number of 0s |
| 100 | +constautomaton=newFiniteAutomaton({ |
| 101 | +transitions:[ |
| 102 | +{state:'q0',symbol:'0',resultState:'q1'}, |
| 103 | +{state:'q0',symbol:'1',resultState:'q0'}, |
| 104 | +{state:'q1',symbol:'0',resultState:'q0'}, |
| 105 | +{state:'q1',symbol:'1',resultState:'q1'}, |
| 106 | +], |
| 107 | +startState:'q0', |
| 108 | +acceptStates:['q0'] |
| 109 | +}) |
| 110 | + |
| 111 | +console.log('states:',automaton.states()) |
| 112 | +console.log('alphabet:',automaton.alphabet()) |
| 113 | +console.log('transitions:',automaton.transitions()) |
| 114 | +console.log('startState: ',automaton.startState()) |
| 115 | +console.log('acceptStates: ',automaton.acceptStates()) |
| 116 | + |
| 117 | +console.log('accepts: \'\'',automaton.isAccepting('')) |
| 118 | +console.log('accepts: 0',automaton.isAccepting('0')) |
| 119 | +console.log('accepts: 00',automaton.isAccepting('00')) |
| 120 | +console.log('accepts: 10',automaton.isAccepting('10')) |
| 121 | +console.log('accepts: 101',automaton.isAccepting('101')) |
| 122 | +console.log('accepts: 001',automaton.isAccepting('001')) |
| 123 | +console.log('accepts: 000',automaton.isAccepting('000')) |
| 124 | +console.log('accepts: 110001011',automaton.isAccepting('110001011')) |
| 125 | + |