形式语言与自动机:大纲与摘要

2020-09-03 (Thu.)

这一系列(共 4 部分)为整理后的形式化语言与自动机的本科课程笔记,可作为知识提纲。


目录

I:概念,推理与文法

核心问题:哪些问题可以通过计算解决(可计算型理论)

自动机理论:研究抽象机器所能解决问题的理论(图灵机:核心理论模型;以及有限状态机、文法、下推自动机等)

谓词逻辑与集合关系

  • „n 元关系是定义在某域上的一组 n 元组的集合

  • „集合 A 和 B 的二元关系 R 是 A×B 的子集;二元关系可写作 xRy

  • „dom (R) 和 ran (R) 分别表示关系 R 的定义域和值域

image-20200902103702649
  • 对于 RS×SR \subseteq S\times S 几种特殊的关系:
    • 偏序关系:自反,反对称,传递 Eg. 自然数集合 N 和小于等于关系≤构成的偏序集
    • 等价关系:自反,对称,传递 -> 等价类:由等价关系确定的一组集合,每个集合中的任意元素都相互等价
      • „等价关系的秩:等价类的个数

字母表、图与语言

  • 字母表是语言中出现的原子符号,通常用 Σ 表示
  • 字符串是字母表中元素的序列,长度必须为有限的,长度、连接等操作在定义上都为递归
    • 长度:递归定义 w=0,w=ε;x+1,w=xa|w| = 0, w = \varepsilon; |x| + 1, w = xa
  • „字符串运算:„联结运算 abc.def、„重复运算 (abc)*
    • 和集合有关的运算:AB=ww=xy,xA,yBA \cdot B = {w | w = x \cdot y, x\in A, y \in B}
      • Σ\Sigma 为字母表,则 Σn\Sigma^n 为长度为 n 的字符串集合
    • 正闭包、克林闭包
  • „语言:一系列特殊字符串的集合:„L⊆Σ^∗
  • 图:系统描述方式
    • „标签集合 D,标签函数 L:S∪T→D
    • „带标签的图可以表示为一个 4 元组 (S,T,D,L)
    • 树是一种特殊的有向无环图
  • 迁移系统:TS=(s,Σ,,S0)TS = (s, \Sigma,\rightarrow,S_0)
  • 给定字符串是否属于某个具体语言 L? 任何问题都可以转换成语言问题 wL?w \in L?
    • (可判定问题与不可判定问题)

逻辑语言与演绎推理

  • 证明:演绎法、归纳法与反证法

  • 命题逻辑

    • „一种可以判定真或假的命题描述语言
    • 由原子命题和连接算子构成
  • 谓词逻辑:比命题逻辑描述能力更强的逻辑语言,增加了变量取值

    • 组成:Variable, Functions & (Predicate symbols, equality, logical connectives, quantifiers)
    • 公式 ϕ\phi 在一个给定的结构 M 和赋值 ϕ\phi 下成立,记为M,σϕM, \sigma \vDash \phiσMϕ\vDash^M_\sigma\phi
    • 在给定结构 M 下每个赋值成立,记为MϕM\vDash\phiM=ϕ\vDash^M = \phi
    • 任意赋值成立:ϕ\vDash\phi
  • 演绎推理

    • „从一个集合的前提条件推导出一个结论的过程
    • 运用 Modus penens,矛盾,传递
    • 一些证明规则:
    • image-20200902110734521
    • 证明过程:对于AC\frac{A}{C},若要证明 C 只需证明 A,A 与 C 是相继式(HGH\vdash G,H 前件,G 后件)
    • 一个证明的例子:
    • image-20200902113914551

文法

