## 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: {〈*l*_{1},*r*_{1}〉,…,〈*l** _{n}*,

*r*

*〉} Each pair 〈*

_{n}*l*

*,*

_{i}*r*

*〉 is a rule, referred to as a*

_{i}**production**, with

**left-hand side**

*l*

*and*

_{i}**right-hand side**

*r*

_{i}; it is usually written

*l*

*→*

_{i}*r*

*Let*

_{i}*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*

_{1}⇒

*w*

_{2}⇒ … ⇒

*w*

*⇒*

_{n−1}*w*

*then*

_{n}*w*

_{1}is said to

**derive**

*w*

_{n}; this is written So

*w*derives

*w′*if

*w′*is obtained from

*w*by a sequence of direct derivations.

{〈*l*_{1},*r*_{1}〉,…,〈*l** _{n}*,

*r*

*〉}*

_{n}*l** _{i}* →

*r*

_{i}*ulv* ⇒ *urv*

*w*_{1} ⇒ *w*_{2} ⇒ … ⇒ *w** _{n−1}* ⇒

*w*

_{n}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*.

{*ab* → *ba*, *ba* → *ab*}

*aabba* ⇒ *ababa* ⇒ *baaba* ⇒ *baaab*

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

{*ab* → *ba*, *ba* → Λ}

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

*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

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