Recognize Regular Languages with Programmable Building-Blocks.

This paper introduces a new programmable building-block for recognition of regular languages. By combining three types of basic cells a circuit for recognizing any regular language can be constructed or programmed automatically from the regular expression describing that language. Recognizers built in this way are efficient pipeline circuits that have constant response time and avoid broadcast. In addition, the paper proposes the use of a single, regular layout, called the PRA programmable recognizer array, that can be personalized to recognize the language specified by any regular expression. PRAs provide compact reconfigurable layouts for recognizer circuits, requiring only On log n area for regular expressions of length n. Author