“Parikh’s theorem”的概念、定义、翻译、参考文献-科学参考

Parikh’s theorem

Computer

A theorem in formal language theory that concerns the nature of context-free languages when order of letters is disregarded.
Let the alphabet Σ‎ be the set {a₁,…,a_n}. The letter distribution, ϕ‎(w), of a Σ‎-word w is the n-tuple
$〈 N_{1}, \dots, N_{n} 〉$
with N_i the number of occurrences of a_i in w. The Parikh image, ϕ‎(L), of a Σ‎-language L is
${ϕ (w) | w \in L}$
i.e. the set of all letter-distributions of words in L. L₁ and L₂ are letter-equivalent if
$ϕ (L_{1}) = ϕ (L_{2})$
Letter distributions may be added component-wise as vectors. This leads to the following: a set S of letter distributions is linear if, for some distributions d and d₁,…,d_k, S is the set of all sums formed from d and multiples of d_i. S is semilinear if it is a finite union of linear sets.
Parikh’s theorem now states that if L is context-free ϕ‎(L) is semilinear. It can also be shown that ϕ‎(L) is semilinear if and only if L is letter-equivalent to a regular language. Hence any context-free language is letter-equivalent to a regular language—although not all such languages are context-free.

单词	Parikh’s theorem
释义	Parikh’s theorem Computer A theorem in formal language theory that concerns the nature of context-free languages when order of letters is disregarded. Let the alphabet Σ‎ be the set {a₁,…,a_n}. The letter distribution, ϕ‎(w), of a Σ‎-word w is the n-tuple $〈 N_{1}, \dots, N_{n} 〉$ with N_i the number of occurrences of a_i in w. The Parikh image, ϕ‎(L), of a Σ‎-language L is ${ϕ (w) \| w \in L}$ i.e. the set of all letter-distributions of words in L. L₁ and L₂ are letter-equivalent if $ϕ (L_{1}) = ϕ (L_{2})$ Letter distributions may be added component-wise as vectors. This leads to the following: a set S of letter distributions is linear if, for some distributions d and d₁,…,d_k, S is the set of all sums formed from d and multiples of d_i. S is semilinear if it is a finite union of linear sets. Parikh’s theorem now states that if L is context-free ϕ‎(L) is semilinear. It can also be shown that ϕ‎(L) is semilinear if and only if L is letter-equivalent to a regular language. Hence any context-free language is letter-equivalent to a regular language—although not all such languages are context-free.
随便看	rain-wash Rainwater, (Leo) James raised beach raised bog raised cosine window raise(to a power) Rajagopalachariar, Chakravarti (1878–1972) Rajput rake Raketoplan raking Rakosi, Matyas (1892–1971) RAL Raleigh, Sir Walter (1552–1618) RAM r.a.m. Ramachandran plot Ramakrishna movement Raman effect Raman, Sir Chandrasekhara Venkata Ramanuja (1137) Ramanujan, Srinivasa (1887–1920) Ramanujan, Srinivasa Iyengar Ramapithecus Ramaty High-Energy Solar Spectroscopic Imager