Some basic terms

Alphabet ($\Sigma$)

字母表：a set of non-empty finite elements/symbols
一个非空的有限符号集合 $\Sigma$

String

字符串：any finite sequence consisted of symbols in $\Sigma$
由 $\Sigma$ 中符号组成的有限序列

Empty string ($\varepsilon$)

空串：null sequence, also a string of $\Sigma$ $|\varepsilon| = 0$
长度为 0 的字符串

$\Sigma^*$

all strings over $\Sigma$, including $\varepsilon$
所有可能字符串（包括 $\varepsilon$）

Length

长度：the amount of symbols in a string 字符串中符号的个数

String Operations

Concatenation

连接：$UV = \{ \alpha\beta \mid \alpha \in U \land \beta \in V \}$
例：$U=\{a, aa\}, V=\{b, bb\} \to UV=\{ab, abb, aab, aabb\}$

Power

幂运算：$U^n$ = n 次连接
$U^0 = \varepsilon, U^1 = U, U^2 = UU, U^3 = UUU \dots$

Positive Closure

$U^+ = \{ U, UU, UUU, \dots, U^n, \dots \}$

Kleene Closure

$U^* = \{\varepsilon\} \cup U^+ = \{\varepsilon, U, UU, UUU, \dots\}$

Finite State Machine (FSM)

• Finite State Machine (FSM) = Finite Automata (FA)
• a language can be described by regular grammar, it can be analyzed by FSM
  • 一个语言能被 FSM 识别，就可以成为是正则语法

• Regular Grammar $\rightleftarrows$ FSM $\rightleftarrows$ Regular Language

  it is used to express (type 3 grammar) Regular grammar FSM 用于表达正则语法
  The language which is described by this grammar is regular language 正则语法表示的语言是正则语言

• Every FSM recognizes exactly ONE language
  每一个 FSM 只能对应一个语言

Formal Definition of FSM

$$ M = (S, \Sigma, f, s_0, Z) $$

$$ \begin{array}{ll} S & \text{finite set of states} \\ \Sigma & \text{finite input alphabet} \\ f: S \times \Sigma \to S & \text{transition function} \\ s_0 \in S & \text{initial state} \\ Z \subseteq S & \text{set of final states} \end{array} $$

$$ L(M) = \{ w \mid f(s_0, w) \in Z, w \in \Sigma^* \} $$