d-Primitive Words and Contextual Grammars

Tetsuo MORIYA  Itaru KATAOKA  

IEICE TRANSACTIONS on Information and Systems   Vol.E95-D   No.11   pp.2710-2711
Publication Date: 2012/11/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E95.D.2710
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
formal language,  primitive word,  non-overlapping word,  d-primitive word,  context-free,  Marcus contextual grammar and language,  

Full Text: PDF>>
Buy this Article

In this paper we study the ploblem whether the language D(1) of all d-primitive words can be generated by a contextual grammar. It is proved that D(1) can be generated neither by an external contextual grammar nor by an internal contextual grammar, and that it can be generated by a total contextual grammar with choice.