I made use of the fact that "egrep -o [some regex]" will print the first (going left-to-right) match for the regex. So I ran egrep -o, and several other programs, once per line of input. (And to go from right to left, I used "rev" and an egrep on the reversed string.) My computer wept, but it worked.

  pbpaste | bash -c '
    tt=0
    while read x; do
      y=$(( 10 *
            $(echo $x |
              egrep -o "[0-9]|one|two|three|four|five|six|seven|eight|nine" |
              head -1 |
              sed -E "s/one/1/; s/two/2/; s/three/3/; s/four/4/; s/five/5/; s/six/6/; s/seven/7/; s/eight/8/; s/nine/9/")
          + $(echo $x |
              rev |
              egrep -o "[0-9]|eno|owt|eerht|ruof|evif|xis|neves|thgie|enin" |
              head -1 |
              rev |
              sed -E "s/one/1/; s/two/2/; s/three/3/; s/four/4/; s/five/5/; s/six/6/; s/seven/7/; s/eight/8/; s/nine/9/")))
      tt=$((tt+y))
    done
    echo $tt'

Sorry all, I misused the word finite state. I meant it more from a combinatorics viewpoint(e.g. we only have X amount of operations per Y interval). You could consider my solution to be brute force code.

Abstractly I do this:

  read_file()
  lines = read_lines()
  sum = 0
  while lines:
    left = get_first_num_forwards(line)
    right = get_first_num_backwards(line)
    sum += integer(left+right)
  return sum

I define get_first_num() something like this:

  get_first_num(line):
    lowest_index_pair = None
    for key,val in dict.values():
       get_index_of_key_if_exists()
       if_exists: update_lowest_index_pair()
    index,num find_first_instance_num() //just gets the first num that appears
    update_lowest_index_pair()
    return lowest_index_pair[1]//just returns the number

Basically the idea is very similar to yours. We parse each line 11 times in both direction(10 per the word_vals dict and once more to find the index of the first numerical) which is only 22 parses. Then we grab the minimum index from this list and concat with the opposite side.

I just don't do any replacements at the cost of a longer run time. But I figure the cost of 11 parses was low enough that it wouldnt impact the run time significantly for this exercise.

The key point is that overlaps are not an issue because we check for string comparisons in the methods

That's ok, you misused the word 'word' to apply to 'finite' and 'state' :-P.

lol you know how it goes :). The mind does what it does.