3.1.6 Regular Relations and Rewriting Rules

Regular expressions also relate to finite state transducers.

Before we turn to a closer examination of the class of regular languages, let us have a short look at finite state transducers. Is there anything to do the job of regular expressions for finite state transducers? And what corresponds to regular languages in this case?

Finite state transducers recognize tuples of strings. A set of tuples of strings that can be recognized by an FST is called a regular relation. So, regular relations are to FSTs what regular languages are to FSAs. The following transducer (we have already seen it in Section 2.2.1), for instance, recognizes the regular relation .

Regular relations can be specified using (ordered sets of) rewriting rules. The rewriting rules

for instance, express the e-insertion rule. The first one is read as ``replace nothing () with e in the context of s+ (s and a morpheme boundary, +) to the left and s% (s and a word boundary, %) to the right. There are algorithms for translating such rule systems (at least as long as they obey certain restrictions) into transducers.


Kristina Striegnitz, Patrick Blackburn, Katrin Erk, Stephan Walter, Aljoscha Burchardt and Dimitra Tsovaltzi
Version 1.2.5 (20030212)