首页 >
形式语言
✍ dations ◷ 2025-12-05 12:50:39 #形式语言
在数学、逻辑和计算机科学中,形式语言(英语: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 ^{*}}
的空子集 ∅ 与只包含空串的语言 {ε} 是两个不同的语言。语言间的运算就是 Σ*幂集上的运算。不像自然语言,一个形式语言作为一个集合,需要有某种明确的标准来定义一个字符串是否是它的元素。这可以通过多种方法来完成,下面将给出一些例子:如果一个形式语言的元素数目是有限的,那么可以通过枚举它的各个字符串来严格地定义它。通过形式文法来产生(参见乔姆斯基谱系)。正则表达式是一种很多编程语言和库都支持的语法,这种语法可以用于匹配符合一定条件的字符串,经常用于文本的搜索和过滤。从名称上来说,正则表达式应当是对应于正则语言的,在形式语言领域内所称的正则表达式确实如此。不过,在实际的编程语言中,很多正则表达式已经通过引入复杂的扩展,可以匹配正则表达式所不能描述的内容。形式语言中的正则表达式和一般编程语言中所称的正则表达式在语法上也有较大差异。直觉上来说,自动机消耗输入符号,并在自身的不同状态间转移,可以通过状态机消耗完整个字符串之后是否达到某些特定状态来定义一个字符串是否属于某一个语言。语言可以通过某种自动机来识别,比如图灵机、有限状态自动机。
相关
- 巨人症巨人症,亦称为巨大症,是一种疾病,表现为过度生长且其身高明显高于人类平均身高。该疾病是由于人类在童年时期生产过多的生长激素,使得患者身高异于常人,达2.13米(7.0英尺)至2.74米(9
- Sabin-Feldman 染色试验弓形虫染色试验,又名萨宾-费尔德曼染色试验,是一个用于诊断弓虫症的血清学试验,实验原理是某些抗体会阻止亚甲蓝染液进入弓形虫生物的细胞质。用弓形虫滋养体和补体作为激活剂
- 死亡行军死亡行军 是一个针对战俘或其他俘虏或被驱逐出境者的强迫行军,旨在令他们死在途中,这就把它们从一般单纯的用徒步行军去运送囚犯区分出来。死亡行军通常包含严苛的体力劳动和
- 粮食安全粮食安全指的是能够稳定地让所有人取得足够食物的状态。联合国政府间气候变化专业委员会曾于2014年3月31日在日本横滨召开会议时发表了一份报告,报告中指出:“气候变迁正冲击
- 忧郁型抑郁障碍忧郁型抑郁障碍,表现为患者对绝大多数或者所有活动失去兴趣,对于愉快的刺激失去反应,抑郁心境且比丧恸或失去亲人更严重,在早上情况更差,早醒,精神运动性阻滞,体重迅速降低(注意与神
- 柳氮磺胺吡啶柳氮磺胺吡啶(Sulfasalazine),缩写为SSZ,是一种磺胺类药物,可用于治疗类风湿性关节炎、溃疡性结肠炎,以及克罗恩病。柳氮磺胺吡啶最早于1950年在美国获批上市,目前仍然是治疗类风湿
- 脑血管障壁脑血管障壁(英语:blood–brain barrier ,BBB),也称为血脑屏障或血脑障壁,指在血管和脑之间有一种选择性地阻止某些物质由血液进入大脑的“屏障”。19世纪末,保罗·埃尔利希在一个实
- 超自然超自然(Supernatural)又称灵异现象,包含了超自然现象和超自然力量,即无科学根据而所谓在自然界的力量或现象。一旦超自然能够被证实,则它就不再是超自然了。超自然超出科学的范畴
- 羊水栓塞羊水栓塞是一种罕见及未被完全了解的产科紧急症候。指在分娩过程中,羊水、胎儿细胞、胎发、胎粪、皮屑等物,透过子宫基底的胎盘进入母体血液循环而诱发母体之发炎反应。这作用
- 认知语言学认知语言学是语言学的一门颇新分支,它脱胎自认知心理学或认知科学,大约在1980年代后期至1990年代开始成型。认知语言学涉及电脑自然语言理解、人工智能、语言学、心理学、神经
