#import "@local/note_template:0.0.1": *
#import "@preview/finite:0.3.0": automaton
#import "@preview/cetz:0.2.2"

#set heading(numbering: "1.1")

#show heading: body => [
  #text(font:("Times New Roman","Weibei SC"))[#body]
]

#frontmatter(title: "Final Note", date: "2021-6-12", authors: ("Nemo",))
#set text(font:("Times New Roman","Weibei SC"))
#outline(indent: true)
#set text(font: ("Times New Roman","SimSun"))

#pagebreak()

#let make_cols(cols,body) = context{
  let size = measure(body)
  box(height: size.height/cols)[
    #columns(cols)[
      #body
    ]
  ]
}

= 有穷自动机

Basic defs:

#make_cols(2)[
- 字母表
- 字符串/字
- 空串
- 串的长度
- 串的连接
- 串的逆序
- 集合的连接
- 集合的幂
- 正闭包
- 克林闭包
- 串的前缀, 后缀, 真前缀, 真后缀
- 语言: $L, forall L in Sigma^*$
]

== DFA

#let map = sym.arrow.r.bar

$"DFA" A = (Q, Sigma, delta, q_0, F)$

状态转移函数:
$delta: Q times Sigma map Q $

拓展状态转移函数:
$hat(delta): Q times Sigma^* map Q$

=== Exercies

+ Design a DFA that accepts all strings w over {0, 1} such that w is the binary representation of a number that is a multiple of 3.

  基本的, 分成三个类别, $q_0, q_1, q_2$, 余数分别为0, 1, 2; 考虑一下初始状态, 如果开始时0, 则为 $q_0$, 开始为1, 则为 $q_1$, 故还需要添加一个开始状态, 记作 _dummy_. 有以下自动机:
  #align(center)[
  #automaton((
    dummy: (q0: 0,q1: 1),
    q0: (q0: 0,q1: 1),
    q1: (q0: 1,q2: 0),
    q2: (q2: 1,q1: 0)
  ),
  layout:(
    dummy: (0,0),
    q0: (0,-3),
    q1: (3,-3),
    q2: (6,-3)
  ),
  initial: "dummy",
  final: "q0"
  )]

  思路为, 二进制数读入一个0, 已知数乘二, 读入一个1, 已知数乘二加一.

== NFA

$"NFA" A = (Q, Sigma, delta, q_0, F)$

$delta: Q times Sigma map 2^Q$

状态可以一次转移并行的跳转至多个状态, 最终接受时, 只要有一个状态处于接受集中即可.

#note()[如果出现一个状态没有任何转移, 则认为其转移到一个空集.]

=== Exercies

+ $L={w bar w in {0,1}^*}$ 设计 NFA 使其接受最后三个符号至少有一个 1 的串.

  + 有以下自动机:
  
    #align(center)[
      #automaton((
        q0: (q0: (0,1), q1: 1),
        q1: (q2: (0,1)),
        q2: (q3: (0,1)),
        q3: ()
      ),
      initial: "q0",
      final: ("q1","q2","q3")
      )
    ]

    思路为: 开始时如果没有 1 就停留在 $q_0$, 有 1 就向下传, 一共传递 3 次, 如果没有结束就转移至 $nothing$, 结束就停在 $q_1, q_2, q_3$ 中任一状态, 以实现 "最后三个字符" 的要求.
    
    同时要注意, $q_0, 0 -> q_0$ 的转移是必须的, 如果出现一次 1 但是后续若超过 3 个字符, NFA 将转移至 $nothing$, 无法接受, 故此转移维护了起始状态.

    #note()[
      可以利用 NFA 转移至 $nothing$ 的方式来实现计数, 但是这样会使得状态数目增加, 且每个状态不具有充分的实际意义, 更像占位符.
    ]

  + 还有另外一种方式的实现:

    #align(center)[
      #automaton((
        q0: (q0: (0,1), q1: 1, q2: 1, q3: 1),
        q1: (q2: (0,1)),
        q2: (q3: (0,1)),
        q3: ()
      ),
      initial: "q0",
      final: ("q3"),
      layout: (
        q0: (0,0),
        q1: (0,-3),
        q2: (3,-3),
        q3: (6,-3)
      ),
      style: (
        q0-q1: (curve: 0)
      ))
    ]

    和上面差不多同理, 也是通过三个状态, 转移至 $nothing$ 来计数.

