I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) that necessitates ( n-1 ) equivalence queries for the L* algorithm to correctly learn the automaton.

The L* algorithm operates by building an observation table and using membership and equivalence queries to fill out and correct this table. In each round, the algorithm proposes a hypothesis automaton based on the current observation table. If the hypothesis is incorrect, an equivalence query will provide a counterexample, which is then used to update the table for the next round.

I have been able to construct such DFAs manually for small ( n ) (up to 7), with each automaton requiring one less round than the number of states to be learned. However, I'm struggling to generalize this construction for arbitrary ( n ). Here is the progression pattern I've observed for my DFAs so far (also the observation table for the last hypothesis):

I am looking for a systematic method to create such DFAs for any given ( n ), ensuring the L* algorithm requires ( n-1 ) rounds to learn the DFA. How can this be achieved? Is there a general pattern or formula that can be applied to construct these DFAs?

The approach I am currently working on:

Given a closed and determinstic observationtable

How can we construct a violation in closedness by adding an element to the prefix set (upper row set) such that when resolving the violation by adding a new suffix to the suffix set no new violation in closedness or determinism occurs.

s d a ss qqq aa




Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.