semi-Thue system

Quick Reference

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 sideli and right-hand sideri; it is usually written liri Let u and v be Σ-words, and lr be a production, then the word ulv is said to directly derive the word urv; this is written ulvurv So w directly derives w′ if w′ is the result of applying a production to some substring of w. if w1w2 ⇒ … ⇒ wn−1wn then w1 is said to derivewn; this is written So w derives w′ if w′ is obtained from w by a sequence of direct derivations.




w1w2 ⇒ … ⇒ wn−1wn

As one example, let Σ be {a,b} and let the productions be {abba, baab} then aabba derives baaab by the sequence aabbaabababaababaaab It is clear that w derives any permutation of w.

{abba, baab}


As a second example, with productions {abba, ba → Λ} w derives Λ (the empty word) if and only if w has the same number of as as bs.

{abba, ba → Λ}

The question of whether w derives w′ is algorithmically undecidable.

Subjects: Computing.

Reference entries