Exploring Computational Models: Analysis, Extensions, and Novel Approaches in Automata Theory

Abstract

This thesis investigates the structure, limitations, and extensions of classical computational models, including finite automata, pushdown automata, and Turing machines. Motivated by the trade-off between expressive power and structural simplicity, it introduces a novel model called Counter-Based Finite Automata (CBFA). The proposed model extends deterministic finite automata by incorporating counters that accumulate quantitative information during computation while preserving finite-state control. Several variants of CBFA are formally defined and analyzed, including state-based, input-based, and transition-based models. The thesis establishes key theoretical results, such as linear-time membership and the ability to recognize certain non-context-free languages, while also identifying limitations of the model. Finally, it situates CBFA within the broader computational hierarchy and outlines future research directions, including extensions toward counter-based pushdown automata.