FA Simulation Algorithm issue

Question

I have this Grammar, which my professor gave me. It's set to recognize strings defined by a Finite State Automaton. it should be transformed to recognize the longest valid prefix of the input.

//This would output valid if the whole string is valid not the longest

read input;
state = init;
while not end of input
{
  state = move(state,symbol);
  readnextInput();
}
if state is in (F):Final States print (valid);
else print(invalid);

I tried to append "& state is in (F)" to the while condition. But that will recognize to the shortest valid prefix.

What can be the problem here? Should I define a stack and push each string when it reaches a final state and pop the last one as a solution?

Answer 1

Are you trying to match the signatures using finite automaton?? if it is so then this paper may be helpful for you as I did it for multiple pattern searching.