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

Show simple item record

dc.contributor.advisor Bezakova, Ivona
dc.contributor.advisor Homan, Christopher Norton, Daphne 2009-03-26T23:04:52Z 2009-03-26T23:04:52Z 2009
dc.description.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
dc.language.iso en_US
dc.subject Deterministic finite automata en_US
dc.subject DFA en_US
dc.subject Equivalence algorithms en_US
dc.subject Finite automaton en_US
dc.subject JFLAP en_US
dc.subject NFA en_US
dc.subject Nondeterministic finite automata en_US
dc.subject Witness string en_US
dc.title Algorithms for testing equivalence of finite automata, with a grading tool for JFLAP
dc.type Masters Project B. Thomas Golisano College of Computing and Information Sciences
dc.description.department Department of Computer Science
dc.contributor.advisorChair Hemaspaandra, Edith

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

This item appears in the following Collection(s)

Show simple item record

Search RIT DML

Advanced Search