Recognize Regular Languages with Programmable Building-Blocks.

Abstract

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. PRA's provide compact reconfigurable layouts for recognizer circuits, requiring only O(n log n) area for regular expressions of length n. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 19, 1981
Accession Number
ADA104874

Entities

People

  • H. T. Kung
  • Michael J. Foster

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Circuits
  • Comparators
  • Computer Science
  • Computers
  • Construction
  • Context Free Grammars
  • Electronic Circuits
  • Grammars
  • Language
  • Military Research
  • Nervous System
  • Personality
  • Pipelines
  • Production
  • Programming Languages
  • Scientific Research

Fields of Study

  • Computer science
  • Engineering

Readers

  • Computational Linguistics
  • Operations Research
  • Parallel and Distributed Computing.