正規表現のNFA（有向グラフ）をDFAに変換し、状態遷移表を出力するプログラム

nfaToDfa.js

// '_' indicates epsilon
// INPUT is directed graph of NFA

// (00|11)(00|11)*
const INPUT = {
    0: [['_', 1]],
    1: [['_', 2], ['_', 5]],
    2: [['0', 3]],
    3: [['0', 4]],
    4: [['_', 8]],
    5: [['1', 6]],
    6: [['1', 7]],
    7: [['_', 8]],
    8: [['_', 9]],
    9: [['_', 10], ['_', 18]],
    10: [['_', 11], ['_', 14]],
    11: [['0', 12]],
    12: [['0', 13]],
    13: [['_', 17]],
    14: [['1', 15]],
    15: [['1', 16]],
    16: [['_', 17]],
    17: [['_', 18], ['_', 10]],
    18: [['_', 19]],
    19: []
}

// Test input
const TEST = '001100';

// if output Dtran
const SHOW_DTRAN = false;

// if output Dstates
const SHOW_DSTATES = false;

// if output each step
const SHOW_STEPS = false;

// ======================================== //

// (array: number[], char: string, isMove: boolean) => number[]
const move = (array, char, isMove = true) => {
    const accept = (result, current) => {
        for (const element of INPUT[current]) {
            if (element[0] === char && !result.includes(element[1])) {
                result.push(element[1]);
                accept(result, element[1]);
            }
        }
    }

    let result = isMove ? [] : [...array];

    for (const element of array) {
        accept(result, element);
    }

    if (isMove) {
        for (const element of result) {
            const node = INPUT[element];
            const nextNode = node.find((n) => result.includes(n[1]));
            if (nextNode) {
                result = result.filter((r) => r !== nextNode[1]);
            }
        }
    }

    return result;
}

// (array: number[]) => number[]
const eClosure = (array) => {
    return move(array, '_', false);
}

const arrayEquals = (array1, array2) => {
    if (array1.length !== array2.length) {
        return false;
    }

    array1.sort((a, b) => a - b);
    array2.sort((a, b) => a - b);

    for (let i = 0; i < array1.length; i++) {
        if (array1[i] !== array2[i]) {
            return false;
        }
    }

    return true;
}

const inputValues = []
Object.values(INPUT).forEach((value) =>
    value.forEach((node) => {
        if (node[0] !== '_' && !inputValues.includes(node[0])) {
            inputValues.push(node[0]);
        }
    })
);
inputValues.sort();

const dTran = {};
const dStates = {};
let k = 'A'.charCodeAt(0);
dStates['A'] = {
    checked: false,
    array: eClosure([0]),
};

const step = (key) => {
    const state = dStates[key];
    state.checked = true;

    for (const value of inputValues) {
        const m = move(state.array, value);
        const u = eClosure(m);

        if (SHOW_STEPS) {
            console.log(key, value, m, u);
        }

        if (!Object.values(dStates).map((state) => state.array).some((array) => arrayEquals(array, u))) {
            k++;
            dStates[String.fromCharCode(k)] = {
                checked: false,
                array: u,
            }
        }

        dTran[`${key}_${value}`] = u;
    }

    const next = Object.entries(dStates).find(([_, v]) => !v.checked);
    if (next) {
        step(next[0]);
    }
}

step('A');

if (SHOW_DSTATES) {
    console.log('DStates', dStates);
}

if (SHOW_DTRAN) {
    console.log('Dtran', dTran);
}

Object.entries(dTran).forEach(([k, v]) => {
    const values = Object.entries(dStates).find(([_, vv]) => arrayEquals(vv.array, v));
    if (values) {
        // dTran[k] = values[1].array.length !== 0 ? values[0] : '-';
        dTran[k] = values[0];
    }
});

console.log(`|   | ${inputValues.join(' | ')} |`);
console.log(`|---|${inputValues.map((_) => '---').join('|')}|`);
Object.keys(dStates).forEach((key) => {
    console.log(`| ${key} | ${Object.entries(dTran).filter(([k, _]) => k.startsWith(key)).map(([k, v]) => v).join(' | ')} |`);
});

console.log();

const terminal = parseInt(Object.keys(INPUT)[Object.keys(INPUT).length - 1]);
console.log(`Accepted: ${Object.entries(dStates).filter(([_, v]) => v.array.includes(terminal)).map(([k, _]) => k).join(', ')}`)

console.log();

if (TEST) {
    const terminals = Object.entries(dStates).filter(([_, v]) => v.array.includes(terminal)).map(([k, _]) => k);

    console.log('==== TEST ====');
    console.log(`${'Test for'.padEnd(11, ' ')}: '${TEST}'`);
    console.log(`${'Accepted'.padEnd(11, ' ')}: [ ${terminals.join(', ')} ]`);

    let state = 'A';
    const states = [state];
    for (const char of Array.from(TEST)) {
        const next = dTran[`${state}_${char}`];
        states.push(next);
        if (!next) {
            console.log(`${'States'.padEnd(11, ' ')}: [ ${states.join(', ')} ]`);
            console.log(`${'Last State'.padEnd(11, ' ')}: ${state}`);
            console.log(`${'Result'.padEnd(11, ' ')}: *** Error ***`);
            break;
        } else {
            state = next;
        }
    }

    console.log(`${'States'.padEnd(11, ' ')}: [ ${states.join(', ')} ]`);
    console.log(`${'Last State'.padEnd(11, ' ')}: ${state}`);

    if (terminals.includes(state)) {
        console.log(`${'Result'.padEnd(11, ' ')}: * Passed`);
    } else {
        console.log(`${'Result'.padEnd(11, ' ')}: *** Error ***`);
    }
}

output.txt

|   | 0 | 1 |
|---|---|---|
| A | B | C |
| B | D | E |
| C | E | F |
| D | G | H |
| E | E | E |
| F | G | H |
| G | I | E |
| H | E | J |
| I | G | H |
| J | G | H |

Accepted: D, F, I, J

==== TEST ====
Test for   : '001100'
Accepted   : [ D, F, I, J ]
States     : [ A, B, D, H, J, G, I ]
Last State : I
Result     : * Passed