Skip to content

The Public API of the Finite Automata Classes (NFA and DFA)

Jump to bottom
NBKlepp edited this page Jun 11, 2018 · 8 revisions

The core of the TheoryAssistant package is the representation of the Deterministic Finite Automaton (DFA) and Non-deterministic Finite Automaton (NFA) found in the classes of the same name. The public API for those classes includes constructors and various other methods useful in the design, analysis and evaluation of formal languages.

There are several instance methods in the public API for the NFA and DFA classes which a user may find useful. The following is a description of some of those useful methods.

The Public API of the NFA and DFA Classes

  1. Compute : The compute method takes a string as a parameter and returns a boolean value: true if the calling machine accepts the string and false otherwise.

  2. ComputeRecord : The compute record method returns the same information as the compute method, as well as the computational history of computing the string on the machine.

  3. Equals : The equals method takes another finite automaton as a parameter and returns a boolean value: true if the calling machine recognizes the same language as the parameter machine, and false otherwise.

  4. Complement : The complement method is callable on a finite automaton and returns a new finite automaton which recognizes the complement of the language of the calling machine over its alphabet. For instance, if the calling machine is a DFA which recognizes all strings over {0,1} with an even number of characters, then the return value would be a DFA which recognizes all strings over {0,1} with an odd number of characters. The type of the finite automaton returned by a call to complement is the same as the calling object.

  5. Union : The union method takes as a parameter another finite automaton and returns an automaton which recognizes the union of the language of the calling machine and the language of the parameter machine.

  6. Intersect : The intersect method takes as a parameter another finite automaton and returns an automaton which recognizes the intersection of the language the calling machine and the language of the parameter machine.

  7. Concat : The concat method takes as a parameter another finite automaton and returns an automaton which recognizes the concatenation of the language of the calling machine and the language of the parameter machine.

  8. RecognizesEmptyLanguage : This method is callable on a finite automaton and returns a boolean value: true if the language of the machine is the empty set and false otherwise.

  9. DFAify() : This method is callable on a finite automaton and returns a new DFA object which recognizes the same language as the calling object.

  10. toString() : a toString() method is implemented which displays the individual members of the 5-tuple which define a finite automaton in verbose format. See the page describing the GrafState syntax for clarification on how the toString() is printed.

Next Steps

Next up, take a look at the simplified syntax for describing DFAs and NFAs.

Clone this wiki locally