• 中国期刊全文数据库
  • 中国学术期刊综合评价数据库
  • 中国科技论文与引文数据库
  • 中国核心期刊(遴选)数据库
黄雅玉, 潘海玉. 形式语言中近似ω-正则语言的刻画J. 桂林电子科技大学学报, 2026, 46(3): 315-322. DOI: 10.16725/j.1673-808X.202363
引用本文: 黄雅玉, 潘海玉. 形式语言中近似ω-正则语言的刻画J. 桂林电子科技大学学报, 2026, 46(3): 315-322. DOI: 10.16725/j.1673-808X.202363
Huang Yayu, Pan Haiyu. The characterization of approximate ω-regular languages in formal languagesJ. Journal of Guilin University of Electronic Technology, 2026, 46(3): 315-322. DOI: 10.16725/j.1673-808X.202363
Citation: Huang Yayu, Pan Haiyu. The characterization of approximate ω-regular languages in formal languagesJ. Journal of Guilin University of Electronic Technology, 2026, 46(3): 315-322. DOI: 10.16725/j.1673-808X.202363

形式语言中近似ω-正则语言的刻画

The characterization of approximate ω-regular languages in formal languages

  • 摘要: 针对形式语言中重要的正则语言和ω-正则语言,将它们扩展到度量背景下,有助于对正则语言和ω-正则语言进行量化。结合度量理论中距离的概念,刻画语言与自动机之间关系,进而定量分析一个自动机在多大范围内接受一个语言。基于伪度量的概念,定义近似正则语言和近似ω-正则语言,并尽可能多地保留传统正则语言和ω-正则语言相关的优良性质;再通过对度量理论中距离的定义进行扩充,然后在经典的Büchi自动机定义的基础上引入距离阈值α,从而对语言的接受条件进行量化。最后对所定义的近似ω-正则语言进行自动机刻画。

     

    Abstract: A metric framework for regular languages and ω-regular languages is proposed to facilitate their quantitative analysis. By introducing the notion of distance from metric theory, a quantitative relationship between languages and automata is established, enabling the acceptance behavior of an automaton with respect to a given language to be quantified. Based on the concept of pseudometrics, approximate regular and approximate ω-regular languages are defined while preserving as many desirable properties of classical regular and ω-regular languages as possible. Furthermore, the notion of distance is generalized, and a distance threshold α is introduced into the classical Büchi automaton framework, thereby quantifying the language acceptance conditions. Finally, an automata-theoretic characterization of the proposed approximate ω-regular languages is established.

     

/

返回文章
返回