  The emergence of intelligence in large language models (LLMs) has inspired
investigations into their integration into automata learning. This paper
introduces the probabilistic Minimally Adequate Teacher (pMAT) formulation,
which leverages a probabilistic oracle that could give persistent errors
randomly during answering the membership queries for deterministic finite
automata (DFA) learning. Given the tendency of LLMs to produce hallucinatory
content, we have developed techniques to improve answer accuracy and ensure the
correctness of the learned automata. We propose the $\mathtt{Discrimination}$
prompt as well as the $\mathtt{Verification}$ prompt and explore their
advantages over common prompts. Additionally, we compare DFA learning
performance between the TTT algorithm and common active learning algorithms. To
address the exponential number of persistent errors, we implement a dynamic
query cache refinement algorithm that identifies and corrects conflicting
queries by combining the active and passive learning algorithms. The empirical
results demonstrate the robustness and efficiency of our approach, providing a
theoretical foundation for automata learning with LLMs in the loop.
