Exploring a Residual Language Learning Algorithm Through the Lens of L* and Reversal Alternation

Residuality Theory has recently emerged as a powerful framework for understanding the learning of formal languages. It enriches regular languages with linguistic meaning and reveals deeper semantic layers inherent in their structure. Alternation Theory, where existential and universal quantifiers interchange during computation, offers a succinct and expressive representation of regular languages. In this paper, we investigate how residuality and reversal alternation influence the learning of regular languages, with a foundation grounded in Angluin’s L* algorithm. Building on these theoretical perspectives, we introduce a trilateral canonical framework called Learner-Teacher-Expert (LTEx), which incorporates an extended and diverse query set. This leads to the development of a new polynomialtime learning algorithm, the Residual Reversal-Alternating (RAL*) for learning regular languages. We demonstrate that the integration of residuality, reversal alternation, and L* enables the learning of extended regular languages and facilitates their representation as a family of structured finite-state machines called Residual Alternating Finite Automata (RAFA). Finally, we reflect on these constructs as conceptual metaphors, proposing them as potential avenues for further research in formal language learning.