On tree-restricted regular-controlled context-free grammars. Issue 4 (2nd October 2017)

• Record Type: Journal Article
• Authors: Meduna, A.; Soukup, O.; Csuhaj-Varjú, E.
• Is Part Of: International journal of computer mathematics. Volume 2:Issue 4(2017)
• Page Start: 147
• Page End: 163
• Publication Date: 2017-10-02
• Subjects: Regular-controlled context-free grammars -- restricted derivation trees -- context-freeness of finite index; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2017.1388291
• Languages: English
• ISSNs: 2379-9927

Abstract

ABSTRACT: This paper gives simple tree-based conditions under which regular-controlled context-free grammars generate context-free languages of finite index, so they cannot even generate all context-free languages. It defines the notion of path-changing derivation step which corresponds to performing two consecutive rewritings of nonterminal symbols present in the different branches of the derivation tree. It proves that if there exists a certain constant that limits the number of path-changing derivation steps, then, the regular-controlled grammar generates a context-free language of finite index. At the end, we generalize achieved result and provide some open problems for future study.