首页 >
形式语言
✍ dations ◷ 2025-04-04 21:02:29 #形式语言
在数学、逻辑和计算机科学中,形式语言(英语: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 ^{*}}
的空子集 ∅ 与只包含空串的语言 {ε} 是两个不同的语言。语言间的运算就是 Σ*幂集上的运算。不像自然语言,一个形式语言作为一个集合,需要有某种明确的标准来定义一个字符串是否是它的元素。这可以通过多种方法来完成,下面将给出一些例子:如果一个形式语言的元素数目是有限的,那么可以通过枚举它的各个字符串来严格地定义它。通过形式文法来产生(参见乔姆斯基谱系)。正则表达式是一种很多编程语言和库都支持的语法,这种语法可以用于匹配符合一定条件的字符串,经常用于文本的搜索和过滤。从名称上来说,正则表达式应当是对应于正则语言的,在形式语言领域内所称的正则表达式确实如此。不过,在实际的编程语言中,很多正则表达式已经通过引入复杂的扩展,可以匹配正则表达式所不能描述的内容。形式语言中的正则表达式和一般编程语言中所称的正则表达式在语法上也有较大差异。直觉上来说,自动机消耗输入符号,并在自身的不同状态间转移,可以通过状态机消耗完整个字符串之后是否达到某些特定状态来定义一个字符串是否属于某一个语言。语言可以通过某种自动机来识别,比如图灵机、有限状态自动机。
相关
- 亚胺培南/西司他丁亚胺培南/西司他丁 (Imipenem/cilastatin),是一种用于治疗各类严重感染的复方抗生素制剂 。 它由亚胺培南和西司他丁的组合制成,通过静脉注射或肌肉注射给药 。 临床应用其钠盐
- 人口增长率人口自然增长率指一定时期内人口自然增长数(出生人数减死亡人数)与该时期内平均人口数之比,通常以年为单位计算,用千分比来表示,计算公式为:人口自然增长率 = (年内出生人数 - 年内死
- 生育控制生育控制(英语:Birth control)也称为避孕,是避免怀孕的方式或是设备。而计划生育即对生育子女的数量和时间做出计划,其中也会包括取得及使用避孕设备或方式。从远古时代以来,人类
- 雷帕霉素雷帕霉素(Rapamune),又名西罗莫司(Sirolimus),为大环内酯类化合物,现主要运用于肾移植的抗排异治疗。其通过抑制白细胞介素-2从而阻碍激活T细胞及B细胞来抑制免疫。其首次发现于复
- 真球虫目Eucoccidiida真球虫目(学名:Eucoccidiorida),是顶复门类锥体纲球虫亚纲之下的一个目,是一种单细胞的微小成胞的寄生物种。本目的原生物种可寄生在人体、家畜、家禽及野生动物的体
- 嗜酸性粒细胞增多症嗜酸性粒细胞增多症是一种疾病过程其特点是血液中的嗜酸性粒细胞计数持续性地升高(多于1500嗜酸性粒细胞/立方毫米),没有明显的病因。嗜酸性粒细胞增多症有两种形式:心内膜纤维
- 斑贴试验贴布试验,又名斑贴试验,是一种用来确定是否有特定物质会导致患者过敏性或发炎肌肤。任何人被怀疑有过敏性接触性皮肤炎(英语:Allergic contact dermatitis)或过敏性皮炎,需要经过
- 拉莫三嗪拉莫三嗪(lamotrigine;LTG、嗪/qín)。葛兰素史克注册为Lamictal,在南非称作Lamictin、以色列叫做Lamogine、在台湾称作乐命达、在韩国则称라믹탈。是一种苯三嗪类的广谱抗癫痫
- 美国食品和药物管理局美国食品药品监督管理局(英语:U.S. Food and Drug Administration,缩写为FDA)为美国卫生与公众服务部直辖的联邦政府机构,其主要职能为负责对美国国内生产及进口的食品、膳食补充
- 玻璃天花板玻璃天花板(英语:glass ceiling)是指在公司、企业和机关、团体中对某些群体(如女性、少数族裔)晋升到高级职位或决策层的潜在限制或障碍。它指正如玻璃一样,这个障碍虽然不会明文