Brzozowski's DFA minification in JavaScript

brzozowski.ts

type Dfa<Tag> = {
    trans: Map<string, [Tag, string][]>;
    initial: string[];
    final: string[];
}

const invertEdges = <Tag,>(auto: Dfa<Tag>): Dfa<Tag> => {
    const trans = new Map<string, [Tag, string][]>();
    for (const [from] of auto.trans) {
        trans.set(from, []);
    }
    for (const [from, edges] of auto.trans) {
        for (const [tag, to] of edges) {
            trans.get(to)?.push([tag, from]);
        }
    }
    return {
        trans,
        initial: auto.final,
        final: auto.initial,
    };
};

const dedup = (arr: string[]): string => {
    return [...new Set(arr.join('').split(''))].sort().join('')
};

const rabinScott = <Tag,>({initial, final, trans}: Dfa<Tag>): Dfa<Tag> => {
    const ntrans = new Map<string, [Tag, string][]>();
    const nfinal = new Set<string>();
    const rec = (vs: string[]) => {
        const st = dedup(vs);
        if (vs.some(v => final.includes(v))) {
            nfinal.add(st);
        }
        if (ntrans.has(st)) return st;
        const edges: [Tag, string][] = [];
        ntrans.set(st, edges);
        const tagTo = new Map<Tag, string[]>();
        for (const from of vs) {
            for (const [tag, to] of trans.get(from) || []) {
                const arr = tagTo.get(tag) || [];
                tagTo.set(tag, arr);
                arr.push(to);
            }
        }
        for (const [tag, tos] of tagTo) {
            edges.push([tag, rec(tos)]);
        }
        return st;
    };
    return {
        trans: ntrans,
        initial: [rec(initial)],
        final: [...nfinal],
    };
};

const brzozowski = <Tag,>(auto: Dfa<Tag>) => {
    const r1 = invertEdges(auto);
    const r2 = rabinScott(r1);
    const r3 = invertEdges(r2);
    const r4 = rabinScott(r3);
    return r4;
};

const prnt = <Tag,>({initial, final, trans}: Dfa<Tag>) => {
    console.log('initial', JSON.stringify(initial));
    console.log('final', JSON.stringify(final));
    for (const [from, tos] of trans) {
        console.log(from, JSON.stringify(tos));
    }
};

// 'I' | 'A' | 'B' | 'C' | 'D' | 'F', 
const test: Dfa<'a' | 'b' | 'c'> = {
    trans: new Map([
        // a(ac*|b*a)d
        ['I', [['a', 'A']]],
        ['A', [['a', 'B'], ['b', 'C']]],
        ['B', [['c', 'D'], ['b', 'F']]],
        ['C', [['a', 'D'], ['b', 'A']]],
        ['D', [['c', 'B'], ['b', 'F']]],
        ['F', []],
    ]),
    initial: ['I'],
    final: ['F'],
};

prnt(brzozowski(test));