Lecture 4 question: FSA example

Lecture 4 question: FSA example

by Mike Yan Michelis -
Number of replies: 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!

In reply to Mike Yan Michelis

Re: Lecture 4 question: FSA example

by 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.
In reply to Jean-Cédric Chappelier

Re: Lecture 4 question: FSA example

by Mike Yan Michelis -
I seem to have completely overlooked the last if-statement... Thank you very much for your answer and clearing it up!