Lecture 4 question: FSA example

Lecture 4 question: FSA example

par Mike Yan Michelis,
Nombre de réponses : 2

Good afternoon!

I have a question about the example on slide 22 of the Out-of-Vocabulary lecture: we see that there are 3 solutions given, but wouldn't "aba" and "bab" also be outputs of the algorithm as described in slide 21 (I guess epsilon would also be an output)?

As far as I see, they are in terminal states of the FSA and the cut-off is also under the threshold. Is it because their distance to X is larger, and hence we don't consider them as solutions?

Thank you for your time!

En réponse à Mike Yan Michelis

Re: Lecture 4 question: FSA example

par Jean-Cédric Chappelier,

> Is it because their distance to X is larger, and hence we don't consider them as solutions?

Indeed, they are not solution at distance smaller or equal to \theta (which is 1).
This is clear from the definition of the task (distance to X is 2).
Regarding the algorithm, it is not added to solutions due to the ``D(X , Y ) ≤ \theta'' in the last ``if''.

> I guess epsilon would also be an output

I don't understand that.
Are you talking about the empty string? It's not a solution either.