1-4hit |
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.
Let Q be the set of all primitive words over a finite alphabet having at least two letters. In this paper, we study the language D(1) of all non-overlapping (d-primitive) words, which is a proper subset of Q. We show that D(1) is a context-sensitive langauage but not a deterministic context-free language. Further it is shown that [D(1)]n is not regular for n ≥ 1.
In this paper, we study d-primitive words and D(1)-concatenated words. First we show that neither D(1), the set of all d-primitive words, nor D(1)D(1), the set of all D(1)-concatenated words, is regular. Next we show that for u, v, w ∈Σ+ with |u|=|w|, uvw ∈ D(1) if and only if uv+w ⊆ D(1). It is also shown that every d-primitive word, with the length of two or more, is D(1)-concatenated.
In this paper, we give some resuts on primitive words, square-free words and disjunctive languages. We show that for a word u ∈Σ+, every element of λ(cp(u)) is d-primitive iff it is square-free, where cp(u) is the set of all cyclic-permutations of u, and λ(cp(u)) is the set of all primitive roots of it. Next we show that pmqn is a primitive word for every n, m ≥1 and primitive words p, q, under the condition that |p| = |q| and (m, n) ≠ (1, 1). We also give a condition of disjunctiveness for a language.