semi-Thue systemSemiThueSystem2007-09-24 00:33:202008-02-14 10:29:35Definitionantecedentconsequentimmediately derivablederivabledefining relationword problem for semi-Thue systemssemi-Thue productiongenerable by a semi-Thue system\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}
\usepackage{psfrag}
% define commands here
\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}}
\newcommand{\derive}{\stackrel{*}{\Rightarrow}}A \emph{semi-Thue system} $\mathfrak{S}$ is a pair $(\Sigma, P)$ where $\Sigma$ is an alphabet and $P$ is a non-empty finite binary relation on $\Sigma^*$, the Kleene star of $\Sigma$.
Elements of $P$ are variously called \emph{defining relations}, \emph{productions}, or \emph{rewrite rules}, and $\mathfrak{S}$ itself is also known as a \emph{rewriting system}. If $(x,y)\in P$, we call $x$ the \emph{antecedent}, and $y$ the \emph{consequent}. Instead of writing $(x,y)\in P$ or $xPy$, we usually write $$x\to y.$$
Let $\mathfrak{S}=(\Sigma,P)$ be a semi-Thue system. Given a word $u$ over $\Sigma$, we say that a word $v$ over $\Sigma$ is \emph{immediately derivable} from $u$ if there is a defining relation $x\to y$ such that $$u=rxs\qquad\mbox{ and }\qquad v=rys,$$ for some words $r,s$ (which may be empty) over $\Sigma$. If $v$ is immediately derivable from $u$, we write $$u\Rightarrow v.$$ Let $P'$ be the set of all pairs $(u,v)\in \Sigma^*\times \Sigma^*$ such that $u\Rightarrow v$. Then $P\subseteq P'$, and
\begin{quote}\begin{center}
If $u\Rightarrow v$, then $wu\Rightarrow wv$ and $uw\Rightarrow vw$ for any word $w$.
\end{center}\end{quote}
Next, take the reflexive transitive closure $P''$ of $P'$. Write $a\derive b$ for $(a,b)\in P''$. So $a\derive b$ means that either $a=b$, or there is a finite chain $a=a_1,\ldots,a_n=b$ such that $a_i\Rightarrow a_{i+1}$ for $i=1,\ldots,n-1$. When $a\derive b$, we say that $b$ is \emph{derivable} from $a$. Concatenation preserves derivability:
\begin{quote}\begin{center}
$a\derive b$ and $c\derive d$ imply $ac\derive bd$.
\end{center}\end{quote}
\textbf{Example}. Let $\mathfrak{S}$ be a semi-Thue system over the alphabet $\Sigma=\lbrace a,b,c\rbrace$, with the set of defining relations given by $P=\lbrace ab\to bc, bc \to cb \rbrace$. Then words $ac^3b$, $a^2c^2b$ and
as $bc^4$ are all derivable from $a^2bc^2$:
\begin{itemize}
\item $a^2bc^2 \Rightarrow a(bc)c^2 \Rightarrow ac(bc)c \Rightarrow ac^2(cb) = ac^3b$,
\item $a^2bc^2 \Rightarrow a^2(cb)c \Rightarrow a^2c(cb) = a^2c^2b$, and
\item $a^2bc^2 \Rightarrow a(bc)c^2 \Rightarrow (bc)cc^2 = bc^4$.
\end{itemize}
Under $\mathfrak{S}$, we see that if $v$ is derivable from $u$, then they have the same length: $|u|=|v|$. Furthermore, if we denote $|a|_u$ the number of occurrences of letter $a$ in a word $u$, then $|a|_v\le |a|_u$, $|c|_v\ge |c|_u$, and $|b|_v = |b|_u$. Also, in order for a word $u$ to have a non-trivial word $v$ (non-trivial in the sense that $u\ne v$) derivable from it, $u$ must have either $ab$ or $bc$ as a subword. Therefore, words like $a^3$ or $c^3b^4a^2$ have no non-trivial derived words from them.
\textbf{Remarks}.
\begin{enumerate}
\item Given a semi-Thue system $\mathfrak{S}=(\Sigma,P)$, one can associate a subset $A$ of $\Sigma^*$ whose elements we call \emph{axioms} of $\mathfrak{S}$. Any word $v$ that is derivable from an axiom $a\in A$ is called a \emph{theorem} (of $\mathfrak{S}$). If $v$ is a theorem, we write $A \vdash_{\mathfrak{S}} v$. The set of all theorems is written $L_{\mathfrak{S}}(A)$, and is called the language (over $\Sigma$) generated by $A$.
\item Let $\mathfrak{S}$ and $A$ be defined as above, and $T$ any alphabet. Call the elements of $T\cap \Sigma$ the \emph{terminals} of $\mathfrak{S}$. The set
$$L_{\mathfrak{S}}(A)\cap T^*$$
is called the \emph{language generated by $A$ over $T$}, and written $L_{\mathfrak{S}}(A,T)$. It is easy to see that $L_{\mathfrak{S}}(A,T)=L_{\mathfrak{S}}(A,T\cap \Sigma)$.
\item A language $L$ over an alphabet $\Sigma$ is said to be \emph{generable by a semi-Thue system} if there is a semi-Thue system $\mathfrak{S}$ and a finite set of axioms $A$ of $\mathfrak{S}$ such that $L= L_{\mathfrak{S}}(A,\Sigma)$.
\item Semi-Thue systems are ``equivalent'' to formal grammars in the following sense:
\begin{quote} a language is generable by a formal grammar iff it is semi-Thue generable. \end{quote} The idea is to turn every defining relation $x\to y$ in $P$ into a production $SxT\to SyT$, where $S$ and $T$ are non-terminals or variables. As such, a production of the form $SxT\to SyT$ is sometimes called a \emph{semi-Thue production}.
\item Given a semi-Thue system $\mathfrak{S}=(\Sigma,P)$, the \emph{word problem} for $\mathfrak{S}$ asks whether or not for any pair of words $u,v$ over $\Sigma$, one can determine in a finite number of steps (an algorithm) that $u\derive v$. If such an algorithm exists, we say that the word problem for $\mathfrak{S}$ is solvable. It turns out there exists a semi-Thue system such that the word problem for it is unsolvable.
\item The word problem for a specific $\mathfrak{S}$ is the same as finding an algorithm to determine whether $v$ is a theorem based on a singleton axiom $\lbrace u\rbrace$ for arbitrary words $u,v$.
\item \emph{The word problem for semi-Thue systems} asks whether or not, given \emph{any} semi-Thue system $\mathfrak{S}$, the word problem for $\mathfrak{S}$ is solvable. From the previous remark, we see the word problem for semi-Thue systems is unsolvable.
\end{enumerate}
\begin{thebibliography}{9}
\bibitem{md} M. Davis, {\em Computability and Unsolvability}. Dover Publications, New York (1982).
\bibitem{hh} H. Hermes, {\em Enumerability, Decidability, Computability: An Introduction to the Theory of Recursive Functions}. Springer, New York, (1969).
\end{thebibliography}