With FSA, every word is either accepted or rejected. It’s a hard switch. This is where weighted FSA comes in. Rather than a hard switch, we ask how acceptable is a word is. Weighted FSAs (WFSAs) are generalisation of FSAs, in which each accepting path has a score, computed using the transitions, initial state, and the final state.

A WFSA consists of:

  • A finite set of states
  • A finite input symbols
  • An initial weight function
  • A final weight function
  • A transition function

How is WFSAs differ from FSAs?

  1. Every state can be an initial state, using the initial weight function

  2. Every state can be an accepting state, using the final weight function|

  3. Transitions are possible between any pair of states on any input, using the transition function that takes in initial state, weight, and final state

The total score for any path is equal to the sum of the scores below:

To find the minimum-cost path through WFSA for a particular string, we can use a shortest-path algorithm with time complexity O(E + VlogV), where E is the number of edges and V is the number of vertices.

Ryan

Ryan

Data Scientist

Leave a Reply