VLSI architectures for high speed recognition of context-free languages and finite-state languages

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.

REFERENCES

• 1: M.A. A. Harrison , M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 2: Susan L. Graham , Michael A. Harrison , Walter L. Ruzzo, On line context free language recognition in less than cubic time(Extended Abstract), Proceedings of the eighth annual ACM symposium on Theory of computing, p.112-120, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803638]
• 3: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 4: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 5: L. J. Guibas, H. T. Kung and C. D. Thompson, "Direct VLSI implementation of combinatorial algorithms," Proc. Conf. on VLSI, Caltech, Jan. 1979, pp. 509-526.
• 6: H. T. Kung, "Let's design algorithms for VLSI systems," Proc. Conf. on VLSI, Caltech, Jan. 1979, pp. 65-90.
• 7: K. S. Fu and B. K. Bhargava, "Tree systems for syntactic pattern recognition," IEEE Trans. on Computers, Vol. C-22, No. 12, Dec. 1973.
• 8: W. S. Brainerd, "Tree generating regular systems," Inform. Contr., Vol. 14, 1969, pp. 217-231.
• 9: K. Q. Brown, "Dynamic programming in computer science," Carnegie-Mellon Univ., Tech. Report, CS-79-106, Feb. 1979.
• 10: K. S. Fu, Syntactic methods in pattern recognition, Academic Press, New York, 1974.
• 11: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 12: D. L. Waltz and B. A. Goodman, "Writing a natural language database system," Coordinated Science Lab., Univ. of Illinois, Urbana, IL 61801.
• 13: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 14: Roger Haskin, Hardware for searching very large text databases, Proceedings of the fifth workshop on Computer architecture for non-numeric processing, p.49-56, March 11-14, 1980, Pacific Grove, California, United States
• 15: K. H. Chu and K. S. Fu, "VLSI Architectures for High Speed Recognition of General Context-Free Languages and Finite-State Languages," Tech. Rept. TR-EE 81-42, Purdue University, November 1981.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

General Terms:
Design, Languages