Regular Expression to NFA, NFA to DFA Conversion Algorithm.

DFA.js

class State {
  constructor(name) {
    this.name = name;
    this.transitions = {}; // Holds the transitions from this state
    this.isFinal = false; // Indicates whether this state is a final state
  }
}

class DFA {
  constructor() {
    this.states = []; // Holds all the states in the DFA
    this.startState = null; // The start state of the DFA
    this.alphabet = new Set(); // The alphabet of the DFA
  }

  createState(name) {
    const state = new State(name); // Create a new state with the given name
    this.states.push(state); // Add the state to the list of states in the DFA
    return state;
  }

  setStartState(state) {
    this.startState = state; // Set the given state as the start state of the DFA
  }

  setFinalState(state) {
    state.isFinal = true; // Mark the given state as a final state
  }
}

function regexToDFA(regex) {
  const dfa = new DFA(); // Create a new DFA instance
  const startState = dfa.createState(0); // Create the start state of the DFA
  dfa.setStartState(startState); // Set the start state of the DFA
  dfa.setFinalState(startState); // Mark the start state as a final state

  let currentState = startState; // Initialize the current state to the start state

  for (let i = 0; i < regex.length; i++) {
    const symbol = regex[i]; // Get the current symbol from the regular expression

    if (symbol === '(') {
      // If the symbol is an opening parenthesis, create a new state and transition to it
      const newState = dfa.createState(i + 1);
      currentState.transitions[null] = newState;
      currentState = newState;
    } else if (symbol === '|') {
      // If the symbol is a pipe, create a new state and transition back to the start state
      const newState = dfa.createState(i + 1);
      currentState = dfa.startState;
      currentState.transitions[null] = newState;
      currentState = newState;
    } else if (symbol === ')') {
      // If the symbol is a closing parenthesis, transition back to the start state
      currentState = dfa.startState;
    } else if (symbol === '*') {
      // If the symbol is an asterisk, create a new state and make it loop back to the current state
      const newState = dfa.createState(i + 1);
      currentState.transitions[null] = newState;
      newState.transitions[null] = currentState;
      currentState = newState;
    } else {
      // If the symbol is a regular character, create a new state and transition to it
      const newState = dfa.createState(i + 1);
      currentState.transitions[symbol] = newState;
      currentState = newState;
      dfa.alphabet.add(symbol); // Add the symbol to the DFA's alphabet
    }
  }

  return dfa; // Return the constructed DFA
}

function printFancyDFA(dfa) {
  console.log("\nNumber of NFA States: " + (regex.length + 1));
  console.log("Number of DFA States: " + dfa.states.length);

  console.log("\nDFA States:");
  console.log("──────────────");

  for (const state of dfa.states) {
    let stateString = `State ${state.name}`;
    if (state.isFinal) {
      stateString += " (Final)";
    }
    console.log(stateString);
  }

  console.log("\nDFA Start State:", dfa.startState.name);
  console.log("DFA Alphabet:", Array.from(dfa.alphabet));
}

// Example usage
const regex = "(a|b)*ca*";
const dfa = regexToDFA(regex);

console.log("\nRegular Expression:", regex);
console.log("\n");
console.log("DFA States:", dfa.states.map((state) => state.name));

printFancyDFA(dfa);

Converted to Python

class State:
    def __init__(self, name):
        self.name = name
        self.transitions = {}  # Holds the transitions from this state
        self.isFinal = False  # Indicates whether this state is a final state


class DFA:
    def __init__(self):
        self.states = []  # Holds all the states in the DFA
        self.startState = None  # The start state of the DFA
        self.alphabet = set()  # The alphabet of the DFA

    def createState(self, name):
        state = State(name)  # Create a new state with the given name
        self.states.append(state)  # Add the state to the list of states in the DFA
        return state

    def setStartState(self, state):
        self.startState = state  # Set the given state as the start state of the DFA

    def setFinalState(self, state):
        state.isFinal = True  # Mark the given state as a final state


def regexToDFA(regex):
    dfa = DFA()  # Create a new DFA instance
    startState = dfa.createState(0)  # Create the start state of the DFA
    dfa.setStartState(startState)  # Set the start state of the DFA
    dfa.setFinalState(startState)  # Mark the start state as a final state

    currentState = startState  # Initialize the current state to the start state

    for i in range(len(regex)):
        symbol = regex[i]  # Get the current symbol from the regular expression

        if symbol == '(':
            # If the symbol is an opening parenthesis, create a new state and transition to it
            newState = dfa.createState(i + 1)
            currentState.transitions[None] = newState
            currentState = newState
        elif symbol == '|':
            # If the symbol is a pipe, create a new state and transition back to the start state
            newState = dfa.createState(i + 1)
            currentState = dfa.startState
            currentState.transitions[None] = newState
            currentState = newState
        elif symbol == ')':
            # If the symbol is a closing parenthesis, transition back to the start state
            currentState = dfa.startState
        elif symbol == '*':
            # If the symbol is an asterisk, create a new state and make it loop back to the current state
            newState = dfa.createState(i + 1)
            currentState.transitions[None] = newState
            newState.transitions[None] = currentState
            currentState = newState
        else:
            # If the symbol is a regular character, create a new state and transition to it
            newState = dfa.createState(i + 1)
            currentState.transitions[symbol] = newState
            currentState = newState
            dfa.alphabet.add(symbol)  # Add the symbol to the DFA's alphabet

    return dfa  # Return the constructed DFA


def printFancyDFA(dfa):
    print("\nNumber of NFA States:", len(dfa.states) + 1)
    print("Number of DFA States:", len(dfa.states))

    print("\nDFA States:")
    print("──────────────")

    for state in dfa.states:
        stateString = f"State {state.name}"
        if state.isFinal:
            stateString += " (Final)"
        print(stateString)

    print("\nDFA Start State:", dfa.startState.name)
    print("DFA Alphabet:", list(dfa.alphabet))


# Example usage
regex = "(a|b)*ca*"
dfa = regexToDFA(regex)

print("\nRegular Expression:", regex)
print("\n")
print("DFA States:", [state.name for state in dfa.states])

printFancyDFA(dfa)