+ $L = {w bar w "starts with 01"} union {w bar w "ends with 01"}$ 设计 NFA 接受 $L$

  有以下自动机:

  #align(center)[
    #automaton((
      q0: (q1: 0, q3: (0,1)),
      q1: (q2: 1),
      q2: (q2: (0,1)),
      q3: (q3: (0,1), q4: 0),
      q4: (q5: 1),
      q5: ()
    ),
    initial: "q0",
    final: ("q2","q5"),
    layout: (
      q0: (0,0),
      q1: (3,2),
      q2: (6,2),
      q3: (3,-2),
      q4: (6,-2),
      q5: (9,-2)
    ),
    style: (
      transition: (curve: 0)
    )
    )
  ]

=== NFA 与 DFA 的等价性

对于 NFA 并行的跳转状态, 可以理解为一次跳转至一个确定的状态集, 因此可以将该状态集作为 DFA 的一个状态, 从而实现 NFA 与 DFA 的等价性.

证明详见 _课程讲义 2.3.4_.

== $epsilon dash.en$NFA

$epsilon dash.en "NFA" = (Q, Sigma, delta, q_0, F)$

$delta: Q times Sigma union {epsilon} map 2^Q$
允许读入空串 (不读入字符) 进行转移.

=== $epsilon dash.en "closure"$

#let eclose="ECLOSE"

$epsilon dash.en "closure" (q) = {q} union {p bar p "is reachable from q by epsilon transitions"}$

记为 ECLOSE(q)

对于状态集合的 ECLOSE(S), 则结果为所有状态的 ECLOSE(q) 的并集.

=== 状态转移函数的定义

+ $hat(delta)(q, epsilon) = eclose(q)$

+ 若 $w=x a$
  
  $hat(delta)(q, w) = eclose(union.big_(p in hat(delta)(q,x)) delta(p,a))$

=== Exercies

+ 求 $hat(delta)(q_0, 10)$

  先做 $q_0$ 空转移
  
  再读入 1 得到状态转移, 再进行 ECLOSE
  
  再读入 0 得到状态转移, 再进行 ECLOSE


=== 消除空转移

设 $epsilon dash "NFA" E = (Q_E, Sigma, delta_E, q_E, F_E) space "DFA" D = (Q_D, Sigma, delta_D, q_D, F_D)$ 其中:

$
Q_D &= 2^(Q_E)\
q_D &= eclose(q_E)\
F_D &= {S bar S in Q_E, S sect F_E eq.not nothing}\
delta_D (S, a) &= eclose(union.big_(p in S) delta_E (p, a))
$

=== $epsilon dash.en "NFA"$ 与 DFA 的等价性

