0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Commented May 9, 2019 at 17:12
  • $\begingroup$ Example: 1. Hypothesis 2. Give a counterexample w 3. New Hypothesis 4. Same counterexample w $\endgroup$
    – Marc
    Commented May 9, 2019 at 19:10

1 Answer 1

Reset to default
1
$\begingroup$

I have no idea what it would mean for a hypothesis to be inconsistent in this context, but the answer to your second question is: No. You won't receive the same counterexample twice.

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.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.