形式语言

维基百科,自由的百科全书
跳转至: 导航搜索

数学逻辑计算机科学中,形式语言英语Formal language)是用精确的数学或机器可处理的公式定义的语言。

语言学中语言一样,形式语言一般有两个方面: 语法语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论,它只研究语言的语法而不致力于它的语义。在形式语言理论中,形式语言是一个字母表上的某些有限长字符串集合。一个形式语言可以包含无限多个字符串。

语言的形式定义[编辑]

字母表 Σ 为任意有限集合,ε 表示空串, 记 \Sigma ^{0} 为{ε},全体长度为 n 的字串为\Sigma ^{n}\Sigma ^{*}\Sigma ^{0}\cup \Sigma ^{1}\cup \cdots \cup \Sigma ^{n}\cup \cdots , 语言 L 定义为\Sigma ^{*}的任意子集。

注记:\Sigma ^{*}空子集 ∅ 与 {ε} 是两个不同的语言。

语言间的运算[编辑]

语言间的运算就是 Σ*幂集上的运算。

  • 字符串集合的等运算。
  • 连接运算:L1L2 = { xy | x 属于L1并且 y 属于L2 }。
  • 幂运算:Ln = L … L (共 n 个 L 连接在一起),L0 = {ε}。
  • 闭包运算:L* = L0∪L1∪…∪Ln∪…。
  • 右商运算:L1/L2 = {x | 存在 y 属于L2使得 xy 属于L1}。
  • S ⊆ Σ* 是一个语言,S 的补语言定义为集合 {ω | ω ∈ Σ* 且 ω ∉ S}

语言的表示方法[编辑]

一个形式语言可以通过多种方法来限定自身,比如:

参见[编辑]

參考文獻[编辑]

  • Hamilton, A. G. Logic for Mathematicians. Cambridge University Press. 1978. ISBN 0-521-21838-1. 
  • Ginsburg, Seymour. Algebraic and automata theoretic properties of formal languages. North-Holland. 1975. ISBN 0-7204-2506-9. 
  • Harrison, Michael A. Introduction to Formal Language Theory. Addison-Wesley. 1978. 
  • Hopcroft, John E.; Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Reading, Massachusetts: Addison-Wesley Publishing. 1979. ISBN 0-201-02988-X. 
  • Rozenberg, Grzegorz; Arto Salomaa. Handbook of Formal Languages: Volume I-III. Springer. 1997. ISBN 3-540-61486-9. 
  • Suppes, Patrick. Introduction to Logic. D. Van Nostrand. 1957. ISBN 0-442-08072-7. 

外部链接[编辑]