Back to the index. Or to the chambers

This article has 25 links. View as Cloud or List.

Loading ...

Planetmath Browser (2008—2009)

BSD licence | A django site

All articles taken from PlanetMath.org snapshot under CC-BY-SA licence.

→ The original article on PlanetMath.org

Other Formats: LaTeX

New! You can click on formulas to copy the LaTeX source to your clipboard. | Math Videos

Semi Thue System

A semi-Thue system $\mathfrak{S}$ is a pair $(\Sigma, P)$ where $\Sigma$ is an alphabet and is a non-empty finite binary relation on $\Sigma^*$ , the Kleene star of $\Sigma$ .

Elements of 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 the antecedent, and the consequent. Instead of writing $(x,y)\in P$ or , we usually write

$\displaystyle x\to y.$

Let $\mathfrak{S}=(\Sigma,P)$ be a semi-Thue system. Given a word over $\Sigma$ , we say that a word over $\Sigma$ is immediately derivable from if there is a defining relation $x\to y$ such that

$\displaystyle u=rxs$ and $\displaystyle \qquad v=rys,$

for some words

(which may be empty) over $\Sigma$ . If

is immediately derivable from

, we write

$\displaystyle u\Rightarrow v.$

Let

be the set of all pairs $(u,v)\in \Sigma^*\times \Sigma^*$ such that $u\Rightarrow v$ . Then $P\subseteq P'$ , and

If $u\Rightarrow v$ , then $wu\Rightarrow wv$ and $uw\Rightarrow vw$ for any word .

Next, take the reflexive transitive closure

. Write $a\stackrel{*}{\Rightarrow}b$ for $(a,b)\in P''$ . So $a\stackrel{*}{\Rightarrow}b$ means that either

, 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\stackrel{*}{\Rightarrow}b$ , we say that

is derivable from

. Concatenation preserves derivability:

$a\stackrel{*}{\Rightarrow}b$ and $c\stackrel{*}{\Rightarrow}d$ imply $ac\stackrel{*}{\Rightarrow}bd$ .

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 , and as are all derivable from :

$a^2bc^2 \Rightarrow a(bc)c^2 \Rightarrow ac(bc)c \Rightarrow ac^2(cb) = ac^3b$ ,
$a^2bc^2 \Rightarrow a^2(cb)c \Rightarrow a^2c(cb) = a^2c^2b$ , and
$a^2bc^2 \Rightarrow a(bc)c^2 \Rightarrow (bc)cc^2 = bc^4$ .

Under $\mathfrak{S}$ , we see that if

is derivable from

, then they have the same length: $\vert u\vert=\vert v\vert$ . Furthermore, if we denote $\vert a\vert _u$ the number of occurrences of letter

in a word

, then $\vert a\vert _v\le \vert a\vert _u$ , $\vert c\vert _v\ge \vert c\vert _u$ , and $\vert b\vert _v = \vert b\vert _u$ . Also, in order for a word

to have a non-trivial word

(non-trivial in the sense that $u\ne v$ ) derivable from it,

must have either

as a subword. Therefore, words like

have no non-trivial derived words from them.

Remarks.

Given a semi-Thue system $\mathfrak{S}=(\Sigma,P)$ , one can associate a subset of $\Sigma^*$ whose elements we call axioms of $\mathfrak{S}$ . Any word that is derivable from an axiom $a\in A$ is called a theorem (of $\mathfrak{S}$ ). If 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 .
Let $\mathfrak{S}$ and be defined as above, and any alphabet. Call the elements of $T\cap \Sigma$ the terminals of $\mathfrak{S}$ . The set
$\displaystyle L_{\mathfrak{S}}(A)\cap T^*$
is called the language generated by over , 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)$ .
A language over an alphabet $\Sigma$ is said to be generable by a semi-Thue system if there is a semi-Thue system $\mathfrak{S}$ and a finite set of axioms of $\mathfrak{S}$ such that $L= L_{\mathfrak{S}}(A,\Sigma)$ .
Semi-Thue systems are “equivalent” to formal grammars in the following sense:
a language is generable by a formal grammar iff it is semi-Thue generable.
The idea is to turn every defining relation $x\to y$ in into a production $SxT\to SyT$ , where and are non-terminals or variables. As such, a production of the form $SxT\to SyT$ is sometimes called a semi-Thue production.
Given a semi-Thue system $\mathfrak{S}=(\Sigma,P)$ , the word problem for $\mathfrak{S}$ asks whether or not for any pair of words 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 semi-Thue system such that the word problem for it is unsolvable.
The word problem for a specific $\mathfrak{S}$ is the same as finding an algorithm to determine whether is a theorem based on a singleton axiom $\lbrace u\rbrace$ for arbitrary words .
The word problem for semi-Thue systems asks whether or not, given 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.

Bibliography

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).

1	Obvious
1	Variable
1	Relation
1	Finite
1	Set
1	Axiom
1	Language
1	Biconditional
1	Number
1	Implication
1	Order Group
1	Generating Set Of A Group
2	Concatenation
2	Algorithm
2	Preservation And Reflection
2	Singleton
2	Alphabet
2	Word
3	Formal Grammar
3	Associates
5	Chain
5	Solvable
7	Closure Of A Relation With Respect To A Property
8	Kleene Star
15	Inverse Monoids And Inverse Semigroups Word Problem In The Category Of Groups