先证明 $epsilon dash.en "NFA"$ 与 NFA 的等价性, 然后再证明 NFA 与 DFA 的等价性. 好像能一步到位, 但是我还没看懂(

ToDo

证明与 NFA 的等价性需要构造 NFA $delta_N(q, a) = hat(delta)_E(q, a)$ 以及

$F_N = cases(F_E union {q_0} "if" eclose(q_0) sect F_E eq.not nothing, F_E "otherwise")$

= 正则表达式与正则语言

自动机通过识别来定义语言, 正则表达式通过规则产生语言 (或表示语言); 正则表达式所表示的语 言与正则语言等价.

== 正则表达式的定义

递归定义:

+ $nothing$ 是正则表达式, 表示空语言, 没有任何串能匹配.
+ $epsilon$ 是正则表达式, 表示空串.
+ 对于 $a in Sigma$, $a$ 是正则表达式, 表示只有一个字符的串.
+ 若 $r_1, r_2$ 是正则表达式, 则 $r_1 r_2, r_1 + r_2, r_1^*, (r_1)$是正则表达式, 分别表示串的连接, 串的并, 串的闭包, 以及串运算优先级.

/ e.g. : $("aa")^*("bb")^*b -> {w bar w = a^(2n)b^(2m+1)}$

优先级: $r^* gt r s gt r + s$

== 有穷自动机与正则表达式

=== DFA #sym.arrow Regex

==== 递归法

将 DFA 所有状态编号为 ${1, 2, ..., n}$ 其中编号为 1 的为开始节点, 则该 DFA 对应的正则表达式为:
$union.big_(j in F) R^(k)_(1j)$, 其中 $R^(k)_(i j) = {x bar hat(delta)(q_i, x) = q_j, forall w, x = w alpha, hat(delta)(q_i, w) = q_m, m lt k}$ 即, 从 $i$ 至 $j$ 且不经过 $k$ 及以上的所有串.

递推规则为:

$
R_(i j)^(k) = R_(i j)^(k-1) union R_(i k)^(k-1) (R_(k k)^(k-1))^* R_(k j)^(k-1)\
R_(i j)^(0) = cases({a bar delta(q_i, a) = q_j} &"if" i eq.not j, {a bar delta(q_i, a) = q_j} union {epsilon} &"otherwise")
$

理解: 递推关系为, 从 $i$ 至 $j$ 的串, 通过不超过 $k-1$, 以及从 $i$ 至 $k$, $k$ 至 $k$, $k$ 至 $j$ 的串的连接, 以及 $k$ 至 $k$ 的串的闭包.

采用递推关系计算时: 首先应当明确结果是哪几个串的并集, 同时建议列表, 将 $k lt n$ 的部分算完, 最后一列只需要算需要的, 以避免错误.

==== 状态消除法

通过消除中间状态将 DFA 变换至只有起始节点和接受节点.

#make_cols(2)[
  #automaton((
    q0: (q2:"p"),
    q1: (),
    q2: (q1:"q", q4:"t", q2: "c"),
    q3: (q2:"r"),
    q4: ()
  ),
  initial: "",
  final: "",
  layout:(
    q0: (0,0),
    q1: (4,0),
    q2: (2,-2),
    q3: (0,-4),
    q4: (4,-4)
  ),
  style:(
    transition: (curve: 0)
  )
  )

    #automaton((
    q0: (q1:"pc*q", q4:"pc*t"),
    q1: (),
    q3: (q1:"rc*q", q4:"rc*t"),
    q4: ()
  ),
  initial: "",
  final: "",
  layout:(
    q0: (0,0),
    q1: (4,0),
    q2: (2,-2),
    q3: (0,-4),
    q4: (4,-4)
  ),
  style:(
    transition: (curve: 0, label: (pos: 0.1))
  )
  )

]

== 代数定律

+ 交换律
+ 结合律
+ 分配律
+ 幂等律
+ 有关闭包的定律
+ Others 

  $
  (L+M)^* &=L^*M^*\
  L^*L^* &= L^*\
  (epsilon + L)^* &= L^*
  $

= 正则语言的性质

== 证明非正则 泵引理

若语言 $L$ 是正则的, 则存在一个正整数 (常数) $N$, 对于任何 $w in L$,
只要 $abs(w) gt.eq N$, 则可以把 $w$ 分为三部分 $w = x y z$ 使得
  + $y eq.not epsilon$
  + $abs(x y) lt.eq N$
  + $x y^k z in L, forall k gt 0$

== 正则语言的封闭性

正则语言在交, 并, 补, 差, 连接和克林闭包运算下保持封闭.

