$n$-Insertion on Languages (Algorithms in Algebraic Systems and Computation Theory)
Masami Itō, Ryo Sugiura · Institutional Repositories DataBase (IRDB) · 2002
In this paper, we define the $n$ -insertion $A\triangleright^{1n]}B$ of alanguage $A$ into alanguage $B$ and provide some properties of $n$ -insertions.For instance, the $n$ -insertion of aregular language into aregular language is regular but the $n$ -insertion of acontext-free language into acontext- free language is not always context-free.However, it can be shown that the $n$ -insertion of aregular (context-free) language into acontext-free (regular) language is context-free.We also consider the decomposition of regular languages under n-insertion.1Introduction Let $u$ , $v\in X^{*}$ and let $n$ be apositive integer.Then thewe provide some properties of $n$ -insertions.For instance, the $n$ -insertion of aregular language into aregular language is regular but the $n$ -insertion of a context-free language into acontext-free language is not always context-free.However, it can be shown that the $n$ -insertion of aregular (context-free) language into acontext-free (regular) language is context-free.In Section 3, we prove that, for agiven regular language $L\subseteq X$ ' and apositive integr $n$ , it is decidable whether $L=A\triangleright^{1^{n}]}B$ for some nontrivial regular languages $A$ , $B\subseteq X^{*}$ .Here alanguage $C\subseteq X^{*}$ is said to be nontrivial if $C eq\{\epsilon\}$ where $\epsilon$ is the empty word.Regarding definitions and notations concerning formal languages and automata, not defined in this paper, refer, for instance,