Undergraduate Honors Thesis Defense-Power and Limitations of Computing with Finite Automata

Title: Power and Limitations of Computing with Finite Automata
Speaker: Abigail Stein
Date and Time: Wednesday, April 29, 2:20 pm

Place: 1776 G Street, Room C-101

Abstract: We investigate the power and limitations of computation formalized by finite automata, a foundational model of computation characterized by an arbitrary finite set of states but very limited memory. We present deterministic, nondeterministic, and generalized finite automata, and establish the equivalence between deterministic and nondeterministic models. We further develop various frameworks for corresponding regular languages. Regular expressions are presented as an alternative formalism for describing Chomsky’s regular languages, and key closure properties—such as union, concatenation, and intersection—are examined. We further explore the limitations of regular languages using the pumping lemma, providing a method to demonstrate non-regularity. Central to our study is the Myhill-Nerode theorem, which offers a precise characterization of regular languages and a framework for proving minimality of finite automata. We extend this theorem to generalized automata, addressing settings beyond the classical framework. What distinguishes our study is its integration of both classical results and modern generalizations, particularly the extension of the Myhill-Nerode theorem to generalized automata, presented in a unified and rigorous way. Through a series of examples and non-examples, we illustrate both the expressive capabilities and inherent constraints of finite automata, concluding that while they are computationally efficient and widely applicable, their expressive power is fundamentally limited.