并, 连接, 克林闭包由 regex 定义得出. 补可由定义自动机得出 ($F' = Q - F$).

其他集合运算可由并补得证.

正则语言在反转运算下封闭, 根据 regex 定义, 归纳证明.

正则语言在同态, 逆同态映射下封闭, 同样递归证明.

== 正则语言的判定性质

=== 空性, 有穷性, 无穷性

具有 $n$ 个状态的自动机 $M$ 接受串的集合为 $S$, 有:
+ $S$ 非空, 当且仅当 $M$ 接受某个长度小于 $n$ 的串.
+ $S$ 无穷, 当且仅当 $M$ 接受某个长度为 $m$ 的串, $n lt.eq m lt 2n$.

=== 等价性

存在一个算法, 判定两个有穷自动机是否等价 (是否接受同一语言).

== 自动机最小化

DFA中,称两个状态 $p$ 和 $q$ 是等价的,如果对任意串 $w in Sigma$ 满足:
$ hat(delta)(p, w) arrow.l.r.double hat(delta)(q, w) $

同时在或者同时不在接受集. 反之称为可区分.

=== 填表算法

慢慢找喽.

重复以下过程，直到表中内容不再改变：若存在一个未标记状态 ${p, q}$, 且对于某个 $a in Sigma, {delta(p, a), delta(q, a)}$ 已做标记，则在 ${p, q}$ 对应格子内做标记

== 上下文无关文法/语言

=== CFG 定义

上下文无关文法 (CFG) 由四元组 $G = (V, Sigma, P, S)$ 定义, 其中:
+ $V$ 是变元, 非终结符集合
+ $Sigma$ 是终结符集合
+ $P$ 是产生式集合
+ $S$ 是开始符号

=== 派生

分析文法和串的关系, 可以由产生式的头向产生式的体分析, 称为派生或推导 (derivation), 也可以由产生式的体向头分析, 称为递归推理 (recursive inference) 或归约 (reduction).

CFG $G = (V, T, P, S)$, 设 $alpha, beta, gamma in (V union T)^* 且 A in V$ , 如果 $A arrow.r gamma$ 是 $G$ 的产生式, 那么称在文法 $G$ 中由 $alpha A beta$ 可派生出 $alpha gamma beta$, 记为 $alpha A beta arrow.r.double_G alpha gamma beta$

最左派生, 最右派生: 字面意思, 每次只能派生最左或最右的变元.

=== 文法产生的语言

$L(G) = {w bar w in T^* ,S arrow.r.double_G^* w}$

=== 句型

能由初始符号派生出来的串, 称为句型.

== 语法分析树

语法分析树是一个树, 其中叶子节点是终结符, 内部节点是非终结符, 根节点是开始符号.

如果内节点的标记是 A, 其子节点从左至右分别为 $t_1, t_2, ..., t_n$, 则 $A -> t_1 t_2 ... t_n$ 是一个产生式.

语法分析树的全部叶节点从左到右连接起来, 称为该树的产物

语法树和派生等价

== 歧义

如果 CFG $G$ 使某些串有两棵不同的语法分析树, 则称 $G$ 是歧义 (ambiguity) 的, 也称二义性的.

产生同样的语言可以有多种文法, 如果上下文无关的语言 $L$ 的所有文法都是歧义的, 那么称 $L$ 是 固有歧义 (Inherent Ambiguity) 的. 这样的语言是确实存在的.

“判定任何给定 CFG "G" 是否是歧义的”是一个不可判定问题.

== 文法化简

文法化简的主要内容包括:
+ 消除无用符号: 在派生过程中没有用到的符号
+ 消除空产生式: $epsilon$
+ 消除单元产生式: $A->B$

=== 消除无用符号

符号 $X in (V union U)$, 如果由初始符号 $S arrow.r.double^* alpha X beta$, 称 $X$ 是可达的 (reachable); 如果有 $alpha X beta arrow.r.double^* w (w in T^*)$, 称 $X$ 是产生的 (generating). 如果 $X$ 同时是产生的和可达的, 即 $S arrow.r.double^* alpha X beta arrow.r.double^* w (w in T^*)$, 称 $X$ 是有用的, 否则称为无用符号. 从文法中消除无用符号, 同时不改变文法产生的语言.

每个非空的 CFL 都能被一个不带无用符号的 CFG 产生.

注意, 此处判断一个符号是否可达/产生不仅需要考虑符号本身还要考虑符号推到出的符号.

#make_cols(3)[
文法定义

$S -> A B bar b\
A -> a$

消除非产生

$S -> b\
A -> a$

消除非可达

$S -> b$
]

=== 消除空产生式