概念

  • 包含: V (ariables) T (erminal symbols) P (roductions /rules) S (tart symbols)

    • V: 非终止符号,满足 VT=V \cap T = \emptyset
    • S: 起始符号,满足 SVS \in V
  • 文法的推导:Let G=(V,T,P,S)$$,. 有αβP,γ,δ(VT) α→β∈P, γ,δ∈(V∪T)^∗, 则称 𝛾𝛼𝛿𝐺𝛾𝛽𝛿𝛾𝛼𝛿⇒_𝐺 𝛾𝛽𝛿

    • 上述过程 = 𝛾𝛼𝛿𝛾𝛼𝛿规约成𝛾𝛽𝛿𝛾𝛽𝛿
    • 最左 & 最右,依据替换次序的不同,一个语句可以有多种推导
  • 文法的语言: L(G)=wwT,SGwL(G) = {w | w\in T^*, S \Rightarrow^*_G w}

  • 符号上的描述: + 和 * 作为幂时表示长度为 1 以上 或 0 以上的表达式,如T,T+T^*, T^+

  • 定义:等价文法:如果L(G1)=L(G2)L(G_1) = L(G_2) ,则等价

文法分类的乔姆斯基体系

3RG2CFG1CSG0PSG3 RG \subset 2 CFG \subset 1 CSG\subset 0 PSG

0 型文法

由文法结构定义的文法,又称为递归可枚举文法、短语结构语言、递归可枚举集等

Phrase structure grammer, aka PSG

1 型文法

满足:αβP,βα\forall \alpha \rightarrow \beta \in P, |\beta| \ge |\alpha|

又称上下文有关文法 Context sensitive grammar aka CSG

2 型文法

满足:αβP,βα\forall \alpha \rightarrow \beta \in P, |\beta| \ge |\alpha|αV\alpha \in V

又称上下文无关文法 Context free grammar, aka CFG

例如:T = {a, b}, SASBε,Aaa,BbS \rightarrow ASB | \varepsilon, A \rightarrow aa, B \rightarrow b

3 型文法

满足:αβP\forall \alpha \rightarrow \beta \in P 具备形式:

AwA \rightarrow wAwBA \rightarrow wB,其中 A,BV,wT+A,B\in V, w\in T^+

又称正则文法 / 正规文法 Regular grammar, aka RG

定义上讲,空语句 ε\varepsilon 在 1 - 3 型文法中都是不允许的,但因为其不影响语言的有穷描述的存在,所以允许 ε\varepsilon 存在,但其除了用于产生空语句以外不可用于其他任何句子的推导之中。

II: 有穷自动机与正则语言

有穷自动机 Finite Automation

动机:语言的识别:

  • 为了证明 wLw \subset L,需推导 G,或规约 w,缺乏目的性和方向性
  • 设计一套系统,提高识别效率,简介抽象、直观描述

定义

五元组:M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F)

  • Q 非空集合;Σ\Sigma 输入字母表, δ\delta 状态转移函数, q0q_0 开始状态,FF 终止 / 接收状态

  • δ(q,a)=p\delta(q,a) = p 表示在 q 状态下读入 a 转移到 p。

FA 的表达方式:函数或转换表(更直观)

字符串集合:set(q)=xxΣ,δ(q0,x)=qset(q) = {x | x \in \Sigma^*, \delta(q_0, x) = q}

Instant Description 瞬时描述

表示自动机识别一个输入串的过程。形式:xqyxqy,x 为已处理的字符,y 为未处理的字符

有:xqayMxapyxqay \vdash_M xapy,,其中 m\vdash_m与文法中的转换 \Rightarrow 有类似的表达方式(+: 至少一次,*: 若干次,n: n 次 等)

  • αMnβ\alpha \vdash_M^n \beta 表示 M 经过 n 次移动。从状态 α\alpha 转换成了状态 β\beta

确定有穷状态自动机 Deterministic Finite Automaton, DFA

对于任意 qQ,aSigma,δ(q,a)均有确定值q \in Q, a \in Sigma, \delta(q,a) 均有确定值

关于 δ^\hat{\delta}δ\delta:前者为后者的扩充,有δ^:Q×ΣQ\hat{\delta}: Q \times \Sigma^* \rightarrow Q,用于识别语言

注意到后者定义域 Q×ΣQ\times \Sigma 为前者定义域 Q×ΣQ \times \Sigma ^* 的真子集,所以二者如果有相同的值,不用区别符号,故常用δ\delta 代替 δ^\hat{\delta}

