DOI

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.

Язык оригиналаанглийский
Страницы (с-по)419-448
Число страниц30
ЖурналTheoretical Computer Science
Том320
Номер выпуска2-3
DOI
СостояниеОпубликовано - 14 июн 2004
Опубликовано для внешнего пользованияДа

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 41144387