by 40 Thieves.
Created 2003-12-09, 974 BMT.
Updated 2003-12-11, 352 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.
XxMeowPurrHissxX: damn i hate the weather outside
Evil Adam: yeah
Evil Adam: its like dionne warwick out there
Evil Adam: all ugly
-added 2004-03-09