形式语言

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

相关

  • 药理学药理学(英语:Pharmacology),是研究药品与有机体(含病原体)相互作用及作用规律的学科。它既研究药品对生物的作用及作用机制,即药品效应动力学(Pharmacodynamics,简称药效学);也研究药品
  • 人造卫星人造卫星,在不产生歧义的情况下亦称卫星,是由人类建造的航天器的一种,是数量最多的一种。人造卫星以太空飞行载具如运载火箭、航天飞机等发射到太空中,像天然卫星一样环绕地球或
  • 伽马射线伽玛射线(或γ射线)是原子衰变裂解时放出的射线之一。此种电磁波波长在0.01纳米以下,穿透力很强,又携带高能量,容易造成生物体细胞内的脱氧核糖核酸(DNA)断裂进而引起细胞突变,因此
  • 钙调磷酸酶1AUI, 1M63, 1MF8, 2JOG, 2JZI, 2P6B, 2R28, 2W73· calcium-dependent protein serine/threonine phosphatase activity · calcium ion binding · protein binding ·
  • 大平原区大平原(英语:Great Plains),多称北美大平原、北美大草原,是北美洲中部一块广袤的平原地区,大致位于密西西比河以西、落基山脉以东、格兰德河以北。自然植被以草为主。大平原东西长
  • 内皮细胞内皮细胞或血管内皮是一薄层的专门上皮细胞,由一层扁平细胞所组成。它形成血管的内壁,是血管管腔内血液及其他血管壁(单层鳞状上皮)的界面。内皮细胞是沿着整个循环系统,由心脏直
  • 萨延बाप तहसील घंटियाली 城镇萨延(Sayan),是印度古吉拉特邦Surat县的一个城镇。总人口12856(2001年)。该地2001年总人口12856人,其中男性7258人,女性5598人;0—6岁人口
  • 体感体感,或称躯体感觉,是触觉、压觉、温觉、痛觉和本体感觉(关于肌肉和关节位置和运动、躯体姿势和运动以及面部表情的感觉)的总称。体感是和特殊感觉相对的一个概念。这些不同的体
  • 表皮癣菌表皮癣菌属(学名:Epidermophyton)是子囊菌门的一属真菌,只包含两个物种,其中絮状表皮癣菌(Epidermophyton floccosum)是能造成皮肤感染的真菌之一,能感染皮肤与指甲,造成足癣、股癣、
  • 先天性水痘症候群先天性水痘症候群(Costello syndrome),又名小黑人症、克斯提洛氏弹性蛋白缺陷症、科斯特洛综合症、面肌肉骨骼综合症(faciocutaneoskeletal syndrome)或FCS综合症等各种名称,是一