先确定全部可空的变元:
+ 如果A→ε,则A是可空的;
+ 如果 $B → alpha$ 且 $alpha$ 中的每个符号都是可空的, 则 $B$ 是可空的

再替换全部带有可空符号的产生式, 如果 $A → X_1 X_2 ... X_n$ 是产生式, 那么用所有的 $A →
Y_1 Y_2 ... Y_n$ 产生式代替, 其中:
+ 若 $X_i$ 不是可空的,则 $Y_i = X_i$ 
+ 若 $X_i$ 是可空的,则 $Y_i$ 是 $X_i$ 或 $epsilon$ 
+ 但 $Y_i$ 不能全部为 $epsilon$.

=== 消除单元产生式

先确定所有的单元对$(A,B) "满足" A arrow.r.double^* B$, 若存在 $B->alpha$ 为非单元产生式, 则将 $A->alpha$ 加入产生式集合, 最后删除所有单元产生式.

文法简化步骤的顺序是重要的, 一个可靠的顺序是:
+ 消除 ε 产生式;
+ 消除单元产生式;
+ 消除非产生的无用符号; 
+ 消除非可达的无用符号.

== 乔姆斯基范式和格雷巴赫范式

文法格式的限制通过两个范式定理给出: 乔姆斯基范式 (Chomsky Normal Form, CNF) 定理和格雷巴赫范式 (Greibach Normal Form, GNF) 定理.

=== 乔姆斯基范式

每个不带 $epsilon$ 的 CFL 都可以由这样的 CFG $G$ 产生, $G$ 中所有产生式 的形式或为 $A -> B C$, 或为 $A -> a$, 这里的 $A, B$ 和 $C$ 是变元, $a$ 是终结符.

利用 CNF 派生长度为 n 的串, 刚好需要 2n - 1 步, 因此可以设计算法判断串是否在 CFL 中.
此外利用 CNF 可以实现多项式时间的解析算法 (CYK 算法).

=== 格雷巴赫范式

每个不带 $epsilon$ 的 CFL 都可以由这样的 CFG $G$ 产生, $G$ 中的每个产生 式的形式为 $A -> a alpha$, 这里 $A$ 是变元, $a$ 是终结符, $alpha$ 是零个或多个变元的串.

因为格雷巴赫范式的每个产生式都会引入一个终结符, 所以长度为 n 的串的派生恰好是 n 步.

转换方法ToDo

暂时没搞清楚这几个东西的设计意图.

== PDA

下推自动机 (Pushdown Automata, PDA) $P$ 的形式定义, 为七元组 $P = (Q, Sigma, Gamma, delta, q_0 , Z_0 , F )$:
+ $Q$ 是状态集合
+ $Sigma$ 是输入字母表
+ $Gamma$ 是栈字母表
+ $delta$ 是状态转移函数
+ $q_0$ 是初始状态
+ $Z_0$ 是初始栈符号
+ $F$ 是接受状态集合

=== PDA 的状态转移

$delta(q,a,Z) = {(p_1, beta_1), ..., (p_n, beta_n)}$

输入符号是 $a$, 栈顶符号 $Z$ 的情况下, 处于状态 $q$ 的 PDA 能够进入状态 $p_i$, 且用符号串 $beta_i$ 替换栈顶的符号 $Z$, 这里的 $i$ 是任意的, 然后输入头前进一个符号.

图形表示: 

#align(center)[
  #automaton((
    q0: (q1: "a,Z/beta"),
    q1: ()
  ),
  initial: "",
  final: "",
  layout: (
    q0: (0,0),
    q1: (4,0)
  ),
  style: (
    transition: (curve: 0)
  ))
]

=== ID, ID 转移符号

ID 瞬时描述: $(q, w, gamma) in Q times Sigma^* times Gamma^*$ 分别表示: 状态, 剩余输入串, 栈符号串.

ID 转移符号: $tack.r_P space tack.r_P^*$ 用于表示 ID 的转移 $"ID"_1 tack.r_P "ID"_2$

=== PDA 接受的语言

终态接受和空栈接受, 两者可以相互转换.