Elements of are variously called defining relations, productions, or rewrite rules, and itself is also known as a rewriting system. If , we call the antecedent, and the consequent. Instead of writing or , we usually write
Let be a semi-Thue system. Given a word over , we say that a word over is immediately derivable from if there is a defining relation such that
for some words (which may be empty) over . If is immediately derivable from , we write
Let be the set of all pairs such that . Then , and
If , then and for any word .
Next, take the reflexive transitive closure of . Write for . So means that either , or there is a finite chain such that for . When , we say that is derivable from . Concatenation preserves derivability:
and imply .
Example. Let be a semi-Thue system over the alphabet , with the set of defining relations given by . Then words , and as are all derivable from :
Under , we see that if is derivable from , then they have the same length: . Furthermore, if we denote the number of occurrences of letter in a word , then , , and . Also, in order for a word to have a non-trivial word (non-trivial in the sense that ) derivable from it, must have either or as a subword. Therefore, words like or have no non-trivial derived words from them.
Let and be defined as above, and any alphabet. Call the elements of the terminals of . The set
is called the language generated by over , and written . It is easy to see that .
A language over an alphabet is said to be generable by a semi-Thue system if there is a semi-Thue system and a finite set of axioms of such that .
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 in into a production , where and are non-terminals or variables. As such, a production of the form is sometimes called a semi-Thue production.
Given a semi-Thue system , the word problem for asks whether or not for any pair of words over , one can determine in a finite number of steps (an algorithm) that . If such an algorithm exists, we say that the word problem for 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 is the same as finding an algorithm to determine whether is a theorem based on a singleton axiom for arbitrary words .
The word problem for semi-Thue systems asks whether or not, given any semi-Thue system , the word problem for is solvable. From the previous remark, we see the word problem for semi-Thue systems is unsolvable.
|Date of creation||2013-03-22 17:33:16|
|Last modified on||2013-03-22 17:33:16|
|Last modified by||CWoo (3771)|
|Defines||word problem for semi-Thue systems|
|Defines||generable by a semi-Thue system|