You are here
HomesemiThue system
Primary tabs
semiThue system
A semiThue system $\mathfrak{S}$ is a pair $(\Sigma,P)$ where $\Sigma$ is an alphabet and $P$ is a nonempty finite binary relation on $\Sigma^{*}$, the Kleene star of $\Sigma$.
Elements of $P$ are variously called defining relations, productions, or rewrite rules, and $\mathfrak{S}$ itself is also known as a rewriting system. If $(x,y)\in P$, we call $x$ the antecedent, and $y$ the consequent. Instead of writing $(x,y)\in P$ or $xPy$, we usually write
$x\to y.$ 
Let $\mathfrak{S}=(\Sigma,P)$ be a semiThue system. Given a word $u$ over $\Sigma$, we say that a word $v$ over $\Sigma$ is 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^{{\prime}}$ be the set of all pairs $(u,v)\in\Sigma^{*}\times\Sigma^{*}$ such that $u\Rightarrow v$. Then $P\subseteq P^{{\prime}}$, and
If $u\Rightarrow v$, then $wu\Rightarrow wv$ and $uw\Rightarrow vw$ for any word $w$.
Next, take the reflexive transitive closure $P^{{\prime\prime}}$ of $P^{{\prime}}$. Write $a\stackrel{*}{\Rightarrow}b$ for $(a,b)\in P^{{\prime\prime}}$. So $a\stackrel{*}{\Rightarrow}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,n1$. When $a\stackrel{*}{\Rightarrow}b$, we say that $b$ is derivable from $a$. Concatenation preserves derivability:
$a\stackrel{*}{\Rightarrow}b$ and $c\stackrel{*}{\Rightarrow}d$ imply $ac\stackrel{*}{\Rightarrow}bd$.
Example. Let $\mathfrak{S}$ be a semiThue system over the alphabet $\Sigma=\{a,b,c\}$, with the set of defining relations given by $P=\{ab\to bc,bc\to cb\}$. Then words $ac^{3}b$, $a^{2}c^{2}b$ and as $bc^{4}$ are all derivable from $a^{2}bc^{2}$:

$a^{2}bc^{2}\Rightarrow a(bc)c^{2}\Rightarrow ac(bc)c\Rightarrow ac^{2}(cb)=ac^% {3}b$,

$a^{2}bc^{2}\Rightarrow a^{2}(cb)c\Rightarrow a^{2}c(cb)=a^{2}c^{2}b$, and

$a^{2}bc^{2}\Rightarrow a(bc)c^{2}\Rightarrow(bc)cc^{2}=bc^{4}$.
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}\leqa_{u}$, $c_{v}\geqc_{u}$, and $b_{v}=b_{u}$. Also, in order for a word $u$ to have a nontrivial word $v$ (nontrivial in the sense that $u\neq v$) derivable from it, $u$ must have either $ab$ or $bc$ as a subword. Therefore, words like $a^{3}$ or $c^{3}b^{4}a^{2}$ have no nontrivial derived words from them.
Remarks.
1. Given a semiThue system $\mathfrak{S}=(\Sigma,P)$, one can associate a subset $A$ of $\Sigma^{*}$ whose elements we call axioms of $\mathfrak{S}$. Any word $v$ that is derivable from an axiom $a\in A$ is called a 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$.
2. Let $\mathfrak{S}$ and $A$ be defined as above, and $T$ any alphabet. Call the elements of $T\cap\Sigma$ the terminals of $\mathfrak{S}$. The set
$L_{{\mathfrak{S}}}(A)\cap T^{*}$ is called the 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)$.
3. A language $L$ over an alphabet $\Sigma$ is said to be generable by a semiThue system if there is a semiThue system $\mathfrak{S}$ and a finite set of axioms $A$ of $\mathfrak{S}$ such that $L=L_{{\mathfrak{S}}}(A,\Sigma)$.
4. SemiThue systems are “equivalent” to formal grammars in the following sense:
a language is generable by a formal grammar iff it is semiThue generable.
The idea is to turn every defining relation $x\to y$ in $P$ into a production $SxT\to SyT$, where $S$ and $T$ are nonterminals or variables. As such, a production of the form $SxT\to SyT$ is sometimes called a semiThue production.
5. Given a semiThue system $\mathfrak{S}=(\Sigma,P)$, the 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\stackrel{*}{\Rightarrow}v$. If such an algorithm exists, we say that the word problem for $\mathfrak{S}$ is solvable. It turns out there exists a semiThue system such that the word problem for it is unsolvable.
6. 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 $\{u\}$ for arbitrary words $u,v$.
7. The word problem for semiThue systems asks whether or not, given any semiThue system $\mathfrak{S}$, the word problem for $\mathfrak{S}$ is solvable. From the previous remark, we see the word problem for semiThue systems is unsolvable.
References
 1 M. Davis, Computability and Unsolvability. Dover Publications, New York (1982).
 2 H. Hermes, Enumerability, Decidability, Computability: An Introduction to the Theory of Recursive Functions. Springer, New York, (1969).
Mathematics Subject Classification
68Q42 no label found03D40 no label found20M35 no label found03D03 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections