首页 形式语言

形式语言复习三

# 语言的识别

系统识别语言{anc∣n≥1}∪{and∣n≥1}{\{}a^nc\vert n\ge1{\}}\cup{\{}a^n d\vert n\ge1{\}} 的字符串过程中状态的变化图示如下：

例子

  • 识别系统 (模型)
    • 系统具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在不同的状态下完成规定的任务
    • 我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有字符串都是这个字母表上的字符串
    • 系统在任何一个状态 (当前状态) 下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态。当前状态和新的状态可以是同一个状态，也可以是不同的状态；当系统从输入字符串中读入一个字符后，它下一次再读时，会读入下一个字符。这就是说，相当于系统维持有一个读写指针，该指针在系统读入一个字符后指向输入串的下一个字符。
    • 系统中有一个状态，它是系统的开始状态，系统在这个状态下开始进行某个给定句子的处理。
    • 系统中还有一些状态表示它到目前为止所读入的字符构成的字符串是语言的一个句子，把所有将系统从开始状态引导到这种状态的字符串放在一起构成一个语言，该语言就是系统所能识别的语言。
    • 相应的物理模型：
      • 一个右端无穷的输入带
      • 一个有穷状态控制器 (FSC)
      • 一个读头
    • 系统的每一个动作由三个节拍构成：读入读头正注视的字符；根据当前状态和读入的字符改变有穷控制器的状态；将读头向右移动一格。

# 有穷状态自动机

  • 有穷状态自动机M=(Q,Σ,δ,q0,F)M=(Q,\Sigma,\delta,q_0,F)

    • Q—— 状态的非空有穷集合。∀q∈Q,q\forall q\in Q,q 称为MM 的一个状态

    • Σ\Sigma—— 输入字母表。输入字符串都是Σ\Sigma 上的字符串

    • q0q_0——q0∈Qq_0\in Q，是MM 的开始状态，也可以叫做初始状态或者启动状态

    • δ\delta—— 状态转移函数，又叫状态转换函数。

      • δ:Q×Σ→Q\delta:Q\times\Sigma\rightarrow Q

      • 对∀(q,a)∈Q×Σ,δ(q,a)=p\forall(q,a)\in Q\times\Sigma,\delta(q,a)=p 表示：MM 在状态qq 读入字符aa，将状态变成pp，并将读头向右移动一个带方格而指向输入字符串的下一个字符

    • FF——F⊆QF\subseteq Q，是MM 的终止状态集合。∀q∈F,q\forall q\in F,q 称为MM 的终止状态，又称为接受状态

  • 有穷状态自动机两种表示方法：

    • 状态转移表
      • 状态转移表是一个二维表，左边第二列列出有穷状态自动机的所有状态，并在第一列中标出开始状态和终止状态，上边第一行列出所有的输入字符，中间的方格内是该行所对应状态下输入该列所对应字符后转换到的新状态。
    • 状态转换图
      • q∈Q⇔qq\in Q\Leftrightarrow q 是该有向图中的一个顶点
      • δ(q,a)=p⇔\delta(q,a)=p\Leftrightarrow 图中有一条从顶点qq 到顶点pp 的标记为aa 的弧
      • q∈F⇔q\in F\Leftrightarrow 标记为qq 的顶点被用双层圈标出
      • 用标有SS 的箭头指出MM 的开始状态

  • 确定的有穷状态自动机 (DFA)

    • 对于任意的q∈Q,a∈Σ,δ(q,a)q\in Q,a\in\Sigma,\delta(q,a) 均有确定的值，所以将这种 FA 称为确定的有穷状态自动机

  • M 接受 (识别) 的语言

    对于∀x∈Σ∗\forall x\in\Sigma^*，如果δ(q0,x)∈F\delta(q_0,x)\in F，则称 x 被 M 接受；如果δ(q0,x)∉F\delta(q_0,x)\notin F，则称 M 不接受 x

    • L(M)={x∣x∈Σ∗,δ(q0,x)∈F}L(M)={\{}x\vert x\in\Sigma^*,\delta(q_0,x)\in F{\}} 称为由 M 接受 (识别) 的语言L(M1)=L(M2)=L(M_1)=L(M_2)=$0({2n)\vert n\ge1$}
    • 如果L(M1)=L(M2)L(M_1)=L(M_2)，则称M1M_1 与M2M_2 等价

  • 即时描述

    • x,y∈Σ∗,δ(q0,x)=q,xqyx,y\in\Sigma^*,\delta(q_0,x)=q,xqy 称为MM 的一个即时描述，表示xyxy 是MM 正在处理的一个字符串，xx 引导MM 从q0q_0 启动并达到状态q,Mq,M 当前正注视着yy 的首字符

    • 即时描述转换

      • 如果xqayxqay 是MM 的一个即时描述，且δ(q,a)=p\delta(q,a)=p，则xqay⊢Mxapyxqay\vdash_M xapy
      • a⊢Mnβa\vdash_M^n\beta：表示MM 从即时描述aa 经过 n 次移动到达即时描述β\beta
      • MM 存在即时描述a1,a2,...,an−1a_1,a_2,...,a_{n-1}，使得a⊢Ma1,a1⊢Ma2,...,an−1⊢Mβa\vdash_M a_1,a_1\vdash_M a_2,...,a_{n-1}\vdash_M\beta
      • 当 n=0，有a=βa=\beta。即a⊢M0aa\vdash_M^0 a
      • a⊢M+βa\vdash_M^+\beta：表示 M 从即时描述aa 经过至少 1 次移动到达即时描述β\beta
      • a⊢M∗βa\vdash_M^*\beta：表示 M 从即时描述aa 经过若干步移动到达即时描述β\beta

  • 对于任意一个FAM=(Q,Σ,δ,q0,F)FA\ M=(Q,\Sigma,\delta,q_0,F)，按照一下方式定义关系RMR_M:

    • 对∀x,y∈Σ∗,xRMy⇔∃q∈Q,\forall x,y\in\Sigma^*,xR_My\Leftrightarrow\exists q\in Q, 使得x∈set(q),y∈set(q)x\in set(q),y\in set(q) 同时成立
    • 按照这个定义所得到的关系实际上是Σ∗\Sigma^* 上的一个等价关系。利用这个等价关系，可以将Σ∗\Sigma^* 划分成不多于∣Q∣\vert Q\vert 个等价类

