From their beginnings in the 1950s and 1960s to implement small hand-built grammars (e.g., Joshi and Hopely 1996) through their applications in computational morphology in the 1980s (Koskenniemi 1983), finite-state models are now routinely applied in areas ranging from parsing (Abney 1996), to machine translation (Bangalore and Riccardi 2001;de Gispert et al.
in M, because there is a transition leaving state s i labeled with w, the backoff arc, which is a failure transition, cannot be traversed, hence the destination of the n-gram arc s j will be the next state in p. in M , both the n-gram transition labeled with w and the backoff transition, now labeled with , can be traversed.