TY  - JOUR
AU  - Aziz Fellah
PY  - 2025
DA  - 2025/08/20
TI  - Exploring a Residual Language Learning Algorithm Through the Lens of L* and Reversal Alternation
JO  - Japan Journal of Research
VL  - 6
IS  - 10
AB  - 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.
SN  - 2690-8077
UR  - https://dx.doi.org/10.33425/2690-8077.1204
DO  - 10.33425/2690-8077.1204