“semi-Thue system”的概念、定义、翻译、参考文献-科学参考

semi-Thue system

Computer

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} 〉, \dots, 〈 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} \to 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
$u l v \Rightarrow u r v$
So w directly derives w′ if w′ is the result of applying a production to some substring of w. if
$w_{1} \Rightarrow w_{2} \Rightarrow \dots \Rightarrow w_{n - 1} \Rightarrow w_{n}$
then w₁ is said to derive w_n; this is written
$w_{1} \overset{⋆}{\Rightarrow} 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
${a b \to b a, b a \to a b}$
then aabba derives baaab by the sequence
$a a b b a \Rightarrow a b a b a \Rightarrow b a a b a \Rightarrow b a a a b$
It is clear that w derives any permutation of w.
As a second example, with productions
${a b \to b a, b a \to Λ}$
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.

单词	semi-Thue system
释义	semi-Thue system Computer 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} 〉, \dots, 〈 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} \to 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 $u l v \Rightarrow u r v$ So w directly derives w′ if w′ is the result of applying a production to some substring of w. if $w_{1} \Rightarrow w_{2} \Rightarrow \dots \Rightarrow w_{n - 1} \Rightarrow w_{n}$ then w₁ is said to derive w_n; this is written $w_{1} \overset{⋆}{\Rightarrow} 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 ${a b \to b a, b a \to a b}$ then aabba derives baaab by the sequence $a a b b a \Rightarrow a b a b a \Rightarrow b a a b a \Rightarrow b a a a b$ It is clear that w derives any permutation of w. As a second example, with productions ${a b \to b a, b a \to Λ}$ 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.
随便看	socionature Société Française de Statistique sock puppet Socrates (469–399) Socratic fallacy Socratic irony Socratic method Socratic paradox SOD soda soda ash soda lake soda lime sodalite sodamide soda nitre Soddy, Frederick Soddy, Frederick (1877–1956) sodication sodic soil sodic soils sodium sodium acetate sodium-adsorption ratio sodium aluminate