非确定有穷状态自动机 Nondeterministic Finite Automaton, NFA

定义类似 DFA 的五元组:M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F)

其中 δ\delta 允许选择多个状态。即 (q,a)Q×Σ,δ(q,a)={p1,p2,,pm}\forall (q,a) \in Q \times \Sigma, \delta(q,a) = \{p_1, p_2, \dots, p_m\}

FA 的 ID 与描述方式对 DFA 同样有效

空迁移

定义五元组:M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F)

在 NFA 的基础上,进一步允许 deltadelta 满足:(q,a)Q×Σ,δ(q,a)=p0,p1,,pm,δ(q,ε)=p0,p1,,pm\forall(q,a) \in Q \times \Sigma, \delta(q,a) = {p_0, p_1, \dots,p_m}, \delta(q,\varepsilon) = {p_0, p_1, \dots,p_m}

即允许 M 在状态 q 下不输入任何字符而选择改变状态,做空移动,称为 εNFA\varepsilon-NFA

空迁移 NFA 同样和 NFA 具有等价性。

注意在 ε\varepsilon-NFA 中,δ\deltaδ^\hat{\delta} 不等价,需要根据上下文区分。

正则语言 / 表达式

正则表达式 Regular Expression - 使用适当的约定用更简洁的方式来表达文法 FA 所表达的语言

FA 是正则语言的识别器(有限自动机和正则表达式等价)

定义:ε\emptyset 和 \varepsilon 是正则表达式,表示语言 ε\emptyset 和 \varepsilon

aΣ\forall a \in \Sigma 是正则表达式,表示语言 {a};

若 r 和 s 是 RE,则 r+s,rsr + s, r\cdot s 是正则表达式,rr^* 是正则表达式。

  • 正则语言 L (RE):有L(r1+r2)=L(r2)L(r2)L(r_1 + r_2) = L (r_2) \cup L (r_2)

⭐️ 正则语言的证明:泵引理 Pumping Lemma

  • 泵引理:L 为一个正则语言,则存在一个常数 N,使得 zL,\forall z \in L, zN|z| \ge N,能把 z 分为三个部分 xyz 满足有:yε,xyN,k0,xykzLy \ne \varepsilon, |xy| \le N, \forall k \ge 0, xy^kz \in L

利用反证法可以证明 L 不为正则语言。(找到恰当的拆分,并得到一个反例即可)

泵引理只是一个 RG 的必要条件,不可用于证明一个而语言是 RG

Eg.image-20200902194829475

Myhill-Nerode Theorem 迈希尔尼罗德定理:L 是正则语言,当且仅当 RL 有有限的等价类。

是一个证明语言是正则语言的必要充分条件。

正则语言的封闭性

  • RL 对于并、乘积、闭包运算封闭
  • RL 对于补、交运算封闭

自动机的转换

通常的转换顺序: RE -> ε\varepsilon-NFA -> NFA -> DFA

NFA -> DFA 及等价性

如果能用 NFA 来表示的语言,同样可以使用 DFA 来表示:

image-20200902163650146

接下来移除不可到达的状态集合得到:

image-20200902163714895

FA -> RE 的转换

  • 使用状态消去 State Elimination:
  • image-20200902183523252
  • 状态消去的方法:
  • image-20200902183712933

RE -> FA

image-20200902183953737
  • Eg.image-20200902184009512

III: 上下文无关文法与下推自动机

上下文无关文法 CFG

Context Free Grammar CFG 需满足:αβP\forall \alpha \rightarrow \beta \in P,均有 αV\alpha \in V 成立(即左侧不可以含有终止字符,但右侧可以含多个 symbols,而不是正则语言中的右侧只允许一个)。

一些概念:

E T F P id
Expression Term Factor Primary Identifier
表达式 因子 初等量 标识符
  • 定义:生成树 / 派生树 parse tree:aka 分析树,语法树
  • 对于字符串的另一种表达方式
    • image-20200902195526615

