绪论

FSM 有限状态机
CFL 上下文无关语言
Turing machine 图灵机
Undecidable 无法用机械解决的问题

Finite State Machine 有限状态机

有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机（英语：finite-state automaton，缩写：FSA），简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。

https://zh.wikipedia.org/wiki/有限状态机

Some noun meanings

Symbol a,b,c,0,1,2,3…

Alphabet symbols的集合 collection of symbol $\Sigma=\{a,b,c\}$

String Sequence of Symbols $a,b,c,aa,bb,cc,abc...$

Language Set of Strings
Eg: $\Sigma = {0,1}$
L1 = set of all strings of length 2
L1 = {00,11,01,10}

Powers of $\Sigma$

$\Sigma = \{0,1\}$

$\Sigma^0=$ set of all strings of length 0
$\Sigma^0=\{\epsilon\}$

$\Sigma^1=$ set of all strings of length 1
$\Sigma^1=\{0,1\}$

$\Sigma^2=$ all strings of length 2
$\Sigma^2=\{00,11,01,10\}$

$\Sigma^3=$ all strings of length 3
$\Sigma^3=\{000,001,010,011,100,101,110,111\}$

$\Sigma^n=$ all strings of length n
$\Sigma^n=\{....\}$
$\Sigma^*=\Sigma^0\cup\Sigma^1\cup\Sigma^2\cup...\Sigma^n$
…

Cardinality 基数

number of elements in a set

eg:
$\Sigma = \{0,1\}$
Cadinality of $\Sigma^1$ is 2
Cadinality of $\Sigma^2$ is 4
Cadinality of $\Sigma^3$ is 8
Cadinality of $\Sigma^n$ is $2^n$

DFA

图中写错了A是automata是自动机的意思

DFA - Deterministic Finite Automata
The simplest mopdel of computation
It has a very limited memory

在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表
Σ\Sigma 的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态）。

https://zh.wikipedia.org/wiki/确定有限状态自动机