正规语言_语言学领域术语

正规语言

语言学领域术语

正规语言又称正则语言，是形式语言与自动机理论中讨论的最基本的语言系，可以架起有穷自动机和正则表达式之间的桥梁。

正规语言的定义

设∑为有穷字母表，∑*为其Kleene闭包（见作用代数）。那么称字符串集L∈∑*为正规语言，当且仅当满足下列条件之一：

正规语言的性质

一、封闭性

二、判定准则

正则语言的应用

由于正则语言可以用有穷自动机识别，所以在进行字符串匹配时可以设计一个无回溯的分析程序。这样就可以使得字符串匹配可以在O(n)时间内完成，而且很容易编程实现。（正则语言在字符串匹配中的应用可以参见词条：正则表达式）

参考资料

最新修订时间：2023-11-10 15:17

条目作者

概述

正规语言的定义

正规语言的性质

参考资料