上下文无关语言在并、乘积、闭包下是封闭的,在交、补运算下不封闭。 CFL 与 RL 的交是 CFL。

派生方式与二义性

  • 极左派生 Leftmost Derivations lm\Rightarrow_{lm},在 α\alpha 派生过程中每一步都对最左变量进行替换(类似地有极右派生 Rightmost derivations),对应的规约有极左 / 右规约。

    • 最右派生 aka 规范派生 Normal Derivation,规范派生产生的句型为规范句型 Normal Sentencial Form
  • 二义性 Ambiguous Grammar:至少具两棵不同的派生树

  • == 判定 CFG 是否为 Ambiguous 是一个不可解问题==。

  • 解决二义性的方法:增加优先级、增加标志等等

  • 固有二义性 Inherent Ambiguity (并非所有语言都具备非二义性文法)

    • 形如 L={0n1n2m3m}L = \{0^n1^n2^m3^m\} 的语言具备不同的派生树,具有固有的二义性,例如:
    • image-20200902201120134

CFG 的化简

  1. 消除无用符号:

    有用符号:X 有效,当存在转移 SαXβwS \Rightarrow^* \alpha X\beta \Rightarrow^* w

    有用符号应当是可生成且可达的,非可达、非可生成的符号都需要被消去

    • Generating: XwX⇒^∗ w for some wTw∈T^∗
    • Reachable: SαXβS⇒^∗ αXβ for some {α,β}(VT)\{α,β\}⊆(V∪T)^∗

    Eg.

    image-20200902225956895
  2. 消除空转移

    Nullable:A 是可空的当 AεA \Rightarrow^* \varepsilon

    计算 nullables:先令 n(G)={AAεP}n(G) = \{A | A \rightarrow \varepsilon \in P\},递归向上规约得到所有 n(G)n(G)

    接下来做替换:若 A nullable,则 ABADA \rightarrow BAD 被替换成 ABADBDA \rightarrow BAD | BD,最后消去所有 AεA \rightarrow \varepsilon

  3. 消除单位转移 Unit Production (形如 ABA \rightarrow B)

    先令 n(G)={(A,A)AV}n(G) = \{(A,A)|A\in V\},如果 (A,B)G(A,B)\in GBCPB\rightarrow C \in P 则将 (A, C) 添加至 G

    接下来遍历 n (G),每一对 (A, B) 如果:BαB\rightarrow \alpha 不是一个单位转移,则添加 AαA \rightarrow \alpha 添加至P1P_1

范式

乔姆斯基范式 Chomsky Normal Form CNF

如果 CFG G=(V,T,P,S)G = (V, T, P, S) 中的所有产生式都有形式:

ABCA \rightarrow BCAaA \rightarrow a,则为 CNF。

乔姆斯基范式中不允许存在 ε\varepsilon 产生式、单一产生式,也不希望含有无用符号。

  • CFL 转换为 CNF:处理所有推导结果长于 2 的,把 a 替换成新的 A,再增加 AaA\rightarrow -a
    • 把所有长于 3 的级联分解成两个变量的转移,图示:
    • image-20200902232010462

格雷巴赫范式 Greibach Normal Form GNF

如果 CFG G=(V,T,P,S)G = (V, T, P, S) 中的所有产生式都有形式 AaαA \rightarrow a\alpha,则为 GNF。

注意到右线性文法是一种特殊的 GNF。

CFL 的泵引理

类似正则语言的泵引理定义如下:

  • 对于 CFL,存在一个 N 若 z>n|z| \gt n 则改写 z=uvwxyz = uvwxy 满足:
    • vwxN;vx>0|vwx| \le N; |vx| > 0
    • 即有i0,uviwxiyL\forall i \ge 0, uv^iwx^iy \in L

例如,证明 L={0m1m2mm1}L = \{0^m1^m2^m | m \ge 1\} 不是 CFL:

image-20200902231726693

下推自动机 Push Down Automaton PDA

PDA 与 CFG - 二型文法等价

