TypeScript implementation of a simple DFA(Deterministic Finite Automata) and NFA(Non-deterministic Finite Automata).

dfa.ts

export type StateId = number
export type Char = '0' | '1'

export interface DFA {
    statesNumber: number
    rules: Record<Char, StateId>[]
    startState: StateId
    acceptStates: StateId[]
}

export function runDFA(dfa: DFA, s: Char[] | string): boolean {
    let state = dfa.startState
    for (const c of s) {
        state = dfa.rules[state][c as Char]
    }
    return dfa.acceptStates.includes(state)
}

nfa.ts

export type StateId = number
export type Char = '0' | '1'
export const EPSILON = Symbol()

export interface NFA {
    statesNumber: number
    rules: Record<StateId, Partial<Record<Char | typeof EPSILON, StateId[]>>>
    startState: StateId
    acceptStates: StateId[]
}

function computeEpsilonClosure(nfa: NFA, sid: StateId): StateId[] {
    const result = [] as StateId[]
    const stack = [sid] as StateId[]
    const dup = { [sid]: true } as Record<StateId, boolean>
    
    while (stack.length) {
        const sid = stack.pop()!
        result.push(sid)

        nfa.rules[sid][EPSILON]?.forEach(neighbor => {
            if (dup[neighbor]) return
            dup[neighbor] = true
            stack.push(neighbor)
        })
    }
    
    return result
}

export function runNFA(nfa: NFA, s: Char[] | string): boolean {
    const epsilonClosures = Array.from(new Array(nfa.statesNumber), (_, sid) => computeEpsilonClosure(nfa, sid))
    
    let currentStates = Array.from(new Array(nfa.statesNumber), () => false)
    epsilonClosures[nfa.startState].forEach(sid => currentStates[sid] = true)

    for (const c of s) {
        const nextStates = currentStates.map(() => false)
        
        currentStates.forEach((isActive, sid) => {
            if (!isActive) return

            epsilonClosures[sid].forEach(sid => {
                // conditioned transition
                nfa.rules[sid][c as Char]?.forEach(nid => nextStates[nid] = true)

                // apply epsilon transition
                nfa.rules[sid][EPSILON]?.forEach(nid => nextStates[nid] = true)
            })
        })

        currentStates = nextStates
    }
    return nfa.acceptStates.some(ac => currentStates[ac])
}

Strict forward implementation for DFA and NFA. Both can recognize any regular languages.

Actually NFA is more practical since they are equivalent. Here's because why. DFA may consumes O(2^N) memory at worst case, while NFA consumes O(N) for same given Regular Expression of length N. Note that this doesn't cache anything like Cox's implementation.