Nonterminal complexity of weakly conditional grammars

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