Survey of the Theory of Automata in Natural Language Processing

Abstract

 Words occur in sequence over time, and the words encountered constrain the meaning of the words that follow, rendering it critical in texts written or spoken in English, Spanish, etc. This makes finite-state machines effective at simulating the sequential property of a language. Having said that, this does not rule off other types of automata such as but not limited to, deterministic pushdown automaton and Turing machines, as these were shown to be useful in both transformational and generative grammars. The theory of automata has a rich literature in providing efficient and convenient tools for several branches of computational linguistics. This paper highlighted the significant works on that domain and presented some of the influential breakthroughs of the automata theory in the analysis of both syntax and semantics of the natural language.