Effective implementation of word-based regular expressions notation in natural language processing

Abstract

This paper introduces a technique that allows to build deterministic finite-state automata from word-based regular expressions that are described in [1]. The automata obtained by this technique can be used in automatic analysis of natural language sentences without any loss of algorithmic deterministic automata efficiency. The paper shows the difference between traditional and word-based regular expressions and explains the need for additional transformation of word-based regular grammar in order to build deterministic finite-state automaton.