✅状態遷移機械をexportする
2022-01-23
2022-01-19
13:52:18
状態遷移機械を遷移させる函数を外部に切り出した
ついでに状態をlogに出してみたのだが、表示されたビットと挙動が違うようなので困惑している
コード
log.tsimport { Asearch, INITSTATE, moveState, preparePatterns } from "./mod.ts";
const source = "abcde";
const pats = preparePatterns(source);
let state = INITSTATE;
const pattern = "abcde";
const format = (n: number) =>
((n | 0) >>> 0).toString(2).padStart(32, "0").slice(
0,
Math.max(pattern.length, source.length) + 1,
);
const printTable = (state: number[]) =>
state.map((bit) => `\t${format(bit)}`).reverse().join("\n");
console.log(printTable(state));
for (const char of pattern) {
state = moveState(char, pats[0], pats[1], state);
console.log(
`input ${char}\t${format(pats[0].get(char) ?? 0)}`,
);
console.log(printTable(state));
}
console.log(
`accept \t${format(pats[2])}`,
);
console.log(state.map((bit) => (bit & pats[2]) !== 0).reverse());
最後の受理判定は確かに正しかった
いや、問題ないのか？
受理判定は問題なさそう
双方のbitがともに 1 である桁が少なくとも1つあれば (bit & pats[2]) !== 0 が true になる
14:07:45 わかった。ゼロ埋めに失敗していたんだ
以下の例なら、最大桁数の8でゼロ埋めしないといけない
txt10000000
1000000
100000
さもないと先頭が全て1になってしまう
14:12:14 コードを直した