Nonterminal complexity of weakly conditional grammars

Sherzod Turaev, Mohd Izzuddin Mohd Tamrin, Norsaremah Salleh

Research output: Contribution to journalConference articlepeer-review


A weakly conditional grammar is specified as a pair K= (G, G′) where G is a context-free grammar, and G′ is a regular grammar such that a production rule of G is only applicable to the sentential form if it belongs to the language generated by G′. The nonterminal complexity Var(K) of the grammar K is defined as the sum of the numbers of nonterminals of G and G′. This paper studies the nonterminal complexity of weakly conditional grammars, and it proves that every recursively enumerable language can be generated by a weakly conditional grammar with no more than ten nonterminals. Moreover, it shows that the number of nonterminals in such grammars without erasing rules leads to an infinite hierarchy of families of languages generated by weakly conditional grammars.

Original languageEnglish
Pages (from-to)53-62
Number of pages10
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8397 LNAI
Issue numberPART 1
Publication statusPublished - 2014
Externally publishedYes
Event6th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2014 - Bangkok, Thailand
Duration: Apr 7 2014Apr 9 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Nonterminal complexity of weakly conditional grammars'. Together they form a unique fingerprint.

Cite this