有穷自动机的分类

Love The Way You Lie 2022-03-22 09:00 239阅读 0赞

### 文章目录 ###

*  FA的分类
 *  确定的有穷自动机（DFA）
 *  非确定的有穷状态机（NFA）
 *  DFA和NFA的等价性

# FA的分类 #

*  确定的FA（Deterministic finite automata, DFA）
 *  非确定的FA（Nondeterministic finite automata, NFA）

# 确定的有穷自动机（DFA） #

M = ( S , ∑ , δ , s 0 , F ) M=(S, \\sum, \\delta,s\_0,F) M=(S,∑,δ,s0,F)

*  S：有穷状态集
 *   ∑ \\sum ∑：输入字母表，即输入符号集合。假设 ϵ \\epsilon ϵ不是 ∑ \\sum ∑中的元素
 *   δ \\delta δ：将 S ∗ ∑ S\*\\sum S∗∑映射到S的**转换函数**。 ∀ s ∈ S , a ∈ ∑ \\forall s \\in S, a \\in \\sum ∀s∈S,a∈∑， δ ( s , a ) \\delta(s,a) δ(s,a)表示从状态s出发沿着标记为a的边所能到达的状态。
 *   s 0 s\_0 s0：开始状态（或初始状态）， s 0 ∈ S s\_0 \\in S s0∈S
 *  F：接收状态（或终止状态）集合， F ⊆ S F \\subseteq S F⊆S

**可以用转换表表示DFA**

# 非确定的有穷状态机（NFA） #

M = ( S , ∑ , δ , s 0 , F ) M=(S, \\sum, \\delta,s\_0,F) M=(S,∑,δ,s0,F)

*   δ \\delta δ：将 S ∗ ∑ S\*\\sum S∗∑映射到 2 S 2^S 2S的**转换函数**。 ∀ s ∈ S , a ∈ ∑ \\forall s \\in S, a \\in \\sum ∀s∈S,a∈∑， δ ( s , a ) \\delta(s,a) δ(s,a)表示从状态s出发沿着标记为a的边所能到达的状态集合。
 *  其余与DFA相同

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]

这就是一个典型的NFA。从状态0出发沿着标记为a（b）的边所能到达的状态集合不止一个。

# DFA和NFA的等价性 #

*  对任何NFA，存在识别同一语言的DFA
 *  对任何DFA，存在识别同一语言的NFA

**给定一个正则文法就能给出一个正则表达式，给定一个正则表达式就能给出一个FA**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20220322/4b0dc200e1a644da8e955eb93703b8e4.png