论文标题
普通语言渐近近似
Asymptotic Approximation by Regular Languages
论文作者
论文摘要
本文调查了一种新的属性，称为Reg-Measuritible，其中Reg是常规语言类别。直观地，如果存在“收敛”到\（l \）的无限序列，则语言是可以调制的。在某种意义上，没有reg衡量性的语言具有复杂的形状，因此（渐近）无法通过普通语言近似。我们表明，几种无上下文的语言是可以使用的（包括具有先验生成功能和先验密度的语言），而某种简单的简单确定性无上下文语言和一组原始单词在很强的意义上是可以重视的。
This paper investigates a new property of formal languages called REG-measurability where REG is the class of regular languages. Intuitively, a language \(L\) is REG-measurable if there exists an infinite sequence of regular languages that "converges" to \(L\). A language without REG-measurability has a complex shape in some sense so that it can not be (asymptotically) approximated by regular languages. We show that several context-free languages are REG-measurable (including languages with transcendental generating function and transcendental density, in particular), while a certain simple deterministic context-free language and the set of primitive words are REG-immeasurable in a strong sense.
