**Gertjan van Noord and Dale Gerdemann**

Finite-state techniques are widely used in various areas of Natural
Language Processing (NLP). As Kaplan and Kay
[12] have argued, regular expressions are the
appropriate level of abstraction for thinking about finite-state
languages and finite-state relations. More complex finite-state
operations (such as contexted replacement) are defined on the basis
of basic operations (such as Kleene closure, complementation,
composition).

In order to be able to experiment with such complex finite-state
operations the FSA Utilities (version 5) provides an *
extendible* regular expression compiler. The paper discusses the
regular expression operations provided by the compiler, and the
possibilities to create new regular expression operators. The
benefits of such an extendible regular expression compiler are
illustrated with a number of examples taken from recent publications
in the area of finite-state approaches to NLP.

- Introduction
- Regular Expressions
- Extendible Regular Expression Operators
- Regular Expression Operators in NLP
- Implementational Issues
- Concluding Remarks
- Bibliography
- Syllabification in Optimality Theory
- Mohri & Sproat Replace Operator
- N-queens Problem
- About this document ...