VLSI architectures for high speed recognition of context-free languages and finite-state languages
- 1 April 1982
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGARCH Computer Architecture News
- Vol. 10 (3) , 43-49
- https://doi.org/10.1145/1067649.801712
Abstract
This paper presents two VLSI architectures for the recognition of context-free languages and finite-state languages. The architecture for context-free languages consists of n(n+1)/2 identical cells and it is capable of recognizing an input string of length n in 2n time units. The architecture for finite-state languages consists of n cells and it can recognize a string of length n in constant time. Since both architectures have characteristics such as modular layout, simple constrol and dataflow pattern, high degree of multiprocessing and/or pipelining, etc., they are very suitable for VLSI implementation.Keywords
This publication has 4 references indexed in Scilit:
- Hardware for searching very large text databasesPublished by Association for Computing Machinery (ACM) ,1980
- On line context free language recognition in less than cubic time(Extended Abstract)Published by Association for Computing Machinery (ACM) ,1976
- An efficient context-free parsing algorithmCommunications of the ACM, 1970
- Tree generating regular systemsInformation and Control, 1969