The scanner part of any program that processes a language is probably a DFA.
There are three main methods to code DFAs. Two use an explicit variable to represent state in this fashion: int state = INITIAL_STATE; while (!is_accepting_state(state)) { char ch = get_next_char(); state = transition(ch, state); if (state == ERROR_STATE) { take_error_action(); break; } } Now this is pseudocode. The question is how to implement transition(char ch, int state); Simplest way is with tables int transition[256][N_STATES]; boolean is_accepting[N_STATES]; The is_accepting[] array is normally fine. But the 2d array transition gets big quickly, especially if the number of possible input "characters" is high. So there are various "table compression schemes". Run length encoding of table rows is a common method. The other way to encode is nested switch statements. Finally - and you see this less often but it often results in the fastest DFAs: You use "goto" and use labels to represent state implicitly. For example, here is a simple DFA that recognizes floating point numbers. There are 4 possible input characters: '-', D, '.', '*' where D stands for a digit and * stands for any char that is not -,D, or . State 0 is the initial state: current '-' D '.' * 0 1 2 3 err 1 err 2 3 err 2 err 2 3 accept 3 err 4 err accept 4 err 4 err accept Code this with goto logic as follows: state0: switch (get_next_char()) { case '-': goto state1; case '0'...'9': goto state2; case '.': goto state3; default: goto err; } state1: switch (get_next_char()) { } state2: switch (get_next_char()) { } state3: switch (get_next_char()) { } state4: switch (get_next_char()) { } accept: // accept action goes here return; err: // error action goes here return; Of course there are many variations on these 3, but the principles stay the same. On Apr 6, 1:39 pm, Doom <duman...@gmail.com> wrote: > Any pointers to a code using NFA / DFA computation model? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.