Towards Persistent Noise-Tolerant Active Learning of Regular Languages with Class Query

Large Language Models (LLMs) are increasingly deployed in human-AI collaborative decision-making systems, where they are expected to align precise formal representations (e.g. temporal-logic monitors or reward machines for reinforcement learning) with ambiguous natural language. However, their ad hoc strategies for resolving ambiguity often lead to hallucinations and inconsistencies. We formalize this setting via probabilistic Minimally Adequate Teachers (pMATs) that (i) answer membership queries with fixed but possibly flipped labels, and (ii) return valid counterexamples to hypothesis equivalence. We present CAPAL (Class-query Active, Persistent-noise-Aware Learning), an active learning algorithm for learning deterministic finite automata (DFAs) without demonstrations and that remains correct under persistent noise in membership queries. CAPAL augments the classic L ⋆ loop with two components grounded in our implementation: (1) a class query realized as a statistical same-state test that compares disagreements between two prefixes against a noise-floor estimate η with Hoeffding tolerances; (2) a discrimination tree (DT) that selects a near-minimal discriminator, keeping the core suffix set small. An efficient micro-bootstrap and cache-reuse scheme estimates η with few new queries. We prove convergence given a perfect language-equivalence oracle and show substantial membership-query savings in practice. Our evaluation across multiple benchmarks, including RegexLib and KB13, demonstrates that this approach enhances both the efficiency and robustness of DFA learning under noisy oracles, supporting the view of LLMs as fallible yet useful collaborators for synthesizing verifiable formal artifacts.