Abstract
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 language | English |
|---|---|
| Pages (from-to) | 53-62 |
| Number of pages | 10 |
| Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Volume | 8397 LNAI |
| Issue number | PART 1 |
| DOIs | |
| Publication status | Published - 2014 |
| Externally published | Yes |
| Event | 6th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2014 - Bangkok, Thailand Duration: Apr 7 2014 → Apr 9 2014 |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science