Success occurs when the machine rolls off the right in a final state. Equivalently, success occurs when the machine enters a final state. Let's see why these are the same.
If an fsm succeeds by entering one of several final states, you can always have it remain in this final state and eat symbols, moving to the right, until the word is finished. Conversely, let an fsm succeed by entering a final state after reading the last symbol. Build a new fsm from the original as follows. Given an input word, append a new symbol, EOS (end of string), and let each of the preexisting final states, on EOS, enter a new final state, which is the final state. Any other state combines with EOS to produce a new state q1 moving left. And q1 on any symbol leads to state q2 and moves right. Of course q2 on EOS moves left and puts you back in q1. Thus, if the machine falls off the right in any state that was not considered final in the original machine, it falls into an infinite loop, and never reaches the new, final state.
The machine must not fall off the left end either, or if you prefer, prepend a new symbol BOS (beginning of string) to the left of the word, and add two new states q3 and q4, as we did above, so the machine is trapped in an infinite loop if it falls off the left.
Two way fsms are no more powerful than their one way cousins. In other words, the language accepted by a two way fsm is a regular language. Given a two way fsm, we will construct a nondeterministic fsm that accepts the same language, and since this is equivalent to a deterministic fsm, the language is regular.
Let a two way fsm accept a given string. Focus in on two adjacent letters XY. Consider the state of the machine as it moves from X to Y for the first time. Write this state down. Then write down the state of the machine when it moves from Y back to X. Then write down the state when it moves from X to Y, and so on.
If the machine is in state s, as it moves from X to Y, and later on in the sequence it is once again in state s, going from X to Y, then it has fallen into an infinite loop. The word is not in the language. So we may assume that the states in positions 1 3 5 7 etc in the sequence, as the fsm moves from X to Y, are all distinct, and similarly, the states in positions 2 4 6 8 etc, as the fsm moves from Y back to X, are distinct. If the machine has n states, each crossing sequence has length ≤ 2n.
How many crossing sequences are possible? Each sequence should be odd. If it is even then we moved off to the left, never to return. The machine cannot roll off the right in a final state. The word would not be accepted, hence we will assume all sequences have odd lengths. And the odd members are distinct, and the even members are distinct. Combinatorics will give you the answer, but it doesn't really matter. The point is, there are a finite number of "legal" crossings. If each of these crossing sequences becomes a state, we are building a new fsm. Actually our new states will be the legal crossings combined with the letters of the alphabet. This is still finite.
If c is a crossing sequence heading out of X, from X to Y for example, and d is another sequence heading out of Y, from Y to Z for example, do the two sequences c and d "link"? Could these crossings coexist?
Let s be the first state in c, hence the machine left X in state s and wound up on Y, in state t. We know where to go from here. Y in state t moves to state u, and heads right or left. If the machine heads left, then t has to be the next state in the crossing c. If it isn't, then Y,d cannot follow from X,c. In fact Y and any crossing cannot follow X,c. If Y,d follows X,c, then c begins with s and t. And we have to ask what happens to the machine in state u, reading X. If it moves left we really can't say anything more about c; but if it moves right then the third entry in c is u, and we must validate u, just as we did with s.
On the other hand, Y in state t might move to state u heading right. In this case the first entry in d must be t. If this fails we cannot have X,c leading to Y,d.
At this point we have established the second entry in c, or the first entry in d. If the former, we may have also established the third entry in c, and perhaps the fourth. Finally we have constrained an even number of entries in c, or, an odd number of entries in c and the first entry in d. From here it is more of the same. If the machine was last seen heading left, having validated an even number of entries in c, then it's time to look at the next entry in c. Follow its constraints, just as we did with state s. If the machine sailed off to the right of Y, look at the next entry in d. We were in some state, on some letter to the right of Y, and we moved back to Y, and are living in a new state, which I will call w. Does the machine, in state w, reading Y, move right? If so, there's nothing wrong with d. Nothing that we can see so far anyways. But if it moves left then we have determined the next entry in c. Begin the validation process again. Continue in this manner until something fails, or both sequences terminate. If c is complete, and the last state of d has also been validated, moving right, then X,c can inddeed lead to Y,d.
The states of our new machine are tuples of the form X,c, where X is a letter of the alphabet and c is an odd length crossing whose even and odd states are distinct.
The start state is ∅,[s], where s is the start state of the original machine. The first crossing, from the left edge of the word onto its first letter, began in state s, and always winds up in state s, no matter the first letter. This mirrors the original machine, which starts in state s when it looks at the first letter. Since the machine never falls off the left edge of the word, the initial sequence has length one, and consists only of s. The special symbol ∅ means we haven't read any letters yet.
The constructed state X,c will be considered a final state if c has length 1, and X, on this state, moves right into a final state. I imagine ∅,[s] could be a final state, if s was a final state in the original machine. Thus both machines accept the null string.
Ok, what are the transitions? Let X,c, reading Y, move to state Y,d, and advance to the next letter, if X,c and Y,d are compatible, as described above. These are the transitions of the new machine. As you might guess, there may be many ways to move from X,c onto y. For instance, Y,d and Y,e could both be compatible with X,c. Thus we have built a nondeterministic fsm.
It is pretty clear that a word accepted by the original 2 way fsm produces a chain of compatible crossings, and is therefore accepted by our new fsm. Conversely, assume a word is accepted by our new fsm. There is at least one chain of compatible crossing sequences. In fact there is only one, since the original fsm was deterministic. The two way fsm follows the dictates of these crossings. Each transition of the two way fsm is legal, because the crossings on either side of the transition are compatible. I'm glossing over the details of a rigorous inductive proof here, but I think you can see that our new fsm accepts the same language as the original two way fsm.
But wait - what if the original, two way fsm was nondeterministic? This really doesn't change things very much. It just means more crossings are compatible. When you consider X,c and Y,d, they will be compatible if there are any transitions, involving X and Y and the states of c and d, that would make them compatible in the prior sense. Again we find a nondeterministic machine that accepts the same language, and the language is regular.