首页 >
形式语言
✍ dations ◷ 2025-04-03 17:05:15 #形式语言
在数学、逻辑和计算机科学中,形式语言(英语: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 ^{*}}
的空子集 ∅ 与只包含空串的语言 {ε} 是两个不同的语言。语言间的运算就是 Σ*幂集上的运算。不像自然语言,一个形式语言作为一个集合,需要有某种明确的标准来定义一个字符串是否是它的元素。这可以通过多种方法来完成,下面将给出一些例子:如果一个形式语言的元素数目是有限的,那么可以通过枚举它的各个字符串来严格地定义它。通过形式文法来产生(参见乔姆斯基谱系)。正则表达式是一种很多编程语言和库都支持的语法,这种语法可以用于匹配符合一定条件的字符串,经常用于文本的搜索和过滤。从名称上来说,正则表达式应当是对应于正则语言的,在形式语言领域内所称的正则表达式确实如此。不过,在实际的编程语言中,很多正则表达式已经通过引入复杂的扩展,可以匹配正则表达式所不能描述的内容。形式语言中的正则表达式和一般编程语言中所称的正则表达式在语法上也有较大差异。直觉上来说,自动机消耗输入符号,并在自身的不同状态间转移,可以通过状态机消耗完整个字符串之后是否达到某些特定状态来定义一个字符串是否属于某一个语言。语言可以通过某种自动机来识别,比如图灵机、有限状态自动机。
相关
- 碳2s2 2p22, 4第一:1086.5 kJ·mol−1 第二:2352.6 kJ·mol−1 第三:4620.5 kJ·mol−1 (钻石六方主条目:碳的同位素碳(Carbon,拉丁文意为煤炭)是一种化学元素,符号为C,原子序数为6,
- 逆转录酶抑制剂核苷类逆转录酶抑制剂(英语:Nucleoside Reverse Transcriptase Inhibitors,简称NRTIs),是合成HIV的DNA逆转录酶底物脱氧核苷酸的类似物,在体内转化成活性的三磷酸核苷衍生物,与天然
- 窒息窒息(英语:asphyxia)在医学上,是人体严重缺氧的一个状况。它的成因很多,严重可导致死亡。在急救上的定义为“气道遭外来物件阻塞而无法呼吸”。在法医学上则指因缺氧而死亡,窒息是
- 四病毒科四病毒科(Tetraviridae)代表种:代表种:
- 立法机构多数党(53)少数党(47)多数党(233)少数党(198)空缺(4)美国国会(英语:United States Congress)是《美国宪法》规定的立法机构,位于国会大厦。根据《美国宪法》,美国是一个三权分立的国家,其中
- 吸收吸收,在物理学上是光子的能量由另一个物体,通常是原子的电子,拥有的过程,因此电磁能会转换成为其它的形式,例如热能。波传导的过程中,光线的吸收通常称为衰减。例如,一个原子的价电
- La5d1 6s22, 8, 18, 18, 9, 2蒸气压第一:538.1 kJ·mol−1 第二:1067 kJ·mol−1 第三:1850.3 kJ·mol主条目:镧的同位素镧,是一种化学元素,元素符号为La,原子序数为57。是一种柔
- 上腔静脉上腔静脉(拉丁语:superior vena cava)是一条粗短的静脉干,下端连于右心房上缘,上端由左、右头臂静脉(无名静脉)在右侧第一胸肋结合处的后方汇合而成,垂直下降,在平对第三胸肋关节的下
- 教宗国教宗国(拉丁语:Civitas Ecclesiae;意大利语:Stato Pontificio、Stato della Chiesa;又译为教皇国、教皇领)是南欧一个已经不存在的国家,为教宗统治的世俗领地,建立于8世纪,位于亚平宁
- 急性淋巴性白血病急性淋巴性白血病(英语:Acute lymphoblastic leukemia,ALL),是因为体内淋巴细胞不正常增生造成的血液疾病。淋巴是人体免疫系统的重要环节,由骨髓与淋巴结所制造。而急性淋巴性白