Treatment of epsilon moves in subset construction

G van Noord*

*Corresponding author for this work

    Research output: Contribution to journalArticleAcademicpeer-review

    19 Citations (Scopus)
    208 Downloads (Pure)


    The paper discusses the problem of determinizing finite-state automata containing large numbers of E-moves. Experiments with finite-state approximations of natural language grammars often give vise to very large automata with a very large number of E-moves. The paper identifies and compares a number of subset construction algorithms that treat E-moves. Experiments have been performed which indicate that the algorithms differ considerably in practice, both with respect to the size of the resulting deterministic automaton, and with respect to practical efficiency Furthermore, the experiments suggest that the average number of E-moves per state can be used to predict which algorithm is likely to be the fastest for a given input automaton.

    Original languageEnglish
    Pages (from-to)61-76
    Number of pages16
    JournalComputational Linguistics
    Issue number1
    Publication statusPublished - Mar-2000

    Cite this