by 40 Thieves.
Created 2003-12-09 015 BMT.
Updated 2003-12-11 394 BMT.
About the Program:
This program simulates the processing of an DFSA (Deterministic Finite State Automata) using C++. Allow the user to enter transitions and states in the format of ordered triples i.e. ("1 a 2"). In this case 1 is the starting state, a is the transition element and 2 is the ending state. The user also defines accepting states for the DFSA. The program then processes an input string from the user and outputs whether or not the string is valid according to the rules defined by the user.
Implementation:
The accepting states are stored in a linked list to allow for any number of states, and for optimal memory usage. The transition rules are stored using a modified binary tree structure to allow for any number of rules. The binay tree structure also limits the search time to allow for quick processing of the DFSA. The binary tree implementation also checks for duplicate rules and removes them to prevent any delay due to redundant rules.State (-1) is used as a trap state, where any conditions that do not conform to the user-defined rules of the DFSA will default to. The program does not allow states symbolized by negative numbers, so no DFSA can be written with this program to escape from the trap state. The number and name of states are implicitly defined by the rules that the user enters, and are not asked to be defined separately by the user.
The program can be downloaded here (zip format)
NOTE: This will probably be rewritten with the STL to make it smooth like a pickle
"Finite State Machine" is Copyright © 2003 40 Thieves. If you know otherwise, hollar.
Get off that Cross, use the wood to build a bridge and move on!
-Matey-O
-added 2002-01-28