-
Notifications
You must be signed in to change notification settings - Fork 23
Description
"NFATextMatch" function with recursive algorithm. But if enter "((ba)*|dd)a" regular expression and enter text like "ddd" the program exit when find first "d" in 10th state. If the program can return 0. state and continue with 2. state can be match the input string and return true.
Could you help me?
The code:
FSM.prototype.totalTextCounter=0;
FSM.prototype.lenghtOfInput = 0;
// Match the input according to NFA.s
FSM.prototype.NFATextMatch= function(inputElement,transitionNumber)
{
epsilons = [];
// Equal accept state.
if(transitionNumber==parseInt(this.acceptStates[0])){
return -1;
}
let len = Object.values(this.transitions[transitionNumber]).length;
for(let i =0; i < len; i++){
if(inputElement=== Object.values(this.transitions[transitionNumber])[i]){
// Return state's number.
return parseInt(Object.keys(this.transitions[transitionNumber])[i])
}
else if(Object.values(this.transitions[transitionNumber])[i]=="ε"){
epsilons.push(parseInt(Object.keys(this.transitions[transitionNumber])[i]));
}
else{
return -1;
}
}
let returnNumber= 0;
let epsilonsNumber = epsilons.length;
// Copy the epsilones' array.
let testTemp = epsilons.slice();
for(let i =0; i< epsilonsNumber;i++){
returnNumber = this.NFATextMatch(inputElement,parseInt(testTemp[i]));
if(returnNumber != -1){
return returnNumber;
}
}
return -1;
}
// Test accesed last state(according to NFATextMatch function) equivalent accept state or go acces state with epsilons.
FSM.prototype.accesAcceptStateNFA = function(currentState,acceptState, indexOfInput){
//Keep can go states with epsilon.
finalEpsilons=[];
var findEpsilon = false;
let len =Object.values(this.transitions[currentState]).length;
for(let i =0; i<len;i++){
if(Object.values(this.transitions[currentState])[i] =="ε" ){
var findEpsilon = true;
if(parseInt(Object.keys(this.transitions[currentState])[i])==acceptState){
return parseInt(Object.keys(this.transitions[currentState])[i]);
}
else{
finalEpsilons.push(parseInt(Object.keys(this.transitions[currentState])[i]))
}
}
if((parseInt(Object.keys(this.transitions[currentState])[i])==acceptState)){
return parseInt(Object.keys(this.transitions[currentState])[i]);
}
}
if(findEpsilon == false){
return -1;
}
let finalReturnNumber = 0;
let finalEpsilonsNumber = finalEpsilons.length;
let temp = finalEpsilons.slice();
for(let i = 0;i<finalEpsilonsNumber;i++){
finalReturnNumber = this.accesAcceptStateNFA(parseInt(temp[i]),acceptState);
}
if(finalReturnNumber == acceptState && this.lenghtOfInput == indexOfInput + 1){
return finalReturnNumber;
}
}
// Match input text according to Nondeterministic Finite Automata(NFA).
FSM.prototype.matchNFA = function(text) {
this.lenghtOfInput = text.length;
// textLength = text.length;
let acceptState= parseInt(this.acceptStates[0]);
// "number" variable keep return NFATextMatch's function value.
let number =0;
for(let j =0; j < text.length; j++){
number = this.NFATextMatch(text[j],number);
if(number === -1){
alert("Not Matched!!");
return false;
}
else
{
this.totalTextCounter=j;
}
}
if(number != -1 && number==acceptState){
alert("Matched!!");
return true;
}
// If text's matched state not equivalent accept state or can go accept state with epsilons.
else if(number != -1 && number!= acceptState){
let FinalState = this.accesAcceptStateNFA(number,acceptState)
if(FinalState == acceptState){
alert("Matched!!");
return true;
}
else{
alert("Not Matched!!");
return false;
}
}
}