For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
d-Primitive Words and Contextual Grammars
Tetsuo MORIYA Itaru KATAOKA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2012/11/01
Online ISSN: 1745-1361
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>>
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.