“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.
随便看	Chile Rise Chile saltpetre chiliagon chilidial plates chilidium CHILL chilled edge chilled margin chill haze chilling Chilopoda Chilton, Cecil Hamilton (1918–72) Chilton, Kevin Patrick (1954– ) Chilton, Thomas Hamilton (1899–1973) Chilton–Colburn analogy chimaera Chime chimera Chimú China China 1 china clay China Development Bank China-Japan Peace and Friendship Treaty (1978) China National Space Administration