“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.
随便看	Rice, Condoleezza (1954) Rice–Herzfeld mechanism Rice–Ramsperger–Kassel theory Richard I (1157–99) Richard II (1367–1400) Richard III (1452–85) Richard of Wallingford Richard of York Richard Rufus (d. c.1260) Richards, Dickinson Woodruff Richards equation Richardson diagram Richardson equation Richardson extrapolation Richardson, John Francis (1920–2011) Richardson, Lewis Fry Richardson, Robert Coleman Richardson, Sir Owen Willans Richardson–Dushman equation Richardson–Lucy algorithm Richards, Paul William (1964– ) Richards, Richard Noel (1946– ) Richards, Theodore William Richard’s paradox Richelieu, Armand Jean du Plessis (1585–1642)