Advertisement
Published in:
2014 | OriginalPaper | Chapter
Nonterminal Complexity of Weakly Conditional Grammars
Authors : Sherzod Turaev, Mohd Izzuddin Mohd Tamrin, Norsaremah Salleh
Published in: Intelligent Information and Database Systems
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.