Overview

semi-Thue system


Related Overviews

 

'semi-Thue system' can also refer to...

 

More Like This

Show all results sharing this subject:

  • Computing

GO

Show Summary Details

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.

{〈l1,r1〉,…,〈ln,rn〉}

liri

ulvurv

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}

aabbaabababaababaaab

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

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.