# NFA

# 作为对 DFA 的修改

FA 和 DFA 的区别在于：

  • 并不是对于所有的(q,a)∈Q×Σ,δ(q,a)(q,a)\in Q\times\Sigma,\delta(q,a) 都有状态与它对应
  • 并不是对于所有的(q,a)∈Q×Σ,δ(q,a)(q,a)\in Q\times\Sigma,\delta(q,a) 只对应一个状态
  • FA 在任意时刻可以处于有穷多个状态

# NFA 的形式定义

  • 不确定的有穷状态自动机 (NFA)

    • MM 是一个五元组M=(Q,Σ,δ,q0,F)M=(Q,\Sigma,\delta,q_0,F)
      • Q,Σ,q0,FQ,\Sigma,q_0,F 的意义同DFADFA
      • δ:Q×Σ→2Q\delta:Q\times\Sigma\rightarrow2^Q，对∀(q,a)∈Q×Σ,δ(q,a)={p1,p2,...,pm}\forall(q,a)\in Q\times\Sigma,\delta(q,a)={\{}p_1,p_2,...,p_m{\}} 表示MM 在状态qq 读入字符aa，可以选择地将状态变成p1p_1，或者p2p_2，...，或者pnp_n。并将读头向右移动一个带方格而指向输入字符串的下一个字符

  • FA 的状态转移图、FA 的状态对应的等价类、FA 的即时描述对 NFA 都有效

  • M 接受 (识别) 的语言

    • 对于∀x∈Σ∗\forall x\in\Sigma^*，如果δ(q0,x)∩F≠ϕ\delta(q_0,x)\cap F\neq\phi，则称xx 被 M 接受，如果δ(q0,x)∩F=ϕ\delta(q_0,x)\cap F=\phi，则称 M 不接受 x
    • L(M)={x∣x∈Σ∗,δ(q0,x)∩F≠ϕ}L(M)={\{}x\vert x\in\Sigma^*,\delta(q_0,x)\cap F\neq\phi{\}}，称为由 M 接受 (识别) 语言

  • 对于一个输入字符，NFA 可以进入若干个状态，而 DFA 只能进入一个唯一的状态

