正規語言
===
###### tags: `大學必修-筆記`
Ch0
===
## 電腦的基本能力及限制
* Automata Theory (自動機理論)
* deals with definitions and properties of mathematical models of computation.
> 處理數學計算模型的定義和屬性
* Computability Theory (可計算性理論)
* classifies problems by those that are solvable and those that are not.
> 對可解決的問題和不可解決的問題進行分類。
* Complexity Theory (複雜度理論)
* classifies problems as easy ones and hard ones
> 將問題分類為簡單與困難。
## 三個 computational models
* Finite automaton -> 辨認 regular language
> 有限狀態機 -> 正則語言
* Pushdown automaton -> 辨認 context-free language
> 下推自動機 -> 上下文無關語言
* machine -> 辨認 recursively enumerable language
> 圖靈機 -> 遞歸可枚舉語言
## 數學名詞解釋
* $\sum$ -> alphabet
* $\sum*$ -> 字串集合
* ex：$\sum = \left \{ 0, 1 \right \}$ -> $\sum* = \left \{ Ɛ, 0, 1, 00, 11, ... \right \}$
* $\varepsilon$ -> 空字串
## 證明方法
* proof by construction
* proof by contradiction -> 反證法
* proof by induction -> 數學歸納法

Ch1-1 Finite Automata 有限自動機
===
## 狀態圖

* $q_{2}$ 雙圈圈接受狀態

## 有限自動機組成
* $Q$ -> 有限狀態形成的集合
* $Σ$ -> 字母(alphabet)的集合
* $\delta$ : $Q$ x $Σ$ -> 轉換函數 -> 目前狀態接受到輸入後變成的狀態
* $q_{0}$ -> 機器起始的狀態
* $F$ -> 接受狀態的集合(accept state)

## 定義
* 如果有一個字串放進機器裡，最後會停在accept state
* 代表這個機器接受這個字串，M recognize A
* $L\left ( M \right ) = A$
* regular language -> 如果有字母語言集，可以被一個有限自動機認識

## regular operations
* Union (聯集) -> $A\cup B$
* Concatenation (串接) -> $A \cdot B$
* $A*$ (Kleene星號) -> 從集合裡取出很多的字，任意做成集合

CH1-2
===

## Nondeterminism 不確定性
* Deterministic finite automata (DFA)
* 給了一個輸入後，下一個state只有一個
* Nondeterminism finite automata (NFA)
* 給了一個輸入後，下一個state會有多個選擇，甚至沒有定義
* 其它
* 每個 NFA 都可以寫成 DFA
* NFA 比 DFA 簡單又好理解

## 不確定性(NFA)有限自動機組成
* $Q$ -> 有限狀態形成的集合
* $Σ$ -> alphabet的集合
* $\delta$ : $Q$ x $Σ$ -> 轉換函數 -> 目前狀態接受到輸入後變成的狀態 ---> **唯一的差別**
* $q_{0}$ -> 機器起始的狀態
* $F$ -> 接受狀態的集合 accept state

## NFA to DFA
* 每個 NFA 可以轉成相同的 DFA
* NFA 有時比 DFA 還要簡單

## 用圖來理解 regular operations

### $A^*$
### $A\cup B$
### $A\cdot B$

CH1-3 Regular Expressions
===

* pattern 樣式 -> 一個string所形成的集合
* Regular Expressions 的 value 是一個pattern

## 定義
* 任何集合裡的符號也是一個Regular Expressions
* $\varepsilon$
* 0
* $A\cup B$
* $A \cdot B$
* $A^{*}$

## 優先順序
`star > concatenation > union`

$R^+ = RR^*$
$R^+\bigcup \varepsilon​ = R^*$

## GNFA vs NFA
* GNFA 可以允許邊上是一個regular exprassion
* 起始點(start state) 及 終點(accept state) 只能 出 or 進
* 只能有一個 accept state

