Algorithms for testing equivalence of finite automata, with a grading tool for JFLAP

Show full item record

Title: Algorithms for testing equivalence of finite automata, with a grading tool for JFLAP
Author: Norton, Daphne
Abstract: A wide variety of algorithms can be used to determine the equivalence of two Deterministic Finite Automata (DFAs) and/or Nondeterministic Finite Automata (NFAs). This project focuses on three key areas: 1. A detailed discussion of several algorithms that can be used to prove the equivalence of two DFAs (and/or NFAs, since every NFA has an equivalent DFA), with an analysis of the time complexity involved in each case. 2. Modifications to a few of these algorithms to produce a 'witness' string if the two automata are not equivalent. This string is accepted by one of the automata, but not by the other, so it serves as a clear demonstration of why the two automata are inequivalent. 3. A Java implementation of a couple of efficient algorithms to prove equivalence. The code is designed specially to work with JFLAP, the Java Formal Language and Automata Package. JFLAP is a popular program from Duke University which can be used to demonstrate and manipulate models such as finite automata. JFLAP software allows students to enter finite automata via an easy-to-use GUI, and this project incorporates functionality so that instructors can grade homework assignments and/or allow students to receive detailed feedback in the form of a witness
Record URI: http://hdl.handle.net/1850/8712
Date: 2009

Files in this item

Files Size Format View Description
DNortonMastersProject03-2009.pdf 508.7Kb PDF View/Open Masters Project
DNortonUsersGuide02-2008.pdf 124.3Kb PDF View/Open Users Guide

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse