# Dana Angluin's L* algorithm - Hypothesis inconsistent

is it possible for the Dana Angluin's L* algorithm that a hypothesis is inconsistent?

So assume we have a closded observation table for a regular language L. Now after creating the hypothesis we will get a counterexample w.

The Question is: Can the counterexample w be chosen in the hypothesis, so that I have two times the same counterexample?

Unfortunetaly I could not find any language and counterexample where it will work.

• What does "the counterexample w be chosen in the hypothesis" mean? I don't know what it would mean for a word to be chosen in the hypothesis. Here $w$ is a word, and the hypothesis is a DFA (a regular language). Also what would it mean for a hypothesis to be inconsistent?
– D.W.
May 9, 2019 at 17:12
• Example: 1. Hypothesis 2. Give a counterexample w 3. New Hypothesis 4. Same counterexample w
– Marc
May 9, 2019 at 19:10

The teacher returns a counterexample $$w$$. Here a hypothesis is a DFA (a regular language) and $$w$$ is a word that the DFA gets wrong (either the DFA accepts, but $$w$$ is actually not in the language to be learned; or the DFA rejects, but $$w$$ is actually in the language to be learned). Angluin's L* algorithm constructs a new DFA that is correct on all of the counterexamples that have been returned so far. Since this DFA is correct on all past counterexamples received from the teacher, we will definitely never get the same counterexample a second time.