Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implemented match text with NFA but cause an error. #14

Open
savasturk opened this issue Nov 8, 2018 · 0 comments
Open

Implemented match text with NFA but cause an error. #14

savasturk opened this issue Nov 8, 2018 · 0 comments

Comments

@savasturk
Copy link

savasturk commented Nov 8, 2018

"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;
}
}
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant