substitutionSubstitution2009-05-09 17:09:392009-08-08 07:41:50Definition$\lambda$-free substitutionregular substitution\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
\usepackage{xypic}
\usepackage{pst-plot}
% define commands here
\newcommand*{\abs}[1]{\left\lvert #1\right\rvert}
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{ex}{Example}
\newcommand{\real}{\mathbb{R}}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}}Let $\Sigma_1, \Sigma_2$ be alphabets. A \emph{substitution} is a function $s:\Sigma_1^* \to P(\Sigma_2^*)$ such that
\begin{itemize}
\item $s$ preserves the empty word: $s(\lambda)=\lbrace \lambda \rbrace$, and
\item $s$ preserves concatenation: $s(\alpha\beta)=s(\alpha)s(\beta)$.
\end{itemize}
In other words, for every word $\alpha$ over $\Sigma_1$, $s(\alpha)$ is a language over $\Sigma_2$. In the second condition above, $s(\alpha)s(\beta)$ is the concatenation of languages: $\lbrace uv\mid u\in s(\alpha), v\in s(\beta)\rbrace$.
The word ``substitution'' is used so often in mathematics, that substitution in the context of formal language theory is also known as a \emph{string substitution}.
As the semigroup $\Sigma_1^*$ is freely generated by $\Sigma_1$, every substitution $s:\Sigma_1^* \to P(\Sigma_2^*)$ is uniquely determined by its restriction to $\Sigma_1$. Conversely, every function $f:\Sigma_1 \to P(\Sigma_2^*)$ extends uniquely to a substitution $f_s:\Sigma_1^* \to P(\Sigma_2^*)$.
For any language $L\subseteq \Sigma_1^*$ and a substitution $s:\Sigma_1^* \to P(\Sigma_2^*)$, define $$s(L):=\bigcup \lbrace s(u)\mid u\in L\rbrace.$$
A family $\mathscr{F}$ of languages is said to be \emph{closed under substitutions} if, given any substitution $s$, with $L \in \mathscr{F}$ and $s(w) \in \mathscr{F}$ for each $w\in L$, we have $s(L)\in \mathscr{F}$. The following families are closed under substitutions:
\begin{itemize}
\item regular languages,
\item context-free languages, and
\item type-0 langauges.
\end{itemize}
As a corollary, the families of regular, context-free, and type-0 languages are closed under homomorphisms, since every homomorphism of languages is really just a special case of substitution, such that every symbol of the domain alphabet is mapped to a singleton consisting of a word over the range alphabet.
The family of context-sensitive languages is not closed under general substitutions. Instead, it is closed under $\lambda$-free substitutions (see remark below).
\textbf{Remark}. A substitution $s$ is said to have property $\mathcal{P}$ if for each $a\in \Sigma$, the set $s(a)$ has property $\mathcal{P}$. Thus, for example, a substitution $s$ is finite if $s(a)$ is a finite set, regular if $s(a)$ is a regular language, and $\lambda$-free if each $s(a)$ is $\lambda$-free, etc...
\begin{thebibliography}{9}
\bibitem{sg} S. Ginsburg, {\em The Mathematical Theory of Context-Free Languages}, McGraw-Hill, New York (1966).
\bibitem{dk} D. C. Kozen, {\em Automata and Computability}, Springer, New York (1997).
\end{thebibliography}