Finite State Machine (FSM)

Some basic terms

Alphabet (∑)

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

String

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

Empty string (ε)

空串：null sequence, also a string of ∑ |ε| = 0 长度为 0 的字符串

∑*

all strings over ∑, including ε 所有可能字符串（包括ε）

Length

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

String Operations

Concatenation

连接：UV = {αβ | α∈U & β∈V} 例：U={a,aa}, V={b,bb} → UV={ab, abb, aab, aabb}

Power

幂运算：Uⁿ = n次连接 U⁰=ε, U¹=U, U²=UU, U³=UUU…

Positive Closure

U⁺ = U, UU, UUU, ...Un…

Kleene Closure

U* = ε + U⁺ = {ε, U, UU, UUU...}

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 ⇄ FSM ⇄ 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^* \}$