首页 形式语言

形式语言复习一

本文记录绪论部分，绪论部分有和集合论与图论重合的部分，可以略看

# 集合的基础知识

# 集合及其表示

  • 集合：一定范围内的、确定的、并且彼此可以区分的对象汇集在一起形成的整体叫做集合，简称集

  • 元素：集合的成员为该集合的元素

  • 集合描述形式：列举法、命题法

  • 基数

# 集合的运算

  • 并（A∪BA\cup B）
  • 交（A∩BA\cap B）
  • 差（A−BA-B）
  • 对称差（A⊕BA\oplus B）
  • 笛卡尔积（A×BA\times B）
  • 幂集（2A2^A）
  • 补集（Aˉ\bar{A}）

# 关系

# 二元关系

  • 二元关系：

    • 任意的R⊆A×BR\subseteq A\times B，RR 是AA 到BB 的二元关系

    • (a,b)∈R(a,b)\in R，也可表示为：aRbaRb

    • AA 称为定义域，BB 称为值域

    • 当A=BA=B 时，则称RR 是AA 上的二元关系

  • 二元关系性质：

    • 自反性、反自反性、对称性、反对称性、传递性

  • 等价关系：

    • 具有自反性、对称性、传递性的二元关系称为等价关系

  • 等价类：

    • SS 满足如下要求的划分：S1,S2,...,Sn,...S_1,S_2,...,S_n,... 称为SS 关于RR 的等价划分，SiS_i 称为等价类

      • S=S1∪S2∪S3∪...∪Sn...;S=S_1\cup S_2\cup S_3\cup...\cup S_n...;

      • 如果i≠ji\neq j，则Si∩Sj=ϕ;S_i\cap S_j = \phi;

      • 对于任意的i,Sii,S_i 中的任意两个元素a,ba,b、aRbaRb 恒成立

      • 对于任意的i,j,i≠j,Sii,j,i\neq j,S_i 中任意元素aa 和SjS_j 中任意元素b,aRbb,aRb 恒不成立

  • 关系的合成：

    • 设R1⊆A×BR_1\subseteq A\times B 是AA 到BB 的关系，R2⊆B×CR_2\subseteq B\times C 是BB 到CC 的关系，R1R_1 与R2R_2 的合成R1⋅R2R_1\cdot R_2 是AA 到CC 的关系：

    • R1⋅R2={(a,c)∣∃(a,b)∈R1,(b,c)∈R2}R_1\cdot R_2 ={\{}(a,c)\vert\exists (a,b)\in R_1,(b,c)\in R_2{\}}

# 关系的闭包

  • 闭包：

    • 设 P 是关于关系性质的集合，关系 R 的 P 闭包是包含 R 并且具有 P 中所有性质的最小关系

  • 正闭包：

    • R⊆R+R\subseteq R^+

    • 如果(a,b),(b,c)∈R+(a,b),(b,c)\in R^+，则(a,c)∈R+(a,c)\in R^+

    • 除前两个条件外，R+R^+ 不再含有其他任何元素

    • R+=R∪R2∪...RnR^+=R\cup R^2\cup ...R^n

    • 当SS 为有穷集时:

      R+=R∪R2∪...∪R∣S∣R^{+}=R\cup R^{2}\cup...\cup R^{\vert S\vert}

  • 传递闭包：

    • 具有传递性的闭包
    • R+R^+ 具有传递性

  • 克林闭包

    • R0⊆R∗,R⊆R∗R^0\subseteq R^*,R\subseteq R^*
    • 如果(a,b),(b,c)∈R∗(a,b),(b,c)\in R^*，则(a,c)∈R∗(a,c)\in R^*
    • 除前两个条件外，R∗R^* 不再含有其他元素
    • R∗R^* 具有自反性、传递性
    • R∗=R0∪R+R^*=R^0\cup R^+

# 递归定义与归纳证明

  • 递归定义：
    • 又称为归纳定义，它来定义一个集合
    • 集合的递归定义由三部分组成：
      • 基础：用来定义该集合的最基本的元素
      • 归纳：指出用集合中的元素来构造集合的新元素的规则
      • 极小性限定：指出一个对象是所定义集合中的元素的充要条件是它可以通过有限次的使用基础和归纳条款中所给的规定构造出来
  • 归纳证明：
    • 与递归定义向对应
    • 归纳证明方法包括三大步
      • 基础：证明最基本元素具有相应性质
      • 归纳：证明如果某些元素具有相应性质，则根据这些元素所规定的方法得到的新元素也具有相应的性质
      • 根据归纳性原理，所有的元素具有相应的性质