# NFA 与 DFA 等价

定理：NFA 与 DFA 等价（证明过程过于复杂，可略过）

  • 构造与M1M_1 等价的 DFA M2M_2

    • M1=(Q,Σ,δ1,q0,F)M_1=(Q,\Sigma,\delta_1,q_0,F)，M2=(Q2,Σ,δ2,[q0],F2)M_2=(Q_2,\Sigma,\delta_2,[q_0],F_2)
    • Q2=2QQ_2=2^Q，F2=F_2={[p1,p2,...,pm]∣[p_1,p_2,...,p_m]\vert{p1,p2,...,pmp_1,p_2,...,p_m}⊆Q\subseteq Q&{p1,p2,...,pmp_1,p_2,...,p_m}∩F1≠ϕ\cap F_1\neq\phi}
    • δ2([q1,q2,...,qn],a)=[p1,p2,...,pn]⇔δ1({q1,q2,...,qn},a)=\delta_2([q_1,q_2,...,q_n],a)=[p_1,p_2,...,p_n]\Leftrightarrow\delta_1({\{}q_1,q_2,...,q_n{\}},a)={p1,p2,...,pmp_1,p_2,...,p_m}

  • 证明δ1(q0,x)=\delta_1(q_0,x)={p1,p2,...,pmp_1,p_2,...,p_m}⇔δ2([q0],x)=[p1,p2,..,pm]\Leftrightarrow\delta_2([q_0],x)=[p_1,p_2,..,p_m]

    设x∈Σ∗x\in\Sigma^*，施归纳与∣x∣\vert x\vert

    x∈ϵ,δ1(q0,ϵ)=x\in\epsilon,\delta_1(q_0,\epsilon)={q0q_0}，δ2([q0],ϵ)=[q0]\delta_2([q_0],\epsilon)=[q_0]

    设当∣x∣=n\vert x\vert=n 时结论成立。下证当∣x∣=n+1\vert x\vert=n+1 时结论也成立。设x=wa,∣w∣=n,a∈Σx=wa,\vert w\vert =n,a\in\Sigma

    δ1(q0,wa)=δ1(δ1(q0,w),a)=δ1(\delta_1(q_0,wa)=\delta_1(\delta_1(q_0,w),a)=\delta_1({q1,q2,...,qnq_1,q_2,...,q_n},a)=,a)={p1,p2,...,pmp_1,p_2,...,p_m}

    由归纳假设δ1(q0,w)=\delta_1(q_0,w)={q1,q2,..,qnq_1,q_2,..,q_n}⇔δ2([q0],w)=[q1,q2,...,qn]\Leftrightarrow\delta_2([q_0],w)=[q_1,q_2,...,q_n]

    根据δ2\delta_2 的定义，δ2([q1,q2,...,qn],a)=[p1,p2,...,pm]⇔δ2(\delta_2([q_1,q_2,...,q_n],a)=[p_1,p_2,...,p_m]\Leftrightarrow\delta_2({q1,q2,...,qnq_1,q_2,...,q_n},a)=,a)={p1,p2,...,pmp_1,p_2,...,p_m}

    所以，δ2([q0],wa)=δ2(δ2([q0],w),a)=δ2([q1,q2,...,qn],a)=[p1,p2,...,pm]\delta_2([q_0],wa)=\delta_2(\delta_2([q_0],w),a)=\delta_2([q_1,q_2,...,q_n],a)=[p_1,p_2,...,p_m]

    故，如果δ1(q0,wa)=\delta_1(q_0,wa)={p1,p2,...,pmp_1,p_2,...,p_m} 则必有δ2([q0],wa)=[p1,p2,...,pm]\delta_2([q_0],wa)=[p_1,p_2,...,p_m]

    由上述推导可知，反向的推导也成立，即结论对∣x∣=n+1\vert x\vert=n+1 也成立

    由归纳法原理，结论对∀x∈Σ∗\forall x\in\Sigma^* 成立

  • 证明L(M1)=L(M2)L(M_1)=L(M_2)

    设x∈L(M1),δ1(q0,x)=x\in L(M_1),\delta_1(q_0,x)={p1,p2,...,pmp_1,p_2,...,p_m}，从而δ1(q0,x)∩F1≠ϕ\delta_1(q_0,x)\cap F_1\neq\phi, 即 {p1,p2,...,pmp_1,p_2,...,p_m}∩F1≠ϕ\cap F_1\neq\phi，由F2F_2 的定义，[p1,p2,...,pm]∈F2[p_1,p_2,...,p_m]\in F_2，已知δ2([q0],x)=[p1,p2,..,pm]\delta_2([q_0],x)=[p_1,p_2,..,p_m]，所以x∈L(M2)x\in L(M_2)，因此L(M1)⊆L(M2)L(M_1)\subseteq L(M_2)。反过来推，可得L(M2)⊆L(M1)L(M_2)\subseteq L(M_1)。从而L(M1)=L(M2)L(M_1)=L(M_2) 得证。综上，定理成立

