The number of nonterminals in a linear conjunctive grammar is considered as a descriptional complexity measure of this family of languages. It is proved that a hierarchy collapses, and for every linear conjunctive grammar there exists and can be effectively constructed a linear conjunctive grammar that accepts the same language and contains exactly two nonterminals. This yields a partition of linear conjunctive languages into two nonempty disjoint classes of those with nonterminal complexity 1 and 2. The basic properties of the family of languages for which one nonterminal suffices are established. Nonterminal complexity of grammars in the linear normal form is also investigated.

Original languageEnglish
Pages (from-to)419-448
Number of pages30
JournalTheoretical Computer Science
Volume320
Issue number2-3
DOIs
StatePublished - 14 Jun 2004
Externally publishedYes

    Research areas

  • Cellular automaton, Conjunctive grammar, Descriptional complexity, Formal languages, Language equation, Minimal linear grammar, Trellis automaton

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 41144387