# 语言

  • 什么事语言

    • 语言是一定的群体用来进行交流的工具
    • 语言：某个集合中的元素，按照规则组合成的符号串的集合

  • 形式语言理论

    用数学的方法，对语言的表示法、结构及特性进行研究的理论

    • 怎么去构造语言
    • 怎么去识别语言
    • 怎么去分析语言的定义

  • 形式语言与自动机理论的产生：

    • 对语言研究的三个方面：
      • 如何表示语言
      • 是否存在有穷描述
      • 具有有穷描述的语言结构如何，有什么特性

  • 形式语言理论：乔姆斯基发现文法，用文法产生语言的每个句子

  • 自动机理论：克林在研究神经细胞中，建立了识别语言的系统 —— 有穷状态自动机

  • 文法与自动机是等价的

  • 文法与自动机的运算对象：集合

# 基本概念

  • 字母表：

    • 字母表是一个非空有穷集合，字母表中的元素称为该字母表的一个字母。又叫做符号，或者字符
    • 字符的两个特性：
      • 整体性，也叫不可分性
      • 可辨认性，也叫可区分性

  • 字母表的乘积

    Σ1⋅Σ2={ab∣a∈Σ1,b∈Σ2}\Sigma_1\cdot\Sigma_2={\{}ab\vert a\in\Sigma_1,b\in\Sigma_2{\}}

    例如：{0,1}{0,1}=

  • 字母表Σ\Sigma 的 n 次幂

    Σ0={ϵ}Σn=Σn−1Σ\Sigma^0={\{}\epsilon{\}}\\\Sigma^n=\Sigma^{n-1}\Sigma

    ϵ\epsilon 是由Σ\Sigma 中的 0 个字符组成

  • Σ\Sigma 的正闭包和克林闭包

    Σ+=Σ∪Σ2∪...∪Σ∞\Sigma^+=\Sigma\cup\Sigma^2\cup...\cup\Sigma^{\infty}，是至少一个字符连接而成的字符串

    Σ∗=Σ0∪Σ∪...∪Σ∞\Sigma^*=\Sigma^0\cup\Sigma\cup...\cup\Sigma^{\infty}，若干个字符（包括 0 个）字符连接成的字符串

  • 句子

    Σ\Sigma 是一个字母表，∀x∈Σ∗,x\forall x\in\Sigma^*,x 叫做Σ\Sigma 的一个句子

  • 句子的长度

    • ∀x∈Σ∗\forall x\in\Sigma^*，句子xx 中字符出现的总个数叫做该句子的长度，记作∣x∣\vert x\vert
    • 长度为 0 的句子叫做空句子，记作ϵ\epsilon

  • 并置

    • x,y∈Σ∗,x,yx,y\in\Sigma^*,x,y 的并置是由串xx 直接相接串yy 所组成的。记作xyxy。并置又叫做连结

  • 串的 n 次幂

    • x0=ϵx^0=\epsilon
    • xn=xn−1xx^n=x^{n-1}x

  • 前缀与后缀

    设x,y,z,w,v∈Σ∗x,y,z,w,v\in\Sigma^*，且x=yz,w=yvx=yz,w=yv

    • yy 是xx 的前缀
    • 如果z≠ϵz\neq\epsilon，则yy 是xx 的真前缀
    • zz 是xx 的后缀
    • 如果z≠ϵz\neq\epsilon，则zz 是xx 的真后缀

  • 公共前缀与后缀

    • yy 是xx 和ww 的公共前缀
    • 如果xx 和ww 的任何公共前缀都是yy 的前缀，则yy 是xx 和ww 的最大公共前缀
    • 如果x=zy,w=vyx=zy,w=vy，则yy 是xx 和ww 的公共后缀
    • 如果xx 和ww 的任何公共后缀都是yy 的后缀，则yy 是xx 和ww 的最大公共后缀

  • 子串

    • w,x,y,z∈Σ∗w,x,y,z\in\Sigma^*，且w=xyzw=xyz，则称yy 是ww 的子串
    • 公共子串
      • t,u,v,w,x,y,z∈Σ∗t,u,v,w,x,y,z\in\Sigma^*，且t=uyv,w=xyzt=uyv,w=xyz，则称yy 是tt 和ww 的公共子串，且max{∣y1∣,∣y2∣,...,∣yn∣}=∣yj∣max{\{}\vert y_1\vert,\vert y_2\vert,...,\vert y_n\vert{\}}=\vert y_j\vert，则称yjy_j 是tt 和ww 的最大公共子串。（两个串的最大公共子串并不一定是唯一的）

  • 语言

    • ∀L⊆Σ∗,L\forall L\subseteq\Sigma^*,L 称为字母表Σ\Sigma 上的一个语言，∀x∈L,x\forall x\in L,x 叫做LL 的一个句子

  • 语言的乘积

    • L1∈Σ1∗,L2∈Σ2∗L_1\in\Sigma_1^*,L_2\in\Sigma_2^*，语言L1L_1 和L2L_2 的乘积是一个语言，该语言的定义为：L1L2={xy∣x∈L1,y∈L2}L_1L_2={\{}xy\vert x\in L_1,y\in L_2{\}} 是字母表Σ1∪Σ2\Sigma_1\cup\Sigma_2 上的语言