javascriptfinite-automatadeterministic

How do I make a string validator for Deterministic Finite Automata?


The regular expression for the DFA that I need to validate a string with is (bab | bbb) (a* b*) (a* | b*) (ba)* (aba) (bab | aba)* bb (a | b)* (bab | aba) (a | b)*

I thought of using transitions to tell when an inputted string is valid or not:

class DFA_Exp1 {
    constructor() {
      // Define the transitions as an object
      this.transitions = {
        0: { a: "invalid", b: 1 },
        1: { a: 2, b: 2 },
        2: { a: "invalid", b: 3 },
        3: { a: 4, b: 5 },
        4: { a: 4, b: 6 },
        5: { a: 7, b: 5 },
        6: { a: 7, b: 5 },
        7: { a: 9, b: 8 },
        8: { a: 11, b: 12 },
        9: { a: "invalid", b: 10 },
        10: { a: 7, b: "invalid" },
        11: { a: "invalid", b: 7 },
        12: { a: 13, b: 15 },
        13: { a: "invalid", b: 14 },
        14: { a: 17, b: "invalid" },
        15: { a: 16, b: "invalid" },
        16: { a: "invalid", b: 17 },
        17: { a: 17, b: 17 },
        "invalid": { a: "invalid", b: "invalid" },
      };
  
      this.acceptingState = 17;
    }

    validateInput(input) {
        let currentState = 0; // Initial state
    
        for (let i = 0; i < input.length; i++) {
          const symbol = input[i];
    
          if (!this.transitions[currentState]) {
            return "invalid";
          }
    
          currentState = this.transitions[currentState][symbol];
    
          if (currentState === "invalid" || currentState === undefined) {
            return "invalid";
          }
        }

        if (currentState === this.acceptingState) {
            return "valid";
        }
        console.log(currentState);
        return "invalid";
        
    }  
}

It seems that I lack the knowledge of how to make transitions work because the currentState is always 0 and the string is always checked as invalid.

Is there a better way to do string validation or did I do something wrong with my validateInput method?

(I am very new to JavaScript and automata theory)


Solution

  • You can definitely use the regex to validate the string:

    const input = "bab";
    const dfa_regex = /^(bab | bbb) (a* b*) (a* | b*) (ba)* (aba) (bab | aba)* bb (a | b)* (bab | aba) (a | b)*$/;
    dfa_regex.exec(input);
    

    I have used the syntax with /s to define the regex, but it may be counter intuitive at first. You can also use the constructor (which is the same in the end, just more explicit)

    const dfa_regex = new RegExp("^(bab | bbb) (a* b*) (a* | b*) (ba)* (aba) (bab | aba)* bb (a | b)* (bab | aba) (a | b)*$");