A note on the computational completeness of generalized forbidding grammars

  • R.O. Oladele
  • A.A. Ajayi
Keywords: Formal languages, computational power, generalized forbidding grammars.

Abstract

This paper demonstrates that a generalized forbidding grammars of degree 3, index 5, with no more than 7 conditional productions and 9 non-terminals is computationally complete This result is based on the common idea of using Geffert normal forms for type-0 grammars.

Published
2021-04-15
Section
Articles

Journal Identifiers


eISSN: 1116-4336