CS 3723  Programming Languages
Simulating an FA

• Simulating a DFA: In a language with labels and gotos, this is easy. Each state becomes a labeled location in a simulation program, and each arrow becomes a goto between the two labeled locations that correspond to the two states. You start at the location corresponding to the start state. You accept if you are in an accepting state (or terminal state) at the end of the string being processed. All this is illustrated first with programs in C and Java to recognize the language described in the image above, the one described by the regular expression (a|b)*abb: abb.

  A more complex example is given by programs (also in C and Java) to recognize C-style comments, such as:

  ( /* here's one */ )

  Comments. One C program uses gotos, while the Java program uses a while-switch since gotos are not available in Java. (Some instructor don't allow gotos in a course even if they are available.).

• Simulating an NFA: As you process each input character, your simulating program should keep track of the set of all possible states that you might be in. You start out with the singleton set {start state}. At the end of the input string, if your set of states includes a terminal state, then you accept. Otherwise you reject. This same process is essentially the "subset algorithm" that lets one take an NFA and construct a DFA that accepts the same language as the NFA.

See the Subset Algorithm.