Programmable finite automata for VLSI†

†This work was supported by the Natural Sciences and Engineering Research Council of Canada under grant A-7403

Abstract

We describe a method VLSI for design of programmable finite automata. For any fixed k it can be programmed to deterministically simulate a non-deterministic finite auto- maton with at most k states. For some constant c it runs in time on inputs of length n>b and in time on inputs of length n≧b where b is a constant influencing the size of the realisation, which can be chosen so that ck is much smaller than b. The design is modular, it consists of 0(bk ²) identical processes connected in a uniform manner.

Keywords:

• Non-deterministic finite automata
• VLSI-tree

C.R. Categories and Subject Descriptors:

• F.1.1 [Computation by Abstract Devices]:
• Models of Computation—Finite Automata
• F.4.3. [Mathematical Logic and Formal Languages]
• Formal Languages—Regular Sets
• B.7.1 [Integrated Circuits]
• Types and Design Styles—Algorithms Implemented in Hardware
• VLSI

†This work was supported by the Natural Sciences and Engineering Research Council of Canada under grant A-7403

†This work was supported by the Natural Sciences and Engineering Research Council of Canada under grant A-7403

Notes

†This work was supported by the Natural Sciences and Engineering Research Council of Canada under grant A-7403