形式语言

✍ dations ◷ 2025-04-02 16:37:06 #形式语言
在数学、逻辑和计算机科学中,形式语言(英语: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 ^{*}} 的空子集 ∅ 与只包含空串的语言 {ε} 是两个不同的语言。语言间的运算就是 Σ*幂集上的运算。不像自然语言,一个形式语言作为一个集合,需要有某种明确的标准来定义一个字符串是否是它的元素。这可以通过多种方法来完成,下面将给出一些例子:如果一个形式语言的元素数目是有限的,那么可以通过枚举它的各个字符串来严格地定义它。通过形式文法来产生(参见乔姆斯基谱系)。正则表达式是一种很多编程语言和库都支持的语法,这种语法可以用于匹配符合一定条件的字符串,经常用于文本的搜索和过滤。从名称上来说,正则表达式应当是对应于正则语言的,在形式语言领域内所称的正则表达式确实如此。不过,在实际的编程语言中,很多正则表达式已经通过引入复杂的扩展,可以匹配正则表达式所不能描述的内容。形式语言中的正则表达式和一般编程语言中所称的正则表达式在语法上也有较大差异。直觉上来说,自动机消耗输入符号,并在自身的不同状态间转移,可以通过状态机消耗完整个字符串之后是否达到某些特定状态来定义一个字符串是否属于某一个语言。语言可以通过某种自动机来识别,比如图灵机、有限状态自动机。

相关

  • 坏死性小肠结肠炎坏死性小肠结肠炎(NEC)是一种多发于早产婴儿的疾病,可能会导致小肠坏死,严重时会危及生命。多发于早产儿,其发病率和出生时的胎龄成反比。出生越早的婴儿,越容易得NEC。初期症状
  • 替米沙坦(必康平,Micardis)替米沙坦(国际非专利药品名称:Telmisartan) 是一种血管紧张素II受体拮抗剂(英语:ARB),用于治疗高血压。现时大部分降血压药的疗效最长只能维持10小时。 替米沙坦 (Telmisartan) 的
  • 脊灰脊髓灰质炎(英语:poliomyelitis,简称polio),俗称小儿麻痹症(中文名称译自日语“小児麻痺”;后者则译自英语infantile paralysis),又译急性灰白髓炎。是由脊髓灰质炎病毒引起,可感染人
  • 人工心脏人工器官(英语:Artificial organs)是用人工材料制成,能部分或全部代替人体自然器官功能的部件。目前,除人工大脑外,几乎人体各个器官都在进行人工模拟研制中。不少人工制造的器官
  • 政党美国一直有两大主要政党。从十九世纪六十年代开始,最大的两大政党一直是民主党和共和党。目前共和党是美国国会参议院多数党;而美国国会众议院多数党则是民主党。除两党外,还有
  • 西进时期美国旧西部(American Old West或Wild West)是指美国领土扩张时期,美国西部的历史、地理、居民、文化等多元内涵,这段时间从十七世纪初的英国美洲殖民地到1912年建立最后一个美国
  • 醋酸铅2.55 g/cm3(三水合物)75 °C(三水合物分解)乙酸铅,又称醋酸铅,是一种白色晶体状化合物,带甜味。将铅黄(一氧化铅)和乙酸反应可以制备乙酸铅。和其他铅化合物一样,乙酸铅也有很大毒性
  • 剑桥大学出版社剑桥大学出版社(英语:Cambridge University Press)隶属于英国剑桥大学,成立于1534年,是世界上仅次于牛津大学出版社的第二大大学出版社。剑桥大学出版社为世上现存最古老的大学出
  • 胆癌胆癌是发生在胆部的恶性肿瘤,常见的有胆管癌、胆囊癌和肝外胆管癌三种。胆癌并不常见,通常会发生在六至七十岁人士身上。原发性胆管癌较少见,性别以男性为多。中上腹及右上腹疼
  • 白化病白化症(Albinism、albino)是由于体内黑色素缺乏,导致眼呈红色、毛发与皮肤颜色呈现白色;若虹膜并非红色而呈蓝或灰色,且肤色及毛发偏淡或颜色不均而非纯白,则是白色亚种而非白化症