Nonterminal complexity of weakly conditional grammars

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...

Full description

Bibliographic Details
Main Authors:	Turaev, Sherzod, Mohd Tamrin, Mohd Izzuddin, Salleh, Norsaremah
Format:	Conference or Workshop Item
Language:	English English
Published:	Springer International Publishing Switzerland 2014
Subjects:	QA75 Electronic computers. Computer science
Online Access:	http://irep.iium.edu.my/36798/ http://irep.iium.edu.my/36798/ http://irep.iium.edu.my/36798/ http://irep.iium.edu.my/36798/1/26_Nonterminal_Complexity_of_Weakly_Conditional_Grammars_ASIIDS_%282014%29.pdf http://irep.iium.edu.my/36798/4/36798_Nonterminal%20complexity%20of%20weakly%20conditional%20grammars_SCOPUS.pdf

id	iium-36798
recordtype	eprints
spelling	iium-367982017-09-26T02:53:24Z http://irep.iium.edu.my/36798/ Nonterminal complexity of weakly conditional grammars Turaev, Sherzod Mohd Tamrin, Mohd Izzuddin Salleh, Norsaremah QA75 Electronic computers. Computer science 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. Springer International Publishing Switzerland 2014 Conference or Workshop Item PeerReviewed application/pdf en http://irep.iium.edu.my/36798/1/26_Nonterminal_Complexity_of_Weakly_Conditional_Grammars_ASIIDS_%282014%29.pdf application/pdf en http://irep.iium.edu.my/36798/4/36798_Nonterminal%20complexity%20of%20weakly%20conditional%20grammars_SCOPUS.pdf 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. http://link.springer.com/chapter/10.1007%2F978-3-319-05476-6_6 10.1007/978-3-319-05476-6_6
repository_type	Digital Repository
institution_category	Local University
institution	International Islamic University Malaysia
building	IIUM Repository
collection	Online Access
language	English English
topic	QA75 Electronic computers. Computer science
spellingShingle	QA75 Electronic computers. Computer science Turaev, Sherzod Mohd Tamrin, Mohd Izzuddin Salleh, Norsaremah Nonterminal complexity of weakly conditional grammars
description	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.
format	Conference or Workshop Item
author	Turaev, Sherzod Mohd Tamrin, Mohd Izzuddin Salleh, Norsaremah
author_facet	Turaev, Sherzod Mohd Tamrin, Mohd Izzuddin Salleh, Norsaremah
author_sort	Turaev, Sherzod
title	Nonterminal complexity of weakly conditional grammars
title_short	Nonterminal complexity of weakly conditional grammars
title_full	Nonterminal complexity of weakly conditional grammars
title_fullStr	Nonterminal complexity of weakly conditional grammars
title_full_unstemmed	Nonterminal complexity of weakly conditional grammars
title_sort	nonterminal complexity of weakly conditional grammars
publisher	Springer International Publishing Switzerland
publishDate	2014
url	http://irep.iium.edu.my/36798/ http://irep.iium.edu.my/36798/ http://irep.iium.edu.my/36798/ http://irep.iium.edu.my/36798/1/26_Nonterminal_Complexity_of_Weakly_Conditional_Grammars_ASIIDS_%282014%29.pdf http://irep.iium.edu.my/36798/4/36798_Nonterminal%20complexity%20of%20weakly%20conditional%20grammars_SCOPUS.pdf
first_indexed	2023-09-18T20:52:45Z
last_indexed	2023-09-18T20:52:45Z
_version_	1777410103261003776

Nonterminal complexity of weakly conditional grammars

Similar Items