Loading...
Journal Title
Readers/Advisors
Suchy, Ashley, Easwaran, Chirakkal, Curry, Mike
Journal Title
Term and Year
Spring 2024
Publication Date
2024-05
Book Title
Publication Volume
Publication Issue
Publication Begin
Publication End
Number of pages
Collections
Files
Loading...
DeGennaro_Thesis.pdf
Adobe PDF, 341.13 KB
Research Projects
Organizational Units
Journal Issue
Abstract
In this thesis, we introduce algorithms for creating deterministic (DFA) and nondeterministic finite automata (NFA) for some common types of regular languages. The motivation for this work comes from studying problems students taking theory of com-putation classes encounter. When working with finite automata, there are patterns in the structures of automata that arise. This thesis seeks to generalize a subset of common problems by creating step-by-step constructions based on the distinguishing properties of the given language. Along with these algorithms, software has been developed to generate these automata based on their dis-tinguishing properties. This thesis aims to be the foundation for developing an educational tool for theory of computation students. The goal is to highlight the similarities and logic behind these common constructions, while also providing the visual aid of the constructed automata through the accompanying software. The problems we consider are: the Maximum Prefix-Suffix Overlap problem, the Substring problems, the X followed by Y problem, the Consecutive Character problems, the Conditional Counting Modulo n problems, the Regularly Repeated Characters problem, and the Contains X but not Y problem. All algorithms presented in this thesis are polynomial in runtime, and polynomial in space complexity. The Maximum-Prefix-Suffix Overlap problem has a linear runtime, and the Contains X but not Y problem is of special interest due to its space reduction from the ‘usual’ solution.
Citation
DOI
Description
Accessibility Statement
If this SOAR repository item is not accessible to you (e.g. able to be used in the context of a disability), please email libraryaccessibility@newpaltz.edu