The Compilation of Regular Expressions into Integrated Circuits.

Abstract

We consider the design of integrated circuits to implement arbitrary regular expressions. In general, we may use the McNaughton-Yamada algorithm to convert a regular expression of length n into a nondeterministic finite automation with at most 2n states and 4n transitions. Instead of converting the nondeterministic device to a deterministic one, we propose two ways of implementing the nondeterministic device directly. First, we could produce a PLA (programmable logic array) of approximate dimensions 4n x 4n by representing the states directly by columns, rather than coding the states in binary. This approach, while theoretically suboptimal, makes use of carefully developed technology and, because of the care with which PLA implementation has been done, may be the preferred technique in many real situations. Another approach is to use the hierarchical structure of the automation produced from the regular expression to guide a hierarchical layout of the circuit. This method produces a circuit 0(square root of n) on a side and is, to within a constant factor, the best that can be done in general. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1980
Accession Number
ADA090507

Entities

People

  • Jeffrey D. Ullman
  • Robert W. Floyd

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Alphabets
  • Application Software
  • Aspect Ratio
  • Automata
  • Automata Theory
  • Classification
  • Coding
  • Computer Programming
  • Computer Science
  • Computers
  • Integrated Circuits
  • Language
  • Machines
  • Numbers
  • Operating Systems
  • Security
  • Symbols

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Team-Based Human-Centered Cognitive Task Decision Making and Information Performance.