image-20200902210210350

定义:一个七元组 M=(Q,Σ,Γ,δ,q0,Z0,F)M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)

  • Q 状态集合;Σ\Sigma 输入字母表; Γ\Gamma 栈符号表;Z0Z_0 开始符号(栈底符号)q0q_0 开始状态;FF 终止状态; δ\delta 转移函数 ,形如:δ(q,a,Z)={(p1,γ1),(p2,γ2)...}\delta(q,a,Z) = \{(p_1, \gamma_1), (p_2, \gamma_2)...\} 为一次非空移动

    • 形如:δ(q,ε,Z)={(p1,γ1),(p2,γ2)...}\delta(q,\varepsilon,Z) = \{(p_1, \gamma_1), (p_2, \gamma_2)...\} 为一次空移动,此情况下无论输入内容是什么,都可以选择直接将状态变为 pnp_n
  • 一个例子:构造 Lwwr={wwRw{0,1}}L_{wwr} = \{ww^R | w\in \{0,1\}^*\},其中 R 为倒序:

    • PDA 在图形中表示如下,右侧表示栈 Z 在状态转移之前与之后的情况,栈顶位于左侧,栈底位于右侧:Z0Z_0 表示空栈
    • image-20200902210340064
  • 确定下推自动机 DPDA:δ(q,a,X)\delta(q,a,X) 在 a 是 ε\varepsilon 时总是空,且 δ(q,a,X)\delta(q,a,X) 非空则 δ(q,ε,X)\delta(q,\varepsilon,X) 非空。

    • Regular language \subset L(DPDA) \subset Context-Free language

PDA 即时描述 Instantaneous Description

  • 即时描述:(q,w,γ)(Q,Σ,Γ\*)\forall (q,w,\gamma)\in (Q, \Sigma^*, \Gamma^\*) 成为 M 的一个即时描述
  • 一个非空移动的表示: (q,aw,Zβ)M(p,w,γβ)(q, aw, Z\beta) \vdash _M (p, w,\gamma\beta),其中 aw 为即将读入的字符串,M 之前位于状态 q,栈顶为 Z,进入状态 p 后 Z 被 γ\gamma 替换。
  • 同样有 (M),(M)+ˆ,(M)n(\vdash_M)^*, (\vdash_M)\^+,(\vdash_M)^n 的表达方式以表示特定次数的移动。

可使用 ID 描述上述 LwwrL_{wwr} 如下:()

image-20200902211702996

PDA 接受的语言

  • 以终止状态接受:L(P)=w(q0,w,Z0)(q,ϵ,α)qFL(P)={w ┤| (q_0,w,Z_0 ) ⊢^∗ (q,ϵ,α)∧q∈F}
  • 以空栈接受:N(P)=w(q0,w,Z0)(q,ϵ,ϵ)N(P)={w ┤| (q_0,w,Z_0 ) ⊢^∗ (q,ϵ,ϵ)}

定理:两种接收方式是等价的。

CFG 与 PDA 的等价性

L 是 CFG 当且仅当能被一个 PDA 接受。(两种接收方式)

image-20200902224334935

CFG -> PDA

模拟一个 CFG 的极左派生 lm\Rightarrow^*_{lm}

  1. xAαlmxβαxA\alpha\Rightarrow_{lm}x\beta\alpha 对应一个 PDA 的操作,在栈 Z 中压入非终止字符,在栈上有终止字符时便弹出

  2. 此时可能会有非法的指令(在栈中一字符(包括 ε\varepsilon 只能由一个字符替换)),可以进行指令分解

    image-20200902224102033

    分解 ε,SaTb\varepsilon, S \rightarrow aTb 之后自动机如图所示:

    image-20200902224140954

    以此类推进行指令分解。

PDA -> CFG

暂且省略。

IV: 图灵机与可计算型

图灵机 Turing Machine

TM:人们所接受的算法的形式化描述。与 TM 具有同样计算能力的还有 λ\lambda 演算、递归函数、波斯特系统等。