不可达状态：

  • 不存在从[q0][q_0] 对应的顶点出发，到达该状态对应的顶点的路。我们称此状态从开始状态是不可达的

构造给定 NFA 等价的 DFA 步骤：

  • 把开始状态[q0][q_0] 填入表的状态列中
  • 如果表中所列的状态列表有未处理的，则任选一个未处理的状态[q1,q2,...,qn][q_1,q_2,...,q_n]，对Σ\Sigma 中的每个字符 a，计算δ([q1,q2,...,qn],a)\delta([q_1,q_2,...,q_n],a)，并填入相应的表项中
  • 如果δ([q1,q2,...,qn],a)\delta([q_1,q_2,...,q_n],a) 在表的状态列未出现过，则将它填入表的状态列
  • 如此重复下去，直到表中的状态列中不存在未处理的状态

# 带空移动的有穷状态自动机

带空移动的不确定的有穷状态自动机：

M=(Q,Σ,δ,q0,F),Q,Σ,q0,FM=(Q,\Sigma,\delta,q_0,F),Q,\Sigma,q_0,F 的意义同 DFA。δ:Q×(Σ∪\delta:Q\times(\Sigma\cup{ϵ\epsilon})→2Q)\rightarrow 2^Q

  • 非空移动
    • ∀(q,a)∈Q×Σ\forall(q,a)\in Q\times\Sigma
    • δ(q,a)=\delta(q,a)={p1,p2,...,pmp_1,p_2,...,p_m}
    • 表示 M 在状态 q 读入字符 a，可以选择地将状态变成p1,p2,...,pnp_1,p_2,...,p_n，并将读头向右移动一个带方格而指向输入字符串的下一个字符
  • 空移动
    • ∀q∈Q\forall q\in Q
    • δ(q,ϵ)=\delta(q,\epsilon)={p1,p2,...,pmp_1,p_2,...,p_m}
    • 表示 M 在状态 q 不读入任何字符，可以选择地将状态变成p1,p2,...,pmp_1,p_2,...,p_m。读头不动
  • 在ϵ−NFA\epsilon-NFA 中，对任意a∈Σ,q∈Qa\in\Sigma,q\in Q，δ^(q,a)≠δ(q,a)\hat{\delta}(q,a)\neq\delta(q,a) 需要严格区分

