semi-Thue system

views updated

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 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 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 {abba, baab}

then aabba derives baaab by the sequence aabbaabababaababaaab

It is clear that w derives any permutation of w.

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.

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