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)
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)*$");