## DFA to NFA
`DFA -> GNFA -> regular expression`

1. 在原本的 DFA 加上，另外兩個 state (起點、終點)
2. 漸漸把 state 數減少

CH1-4 Nonregular Languages
===
* Pumping lemma 泵引理
* 表達 regular languages 的必要條件
* 如果 A 是一個 regular language，有一個常數 p 使得任何長度大於 p 的字串可以分成三段 $s = xyz$，滿成以下條件

> * $xy^{i}z$ 也是 A 的regualr language
> * $y$ 不能為空字串
> * $xy$ 的長度不大於 p

* for each $i \geq 0, xy^iz\in A$
* $|xy| \leq p$
* $|y| > 0$

CH2-1 Context-Free Languages 上下文無關語言
===

## Translation Process of Programming Languages

* Lexical analysis 語彙分析

* 把原始碼內的變數名稱、運算子…，拆成一個一個entity

* Parsing 語法分析

* 了解程式裡文法的結構
* ex：if else 的結構

* Code generation

* 目的碼的產生器
* 來產生機器的語言
* 進行最佳化的動作

## Context-Free Grammar (CFG)
$$
(V, \sum, R, S)
$$
* $V$ -> 變數變合
* $\sum$ -> terminal 終端符號 -> 最後產生的符號集合
* $R$ -> 有限的規則所型成的集合
* $A \rightarrow x$, where
* $A \in V$ -> A 是變數
* $x \in (V \cup \sum)^*$ -> x 是 變數or終端符號
* $S$ -> start variable 起始變數

---
EX：
* $L_1 = {\left \{ 0^n1^n | n \geq 0\right \}}$

* $G_1 = {\left \{ V_1, \sum, R_1, S_1\right \}}$
* $V_1 = {\left \{ S_1\right \}}$
* $\sum = {\left \{ 0, 1\right \}}$
* $R_1 = {\left \{ S_1 \rightarrow 0S_11, S_1 \rightarrow \varepsilon \right \}}$

* $S_1 \Rightarrow 0S_11$ (Rule 1) $\Rightarrow 01$ (Rule 2)
---
* **u derives v** -> u 字串透過很多次替換後可以變成 v

* $u \Rightarrow ^* v$

* parse tree 剖析樹

## Designing CFGs

* 大CFG由許多簡單的CFG組成
* 如果 language is regular，那 DFA 可以轉成 CFG

* 把 DFA 裡的 state 換成 variable $R_1$
* 把 $\delta$ 的轉換規則，替換成 $R_j \rightarrow R_j 的替換規則$
* 加入 $R_i \rightarrow \varepsilon$
* 加入 $R_0$ 做為 start variable

## Chomsky Normal Form 喬姆斯基範式
* 定義
* 所有產生規則都符下面形式
* $A → BC$
* $A → α$
* $S → ε$
* 且 A, B 和 C 是非終結符
* α 是終結符（表示常量值的符號）
* B 和 C 都不可以是開始符號。

* 任何一個 CFGs 都可以轉成 Chomsky Normal Form

CH2-2 Pushdown Automata
===
## 定義

* 計算能力和 CFG 一樣
* 是另外一種計算模形
* 跟 finite automaton 比，多了一個無限大的 stack 來存資料
* 有 deterministic、nondeterminstic 之分，不過它們的計算能力不一樣
* 下面介紹 nondeterministic pushdown automata -> PDA (因為這個才與 CFG 相同)

## PDA (nondeterministic pushdown automata)

$$
(Q, \sum, \Gamma, \delta, q_{0}, F)\\
$$

* $Q$ -> 有限狀態形成的集合
* $\sum$ -> 字母(alphabet)的集合
* $\Gamma$ -> 堆疊字母集合
* $\delta$ : $Q$ x $Σ$ x $\Gamma_{\varepsilon} \rightarrow P(Q$ x $\Gamma_{\varepsilon})$ -> 轉換函數 -> 目前狀態接受到輸入後變成的狀態 ---> **唯一的差別**
* $q_{0}$ -> 機器起始的狀態
* $F$ -> 接受狀態的集合 accept state
---
* ex：$\left \{ 0^n1^n | n \geq 0 \right \}$


