semi-Thue system
semi-Thue system An important concept in formal language theory that underlies the notion of a grammar. It was defined and investigated by Axel Thue from about 1904. A semi-Thue system over the alphabet Σ is a finite set of ordered pairs of Σ-words: {〈l1,r1〉,…,〈ln,rn〉}
Each pair 〈li,ri〉 is a rule, referred to as a production, with left-hand side li and right-hand side ri; it is usually written li → ri
Let u and v be Σ-words, and l → r be a production, then the word ulv is said to directly derive the word urv; this is written ulv ⇒ urv
So w directly derives w′ if w′ is the result of applying a production to some substring of w. If w1 ⇒ w2 ⇒ … ⇒ wn–1 ⇒ wn
then w1 is said to derive wn; this is written w1 ⇒∗ wn
So w derives w′ if w′ is obtained from w by a sequence of direct derivations.
As one example, let Σ be {a,b} and let the productions be {ab → ba, ba → ab}
then aabba derives baaab by the sequence aabba ⇒ ababa ⇒ baaba ⇒ baaab
It is clear that w derives any permutation of w.
As a second example, with productions {ab → ba, ba → Λ}
w derives Λ (the empty word) if and only if w has the same number of as as bs.
The question of whether w derives w′ is algorithmically undecidable.
Each pair 〈li,ri〉 is a rule, referred to as a production, with left-hand side li and right-hand side ri; it is usually written li → ri
Let u and v be Σ-words, and l → r be a production, then the word ulv is said to directly derive the word urv; this is written ulv ⇒ urv
So w directly derives w′ if w′ is the result of applying a production to some substring of w. If w1 ⇒ w2 ⇒ … ⇒ wn–1 ⇒ wn
then w1 is said to derive wn; this is written w1 ⇒∗ wn
So w derives w′ if w′ is obtained from w by a sequence of direct derivations.
As one example, let Σ be {a,b} and let the productions be {ab → ba, ba → ab}
then aabba derives baaab by the sequence aabba ⇒ ababa ⇒ baaba ⇒ baaab
It is clear that w derives any permutation of w.
As a second example, with productions {ab → ba, ba → Λ}
w derives Λ (the empty word) if and only if w has the same number of as as bs.
The question of whether w derives w′ is algorithmically undecidable.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
semi-Thue system