定义:七元组 M=(Q,Σ,Γ,δ,q0,B,F)M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)

  • Q 状态的有穷集合;Σ\Sigma 输入字母表;Γ\Gamma 带符号表(运行过程中的符号);q0q_0 M 的开始状态;F 终止状态;B 空白符(基本图灵机的概念);δ\delta 转换函数,形如 δ(q,X)=(p,Y,RL)\delta(q, X) = (p, Y, R或L),表示在状态 q 读入符号 X,将状态更新为 p,并在 X 所在的方格中印刷符号 Y,接着向右 / 左移动一格。

如:

image-20200902233904457

初始状态下,输入字符串依次放在条带上,指针注释第一个元素,状态为 q0q_0

TM 定义的语言为递归可枚举语言,即 0 型文法。

TM 即时描述 Instantaneous Description

TM 的即时描述为字符串 X1X2Xi1qXiXI+1XnX_1X_2…X_{i-1}qX_iX_{I+1}…X_n

  • q:目前状态;磁带指向第 i 个符号
  • 其余符号表示最左侧的空白到最右侧的空白之间的所有字符
  • 同样有 (M),(M)+,(M)n(\vdash_M)^*, (\vdash_M)^+,(\vdash_M)^n 的表达方式以表示特定次数的移动

TM 作为非负整函数的计算模型

对非负整数编码后图灵机具有计算能力。

例如计算 n+m 的图灵机可以将字符串编码为 {0m10n}\{0^m10^n\},利用图灵机扫描,修改 1 的位置即可。

构造方式

Multiple Tracks 多轨

image-20200903000142831

计算能力和单轨相同,可以将存储的值复合为 {X,Y,Z} 即变成单带。

Subroutine 子图

image-20200903000417382

TM 拓展及变型

Multi-tape Turing machine 多带处理器

image-20200903000545081

本质上也和基本图灵机等价。

Non-deterministic TM 非确定图灵机

对于每一个转移函数 δ\delta,非确定图灵机具有一系列转移结果 {(q1,Y1,D1),(qk,Yk,Dk)}\{(q_1,Y_1,D_1 ),…(q_k,Y_k,D_k)\}

只要有一条路径到达最终状态即可接收。

可计算性 Computability

(仅作了解)

可计算型的问题:对于问题给出是与否的判定。

  • 如果一个问题的语言是递归的,则可判定 Decidable
  • 如果一个问题的语言不可递归,则不可判定 Undecidable

Example:

image-20200903002305978

上述程序查找 xn+yn=znx^n+y^n=z^n 的 x, y, z 整数元组,查找到则输出 hello, world。该问题 Undecidable。

img

  • Non-RE language 非递归可枚举语言(一个不能递归枚举字符串中的所有语言)
  • 递归可枚举语言:可以用类似穷举的算法在有限时间内判定一个元素属于该集合
  • 停机问题 Halting Problem: 不存在一个算法,能够判断任意图灵机[公式]在任意字符串[公式]上否停机。
  • 图灵机编码:
    • 用二进制字符串枚举所有可能的字符串(Eg 5337 - 010011011001)
    • image-20200903143418447
    • 接下来对δ\delta 编码如下:
      • 对任意 δ(qi,Xj)=(qk,Xl,Dm)\delta(q_i, X_j) = (q_k,X_l,D_m) 构造字符串 transition = 0i10j10k10l10m0^i10^j10^k10^l10^m,整个图灵机的构造则为 C111C211Cn111CnC_111C_211…C_{n-1}11C_n,其中 CiC_i 为 transition。

NP 与 P

  • P 问题:可以在多项式时间内求解的判定问题 Polynomial Problem
  • NP 问题:Non-Polynomial 不可以在多项式时间内解决的问题
  • NPC 问题:Non-Polynomial Complete NP 中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间的算法,那么所有 NP 问题都是多项式时间可解的。这些问题被称为 NP - 完全问题 (NPC 问题)。

The End

© 2019 - 2024Juntong Chen ||
Dark Mode
|| RSS