定理：ϵ−NFA\epsilon-NFA 与NFANFA 等价

  • 证明：设有ϵ−NFAM1=(Q,Σ,δ1,q0,F)\epsilon-NFA\ M_1=(Q,\Sigma,\delta_1,q_0,F)

    • 构造与之等价的NFAM2NFA\ M_2

      取NFAM2=(Q,Σ,δ2,q0,F2)NFA\ M_2=(Q,\Sigma,\delta_2,q_0,F_2)

      F2={F∪{q0}ifF∩ϵ−CLOSED(q0)≠ϕFifF∩ϵ−CLOSED(q0)=ϕF_2=\begin{cases} F\cup{\{}q_0{\}}&if\ F\cap\epsilon-CLOSED(q_0)\neq\phi\\F&if\ F\cap\epsilon-CLOSED(q_0)=\phi \end{cases}

      δ2(q,a)=δ1^(q,a)\delta_2(q,a)=\hat{\delta_1}(q,a)

# FA 是正则语言的识别器

# FA 与右线性文法

  • DFA M=(Q,Σ,δ,q0,F)M=(Q,\Sigma,\delta,q_0,F)，处理句子a1a2...ana_1a_2...a_n 的特性

    • M 按照句子a1a2...ana_1a_2...a_n 中字符的出现顺序，从开始状态q0q_0 开始，依次处理字符a1,a2,...,ana_1,a_2,...,a_n，在这个处理过程中，每处理一个字符进入一个状态，最终停止在某个终止状态
    • 它每次处理且进处理一个字符：第 i 步处理输入字符aia_i
    • 对应与使用δ(q,a)=p\delta(q,a)=p 状态转移函数的处理，相当于是在状态 q 完成对 a 的处理，然后由 p 接下去实现对后续字符的处理
    • 当δ(q,a)=p∈F\delta(q,a)=p\in F，且 a 是输入字符串的最后一个字符时，M 完成对此输入串的处理

  • 定理：FA 接受的语言是正则语言

    • 构造

      基本思想是让 RG 的派生对应 DFA 的移动

      设DFAM=(Q,Σ,δ,q0,F)DFA\ M=(Q,\Sigma,\delta,q_0,F)

      取右线性文法G=(Q,Σ,P,q0)G=(Q,\Sigma,P,q_0)，P=P={q→ap∣δ(q,a)=pq\rightarrow ap\vert\delta(q,a)=p}∪\cup{q∣δ(q,a)=p∈Fq\vert\delta(q,a)=p\in F}

  • 定理：正则语言可以有 FA 接受

    • 构造

      基本思想：让 FA 模拟 RG 的派生

      设G=(V,T,P,S),ϵ∉L(G)G=(V,T,P,S),\epsilon\notin L(G)，取FAM=(V∪{Z},T,δ,S,{Z}),Z∉VFA\ M=(V\cup{\{}Z{\}},T,\delta,S,{\{}Z{\}}),Z\notin V

    • 对∀(A,a)∈V×T\forall(A,a)\in V\times T

      δ(A,a)={{B∣A→aB∈P}∪{Z}ifA→a∈P{B∣A→aB∈P}ifA→a∉P\delta(A,a)=\begin{cases} {\{}B\vert A\rightarrow aB\in P{\}}\cup{\{}Z{\}}&if\ A\rightarrow a\in P\\{\{}B\vert A\rightarrow aB\in P{\}}&if\ A\rightarrow a\notin P \end{cases}

      用B∈δ(A,a)B\in\delta(A,a) 与产生式A→aBA\rightarrow aB 对应

      用Z∈δ(A,a)Z\in\delta(A,a) 与产生式A→aA\rightarrow a 对应

  • 推论：FA 与正则文法等价

# FA 与左线性文法

DFA 的状态转移图作如下预处理：

  • 删除 DFA 的陷阱状态 (包括与之相关的弧)
  • 在图中加一个识别状态
  • "复制" 一条原来到达终止状态的弧，使它从原来的起点出发，到达新添加的识别状态

定理：左线性文法与 FA 等价