1. A method for automatically recognizing speech, comprising: inputting an electric signal representing an uttered speech; converting the electric signal to a feature vector lattice; and converting the feature vector lattice to a recognized text string representing the uttered speech using at least one approximate weighted finite-state lattice; wherein each at least one approximate weighted finite-state lattice is generated from a corresponding non-deterministic weighted finite-state lattice by: determining the corresponding non-deterministic weighted finite-state lattice to form the approximate weighted finite-state lattice on a state-by-state basis; determining, as each set of states of the corresponding non-deterministic weighted finite-state lattice reachable from a current state of the approximate weighted finite-state lattice is determinized to form at least one proposed new state of the approximate weighted finite-state lattice, for each proposed new state, if that proposed new state is sufficiently similar to a previous state of the approximate weighted finite-state lattice; creating a transition from the current state of the approximate weighted finite-state lattice to the previous state of the approximate weighted finite-state lattice if that proposed new state is sufficiently similar to the previous state; and creating a transition from the current state of the approximate weighted finite-state lattice to the proposed new state of the approximate weighted finite-state lattice if that proposed new state is not sufficiently similar to any previous state of the approximate weighted finite-state lattice.