Turaev, Sherzod and Mohd Tamrin, Mohd Izzuddin and Salleh, Norsaremah (2014) Nonterminal complexity of weakly conditional grammars. In: 6th Asian Conference, ACIIDS 2014, 7th-9th April 2014, Bangkok, Thailand.
PDF
- Published Version
Restricted to Repository staff only Download (181kB) | Request a copy |
|
PDF (SCOPUS)
- Published Version
Restricted to Repository staff only Download (493kB) | Request a copy |
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.
Item Type: | Conference or Workshop Item (Plenary Papers) |
---|---|
Additional Information: | 6846/36798 |
Uncontrolled Keywords: | weakly conditional grammar |
Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button): | Kulliyyah of Information and Communication Technology > Department of Computer Science Kulliyyah of Information and Communication Technology > Department of Computer Science Kulliyyah of Information and Communication Technology > Department of Information System Kulliyyah of Information and Communication Technology > Department of Information System |
Depositing User: | Dr. Sherzod Turaev |
Date Deposited: | 06 Jun 2014 16:19 |
Last Modified: | 26 Sep 2017 10:53 |
URI: | http://irep.iium.edu.my/id/eprint/36798 |
Actions (login required)
View Item |