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: {〈l₁,r₁〉,…,〈l_n,r_n〉}

Each pair 〈l_i,r_i〉 is a rule, referred to as a production, with left-hand side l_i and right-hand side r_i; it is usually written l_i → r_i

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 w₁ ⇒ w₂ ⇒ … ⇒ w_n–1 ⇒ w_n

then w₁ is said to derive w_n; this is written w₁ ⇒∗ w_n

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.