## 圖例子

* ex：$\left \{ 0^n1^n | n \geq 0 \right \}$

* a, b $\rightarrow$ c
* 讀取 a
* 從 stack pop b
* 把 c 丟進 stack
* $ 代表空的 stack

* 一個語言是 CFG if and only if 有 pushdown 機器認識它
* 也就是CFGs和PDAs等價

## Transition Function 的簡寫


## 把 CFGs 轉 PDAs

* 對於變數符號 A, 將換成的新字串反向推入堆疊 : $ε,A→w$ (如下圖<font color=red>紅色</font>部分)
* 對於終止符號 a, 和輸入配對 : $a,a→ε$ (如下圖<font color=#ffcc00>黃色</font>部分)


---
* 每個 regular language 都是 context free

CH2-3 Non-Context-free Languages
===

* 存在一個數字 p ，且有一個字串 s 可以分成五段，$s = uvxyz$

1. foreach $i \geq 0, uv^ixy^iz$
2. $|vy| > 0$
3. $|vxy| \leq P$

CH3-1 Turing Machines
===


* \# -> 把字串分為二，看看兩邊的字串是否為相等
* 圖靈機的特色
* 圖靈機可以在 tape 上讀及寫
* 讀寫的指標都可以從左讀到右
* tape 是無限的
* 接受或不接受的狀態是立即產生的

* 圖靈機定義 7 tuple

$$
(Q, \sum, \Gamma, \delta, q_0, q_{accept}, q_{reject})
$$

* $Q$ -> states 的集合
* $\sum$ -> 輸入的字母集合 不包含 blank symbol 空白號
* $\Gamma$ -> tape 上面可以記錄的符號 blank $\sum$ 都有
* $\delta$ -> 轉換函數 $Q \cdot \Gamma \rightarrow Q \cdot \Gamma \cdot \{ L, R \}$
在什麼狀態下，讀寫頭讀到什麼符號，->要轉換到什麼狀態，把讀寫頭寫入什麼符號，是往左邊還是右邊移動
* $q_0$ -> start state 起初狀態
* $q_{accept}$ -> Q 是 accept state
* $q_{reject}$ -> Q 是 reject state
---
* 一共有三種輸出狀態
* accept
* reject
* 在 tape 上無限往下

* 圖靈機的配製
* current state 目前狀態
* current tape contents 讀寫頭的符號是什麼 -> 狀態的後一個數字
* current head location 讀寫頭在哪裡


* 圖靈機可以把一個狀態從 $c_1$ 轉換成 $c_2$
* ex：
* $uaq_ibv$
* 經過轉換函數的轉換後 $\delta(q_i, b) = (q_j, c, L)$
* $uq_jacv$

* configuration
* start configuration
* accept configuration
* reject configuration
* halting configuration -> accept reject 的集合

* $L(M)$ -> 這些字串形成的集合會使圖靈機可辨認

* 決定器 decider
* 一個圖靈機對於任何一個 input ==一定有 accept 或是 reject 的 state== -> 不有會無限的情況
* Turing-decidale -> 圖靈機可以 decides 語言
* recursively language
* Turing-recognizable -> 圖靈機可以 recognizable 語言
* recursively enumerable language
* ==decidable 包含於 recongnizable==

---
ex：看看字串的 0 長度是否為 2 的指數
$$
M = \{ 0^{2^n} | n \geq 0\}\\
M = (Q, \sum, \Gamma, \delta, q_0, q_{accept}, q_{reject})
$$

* $Q = \{ q_1, q_2, q_3, q_4, q_5, q_{accept}, q_{reject}\}$
* $\sum = \{0\}$
* $\Gamma = \{ 0, x, \sqcup \}$
* 我們把 $\delta$ 看成一個 state 的圖
* $q_1$
* $q_{accept}$
* $q_{reject}$

---

CH3-2 變種圖靈機
===

### 多帶圖靈機 multitape TM

* 可以有 k (>1) 條紙帶
* 每條紙帶上都有一個讀寫頭

### 非決定性圖靈機 Nondeterministic Turing Machines

* 不加特殊說明，通常所說的圖靈機都是==決定型圖靈機==
* 特色

* 在計算的每一時刻，根據當前狀態和讀寫頭所讀的符號
* 機器存在多種狀態轉移方案
* 機器將任意地選擇其中一種方案繼續運作，直到最後停機為止

$$
Q \cdot \Gamma \rightarrow P ( Q \cdot \Gamma \cdot \{ L, R \})
$$

### 枚舉機 Enumerators

* 枚舉機只吐字串
* 會一直吐字串直到吐出我們想要的字串
* 當吐出想要字串的時候就是圖靈機的 accept state

CH3-3 演算法的定義
===

### Computable Functions

* Noncomputable function -> 丟給它一個值可以不能有 output 的函式
* computable function -> 丟給它一個值可以有一個 output 的函式
* Turing machine computable -> 就是 computable function 的定義

### Church–Turing thesis

* λ-function
* 如果有一個演算法成立
* 則一定有一個對應的 Turing machine 或 applicable λ-function 可以執行那個演算法
* Heabert 難問題，多項式是不是有整數根
* ==Recongnizable not Desidable==

CH4-1 Decidability
===


* 包含所有的語言
* 我們可以設計一個圖靈機來決定一個語言
---

### 決定性問題 (Decision problem)

* A：Accept，是否一個自動機會接受一個字串。
* E：Empty，是否一個自動機會接受任何一個字串 (沒有的話為空，接受)
* EQ：Equal，是否兩個自動機相等。

### 接受問題 (Accept Problem)

==$A_{DFA}$ 是一個決定性語言==

$A_{DFA} = \{(B, w)$ $|$ B是接受字串w的DFA $\}$

==$A_{CFG}$ 是一個決定性語言==

$A_{CFG} = \{(B, w)$ $|$ B是接受字串w的CFG $\}$

### 空問題 (Empty Problem)

==$E_{DFA}$ 是一個決定性語言==

$E_{DFA} = \{D |$ D 是一個DFA且 $L(D)=ϕ\}$

==$E_{CFG}$ 是一個決定性語言==

$E_{CFG} = \{D |$ D 是一個CFG且 $L(D)=ϕ\}$

### 相等問題 (Equal Problem)

==$EQ_{DFA}$ 是一個決定性語言==

$EQ_{DFA} = \{<A,B> |$ A和B是DFA，且 $L(A)=L(B)\}$

==$EQ_{CFG}$ 不是一個決定性語言==

CH5 Reducibility 可歸約性
===

* Reduction -> A 這個問題，如果你找到一個 B 的問題可以解決 A 的問題，那麼 A 問題也可以解決
* 如果 A 可以 reduces B -> $A\leq_mB$

### halting problem

* $HALT_{TM} = \{ <M, w> |$ M is a TM and M halt on input w $\}$
* M 是一個圖靈機
* w 是一個字串
* 給定一個字串給圖靈機，這個圖靈機會不會停止(accept，reject)

CH6 Time Complexity
===


* P -> 可用 decidable 圖靈機，以多項式時間來解決決定性問題
* NP -> 可用 renognizable 圖靈機，以多項式時間來看問題是否正確
* NPC ->

$$
\bar{A_{TM}}
$$

從 chruch turing thsis

CH7

big O

Time Complexity

What is the Class P

What is the Class NP

NP complete

satisfact

CH5

what is 歸約

halting problem

turing machine