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

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.

Department dc:contributor.department

DE--Informatikai Kar

Author dc:creator

• Sayor, S M Sadman Sakib

Advisor dc:contributor.advisor

• Horváth, Géza

• Automata Theory
• Computational Models
• Counter-Based Finite Automata (CBFA)

Language dc:language.iso

en

Handle dc:identifier.uri

https://hdl.handle.net/2437/413377

OAI identifier oai:identifier

oai:dea.lib.unideb.hu:2437/413377