General Algorithms for Testing the Ambiguity of Finite Automata

Cyril Allauzen, Mehryar Mohri, Ashish Rastogi

This paper presents efficient algorithms for testing the finite, polynomial, and exponential ambiguity of finite automata with $\epsilon$-transitions. It gives an algorithm for testing th…