# 瞎猜的狀態機

December 17, 2021

## 轉換為確定性有限自動機

let manual = new Manual([
new Rule({
state : 'S1',
input : 'a',
nextState : 'S2'
}),
new Rule({
state : 'S2',
input : 'a',
nextState : 'S3'
}),
new Rule({
state : 'S3',
input : 'a',
nextState : 'S4'
}),
new Rule({
state : 'S4',
input : 'a',
nextState : 'S5'
}),
new Rule({
state : 'S5',
input : 'a',
nextState : 'S6'
}),
new Rule({
state : 'S6',
input : 'a',
nextState : 'S1'
})
]);

let fa = new FA(manual, 'S1', ['S1', 'S3', 'S4', 'S5']);
console.log(fa.canAccept('aaaaaaaa'));

class Rule {
constructor({state, input, nextState}) {
this.state = state;
this.input = input;
this.nextState = nextState;
}

isApplicableTo(state, input) {
return this.state === state &&
this.input === input;
}
}

class Manual {
constructor(rules) {
this.rules = rules;
}

collectStates(states, input) {
return Array.from(states)
.map(state => {
return this.rules.filter(rule => rule.isApplicableTo(state, input))
.map(rule => rule.nextState);
})
.reduce((acc, states) => acc.concat(states));
}

freeMoves(states) {
let frees = new Set(
this.collectStates(states, null)
);
return frees.size === 0 ? states : frees;
}

next_states(states, input) {
return new Set(
this.collectStates(this.freeMoves(states), input)
);
}
}

class Machine {
constructor(manual, states, acceptables) {
this.manual = manual;
this.states = new Set(states);
this.acceptables = acceptables;
}

canAccept(text) {
let manual = this.manual;
function digest(states, txt) {
if(states.size === 0 || txt.length === 0) {
return Array.from(states);
}
return digest(manual.next_states(states, txt[0]), txt.slice(1));
}

return digest(this.states, text).map(state => this.acceptables.includes(state))
.some(acceptable => acceptable);
}
}

let manual = new Manual([
new Rule({
state : 1,
input : null,
nextState : 2
}),
new Rule({
state : 1,
input : null,
nextState : 4
}),
new Rule({
state : 2,
input : 'a',
nextState : 3
}),
new Rule({
state : 3,
input : 'a',
nextState : 2
}),
new Rule({
state : 4,
input : 'a',
nextState : 5
}),
new Rule({
state : 5,
input : 'a',
nextState : 6
}),
new Rule({
state : 6,
input : 'a',
nextState : 4
})
]);

let machine = new Machine(manual, [1], [2, 4]);
console.log(machine.canAccept('aaaaa'));