形式语言

✍ dations ◷ 2025-04-25 03:22:10 #形式语言
在数学、逻辑和计算机科学中,形式语言(英语:Formal language)是用精确的数学或机器可处理的公式定义的语言。如语言学中语言一样,形式语言一般有两个方面:语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论,它只研究语言的语法而不致力于它的语义。在形式语言理论中,形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。语言定义在某一个特定的字母表上,字母表(经常记作 Σ )可以为任意有限集合。例如集合 { a , b , c . . . , z } {displaystyle {a,b,c...,z}} 就表示所有小写字母构成的字母表。字符串是字母表中的元素构成的有穷序列,以之前定义的小写字母表为例,“hello”,“wikipedia”,“abcjkg”都是上面的串,而“AbCd”就不是上面的串了。记号 ε 表示空串——它是一个特殊的长度为0的串。直觉上,一个语言是字母表所能构成的所有串的集合的一个子集,具体来说:对于任意一个字母表,记全体长度为 n 的子串为 Σ n {displaystyle Sigma ^{n}} ,特别的,规定 Σ 0 {displaystyle Sigma ^{0}} 为{ε},则还可以定义Σ ∗ = Σ 0 ∪ Σ 1 ∪ ⋯ ∪ Σ n ∪ ⋯ {displaystyle Sigma ^{*}=Sigma ^{0}cup Sigma ^{1}cup cdots cup Sigma ^{n}cup cdots }Σ ∗ {displaystyle Sigma ^{*}} 包含了字母表 Σ {displaystyle Sigma } 所能构成的所有字符串。语言(一般记为 L )定义为 Σ ∗ {displaystyle Sigma ^{*}} 的任意子集。下面给出一些语言的例子, { h e l l o , w o r l d } {displaystyle {hello,world}} 是一个包含两个字符串的集合,也可以被视为小写字母构成的字母表上的一个语言。而实际上研究的语言的例子则常常更为复杂,例如所有合法的C语言程序串构成的集合也可以视作ASCII上的一个语言(假定编译器只支持英文符号)。需要注意的一点是, Σ ∗ {displaystyle Sigma ^{*}} 的空子集 ∅ 与只包含空串的语言 {ε} 是两个不同的语言。语言间的运算就是 Σ*幂集上的运算。不像自然语言,一个形式语言作为一个集合,需要有某种明确的标准来定义一个字符串是否是它的元素。这可以通过多种方法来完成,下面将给出一些例子:如果一个形式语言的元素数目是有限的,那么可以通过枚举它的各个字符串来严格地定义它。通过形式文法来产生(参见乔姆斯基谱系)。正则表达式是一种很多编程语言和库都支持的语法,这种语法可以用于匹配符合一定条件的字符串,经常用于文本的搜索和过滤。从名称上来说,正则表达式应当是对应于正则语言的,在形式语言领域内所称的正则表达式确实如此。不过,在实际的编程语言中,很多正则表达式已经通过引入复杂的扩展,可以匹配正则表达式所不能描述的内容。形式语言中的正则表达式和一般编程语言中所称的正则表达式在语法上也有较大差异。直觉上来说,自动机消耗输入符号,并在自身的不同状态间转移,可以通过状态机消耗完整个字符串之后是否达到某些特定状态来定义一个字符串是否属于某一个语言。语言可以通过某种自动机来识别,比如图灵机、有限状态自动机。

相关

  • 喘息喘鸣(英语:Wheeze, Sibilant Rhonchi),又称啰音,是指呼吸过程中呼吸道持续产生的粗糙声音。哮鸣发生的原因是由于呼吸道的某些部分缩小或被堵塞,亦可能是呼吸道内的气流速度提高。
  • 血液透析血液透析(英语:Hemodialysis),是将血液抽出体外,经过血液透析机的渗透膜,清除血液中的新陈代谢废物和杂质后,再将已净化的血液输送回体内,俗称“洗肾”及“洗血”。血液透析可用于肾
  • 造血作用造血作用(英语:Haematopoiesis,其它拼法为haemopoiesis或hemopoiesis,在美式英语中也被拼作hematopoiesis;源自古希腊语中意为“血液”的词汇αἷμα以及意为“创造”的词汇πο
  • 北美地区北美地区(英语:Northern America;西班牙语:Norteamérica;法语:L'Amerique septentrionale)为地缘政治地理学的概念,指的是美洲的北部地区,以文化区分法又称盎格鲁美洲,属于北美洲大陆
  • 棉子糖棉子糖(英语:Raffinose,也称棉籽糖、蜜三糖。结构式为:α-D-半乳糖-α-D-葡萄糖-β-D-果糖)是主要存在于棉子和甜菜中一种非还原性三糖,在所有三糖中与人类的关系较大,因为棉子饼可
  • NNL坐标:31°46′33.01″N 35°11′48.58″E / 31.7758361°N 35.1968278°E / 31.7758361; 35.1968278以色列国家图书馆(希伯来语:.mw-parser-output .script-hebrew,.mw-parser-
  • 现实现实(拉丁语:Realitas)在日常应用时意味着“客观存在的事物”或“合于客观情况的条件”。现实是所有实际事物或是存在事物的总和,和全然想像虚构的事物相反。现实一词也常用来表
  • 珊瑚蛇详见内文珊瑚蛇(Coral snake)是蛇亚目眼镜蛇科下拥有大量品种的一种有毒蛇类。此类蛇能分成两个种类,其一是分布于欧亚非大陆(或称旧大陆)地区的丽纹蛇属(Calliophis);另一种为分布
  • 鳃是一种器官,很多水生动物依靠它将溶解在水中的氧气吸收到血液中。这种呼吸方式被称为鳃呼吸。最近的研究表明,鳃的进化起初并非为了呼吸,而是用来调节体液平衡,避免脱水。鳃被
  • 唯名论唯名论(英语:Nominalism),形而上学的观点之一,根源于古希腊柏拉图学派,经中古欧洲经院哲学家发展,长时间成为哲学探讨的主题。在哲学中,它是一种形而上学的争论,它讨论的是关于事物的