---
title: 自動機 ch.1
---
# Automata Theory and Formal Languages
NTNU 自動機理論與正規語言
##### [Back to Note Overview](https://hackmd.io/@NTNUCSIE112/NTNUNote)
##### [Back to Automata Theory and Formal Languages](https://hackmd.io/@NTNUCSIE112/AT110-1)
{%hackmd @sophie8909/pink_theme %}
###### tags: `AutomataTheoryandFormalLanguages` `110-1` `選修` `CSIE` `NTNU`

## Ch.01 Introduction to the theory of computation

- Automaton 自動機
- possesses all the indispensable features of a digital computer
- accepts input :arrow_right: produces output
- make decisions in transforming the input into the output
- may have some temporary storage
- Formal language
- abstraction of the general characteristics of programming languages(PLs)
- the set of all sentence permitted by the rules of formation
#### Graph
- walk: a sequence of edges
- length: the total number of edge
- path: a walk no repeated edge
- simple path: a path no repeated vertex
### 1.1 Mathematical Preliminaries and Notation
<!-- slide 7 -->
#### Set
- $x \in S$
- $x \not\in S$
- Union: $S_1 \cup S_2$
- Intersection: $S_1 \cap S_2$
- Difference: $S_1 - S_2$
- Complementation: $\overline{S}$
- empty set/null set: $\emptyset$
- $S\cup\emptyset=S-\emptyset=S$
- $S\cap\emptyset=\emptyset$
- $\overline\emptyset=U$
- $\overline{\overline S}=S$
- DeMorgan's laws
- $\overline{S_1 \cup S_2} = \overline{S_1} \cap \overline{S_2}$
- $\overline{S_1 \cap S_2} = \overline{S_1} \cup \overline{S_2}$
- size of finite set: $|S|$
- Powerset: $2^S$
- $|2^S| = 2^{|S|}$
- Cartesian product: $S_1\times S_2 \times \cdots \times S_n = \{(x_1, x_2, \cdots, x_n): x_i in S_i \}$
#### Function
<!-- slide 16-->
- domain
- If f denotes a function, then the first set is called the domain of f
- range
- and the second set is range
- total function
- if the domain of f is all of $S_1$
- partial function
- otherwise f is said to be a partial function

#### Order of magnitude
{%hackmd /@SK11/Asymptotic_Notations %}
#### Relation
有些 function 可以被表達成 set of pairs

無法被 function 定義的 pair 稱為 relation
#### Function vs. Relation
- Relation is more general than Function
- Function: one element in the domain associated one element in the range
- Relation: may be several such elements in the range
### 1.2 Three Basic Concepts
+ $\Sigma$：一組有限、非空的符號，稱為字母表
+ 字串 Strings：字母表中有限的符號序列
e.g. $\Sigma=\{a, b\}$ $abab, aaabbba$ 都為 $\Sigma$ 上的字串
+ 串聯 Concatenation（wv）
e.g. $w=a_1a_2...a_n, v=b_1b_2...b_n$
串聯即為 $wv = a_1a_2...a_nb_1b_2...b_n$
+ 相反 Reverse（$w^R$）：$w^R=a_n...a_2a_1$
+ 長度 Length
+ |w|：字串中的符號數
+ |wv|=|w|+|v|
+ 空字串 Empty string（$\lambda$）
+ |$\lambda$|=0
+ $\lambda$w=w$\lambda$=w
+ 子字串 Substring：任何在w中連續的字串
+ w=vu v是前綴，u是後綴

#### 語言
+ 如果 w 是一個字串，則 $w^n$ 代表 w 字串重複 n 遍獲得的字串
+ Define: $w^0 = \lambda$
+ $\Sigma^*$：透過 $\Sigma$ 連結零個或多個符號而獲得的字串集
+ $\Sigma^+=\Sigma^*-\{\lambda\}$
$\Sigma$ 是有限的，但是 $\Sigma^*$ 和 $\Sigma^+$ 是無限的
+ 語言：$\Sigma^*$ 的子集
+ L 的句子（Sentence of L）：在語言 L 中的一個字串（a string in a language L）

#### 語言中的術語
+ $\overline{L}=\Sigma^*-L$
+ Complement of L
L 的補體
+ $L^R=\{w^R:w\in L\}$
+ Reverse of L
L 的相反
+ $L_1L_2=\{xy:x\in L_1, y\in L_2\}$
+ Concatenation of $L_1$ and $L_2$
$L_1$ 和 $L_2$ 的串聯
+ $L^n$
+ L concatenaed with itself n times
L 與自身連結 n 次
+ 特殊狀況：$L^0=\{\lambda\}, L^1=L$
+ $L^*=L^0\cup L^1\cup L^2\cup...$
+ $L^+=L^1\cup L^2\cup...$

#### 語法的定義
語法 G 寫作 $G=(V, T, S, P)$
+ V：a finite set of objects called **varibles** 變數的有限集合
+ T：a finite set of objects called **terminal symbols** 終端符號的有限集合
+ $S \in V$：a special symbol called the **start variable** 集合中一個符號，稱為起始變數
+ P：a finite set of **production** 產生式的有限集合
+ V 和 T 為非空集合（nonempty）且不相交（disjoint）

##### 產生式的規則
+ 形式：$x\rightarrow y$ 其中 $x\in(V\cup T)^+, y\in(V\cup T)^*$
+ $w\Rightarrow z$：w 導出 z，或是 z 是從 w 中導出來的
+ 如果 $w_1\Rightarrow w_2\Rightarrow...\Rightarrow w_n$ 我們寫成 $w_1 \Rightarrow w_n$（箭頭上多一個* LaTeX 打不出來）

#### L(G) 的定義
+ 設 G=(V, T, S, P) 為一個語法
+ $L(G)=\{w\in T^*:S\Rightarrow^*w\}$ 為一個 G 生成的集合
+ 如果 $w\in L(G)$ 則序列 $S\Rightarrow w_1\Rightarrow w_2\Rightarrow ...\Rightarrow w_n\Rightarrow w$ 稱為句子 w 的推導
+ 推導過程的字串 $S, w_1, w_2, ..., w_n$ 稱為句型 sentential form

#### Automata 自動機
一個數位電腦的抽象模型

##### 自動機的操作
+ 在離散的時間範圍內運行
+ 在任何給定的時間，控制單元處於某種內部狀態，輸入機構則正在掃描檔案上特定的符號
+ 轉換函數會根據當前的狀態、輸入符號跟臨時記憶體中的資訊給出下一個狀態
+ 組態：控制單元、輸入檔案跟臨時記憶體的特定狀態
+ 轉移：自動機從一個組態到下一個組態的轉換

##### 自動機模型
+ 有限狀態控制對所有模型都是通用的
+ 根據輸出的地方跟臨時記憶體的性質會有所不同

#### （非）確定性自動機
+ 確定性自動機：每個轉移都由當前組態唯一決定
+ 非確定性自動機：在每個點上，非確定性自動機有幾個可能的動作，我們只能預測一組可能的動作

#### 接受器和變換器
+ 接受器：一種僅能輸出是或否於的自動機
+ 變換器：一種能夠以符號串作為輸出的自動機

<!-- Ch.2 已開 -->