形式语言

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

相关

  • 青霉素青霉素(Penicillin,或音译盘尼西林)是指分子中含有青霉烷、能破坏细菌的细胞壁并在细菌细胞的繁殖期起杀菌作用的一类抗生素,是由青霉菌中提炼出的抗生素。青霉素属于β-内酰胺
  • 蜱传脑炎蜱传脑炎疫苗(Tick-borne encephalitis vaccine)是用于预防蜱传脑炎(英语:tick-borne encephalitis)的疫苗。蜱传脑炎在中欧、东欧与北亚最为盛行。接种过疫苗的人里面有超过87%
  • 头孢维星头孢维星(久安)(Cefovecin,INN)是第三代的头孢类抗菌药,用于治疗猫狗的皮肤感染。头孢维星(久安)由硕腾公司(原辉瑞公司)上市,临床上使用钠盐。商品名为康卫宁(台湾为久安)(Conven
  • 船舰船或船舶,指的是:举凡利用水的浮力,依靠人力、风帆、发动机(如蒸气机、燃气涡轮、柴油引擎、核子动力机组)等动力,牵、拉、推、划、或推动螺旋桨、高压喷嘴,使能在水上移动的交通运
  • 前驱物前体(英文:precursor),又称前驱物。在化学领域,前体是一种可以参与化学反应的化学物质,其反应结果是生成另一种化学物质。一个简单的例子是,甲烷可称作一氯甲烷的前体。在生物化学
  • 乙胺嘧啶乙胺嘧啶(英语:Pyrimethamine)商品名叫达拉匹林(Daraprim),是一种可以与甲酰四氢叶酸治疗一起弓形虫病和等孢球虫病的药物。还与氨苯砜一起用于预防HIV / AIDS患者的肺孢子虫肺炎(P
  • 塔罗糖塔罗糖(Talose)是一种己醛糖。可溶于水,微溶于醇类,存在于某些植物和细菌中,可由葡萄糖或甘露糖经化学反应制备。用于土壤细菌毒性基因的表达控制研究。果聚糖:菊粉 · 果聚糖β
  • 类淀粉蛋白淀粉样物质(英语:amyloid)是一种不可溶的纤维性蛋白质,“淀粉样物质”,港澳台称为“类淀粉蛋白”。在器官中不正常的堆积,会造成类淀粉沉积症(amyloidosis)。在许多神经性疾病,如阿兹
  • 胰岛素依赖型糖尿病1型糖尿病(旧称青少年糖尿病或胰岛素依赖型糖尿病)是糖尿病其中一种类型,患者的身体不能产生足够的胰岛素,导致血糖水平过高,典型症状包括:多尿、口渴、易饿以及体重下降;其他症状
  • 淋病双球菌淋球菌(学名:Neisseria gonorrhoeae,奈瑟氏球菌)又称淋病双球菌(“淋”,拼音:lìn)、淋病奈瑟菌,是导致淋病的病原菌,和脑膜炎奈瑟菌同属于奈瑟菌属,是革兰氏阴性菌一个属种。球菌是需