“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.
随便看	Becquerel, Antoine Henri Becquerel, Antoine Henri (1852–1908) bed bedbug bedding bedding foliation bedding plane Bede, St (c.673–735) Bedeutung bedform bedforms bediasite bed load Bednorz, Johannes Georg bed profile bed return flow bedrock bed roughness bed volume bee beech Beecher, Lyman (1775–1863) Beehive Cluster Beekmantownian Beer–Lambert law