From 05edb10550817cac599a50238d2fdfd036c44c6f Mon Sep 17 00:00:00 2001 From: ouuan Date: Sat, 14 Sep 2019 10:01:10 +0800 Subject: [PATCH] :pencil2: DFA is not a DAG --- docs/string/automaton.md | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/docs/string/automaton.md b/docs/string/automaton.md index e8286362..624df9f4 100644 --- a/docs/string/automaton.md +++ b/docs/string/automaton.md @@ -5,10 +5,10 @@ 一个 **确定有限状态自动机（DFA）** 由以下五部分构成： 1. **字符集** （ $\Sigma$ ），该自动机只能输入这些字符。 -2. **状态集合** （ $Q$ ）。如果把一个 DFA 看成一张有向无环图（DAG），那么 DFA 中的状态就相当于图上的顶点。 +2. **状态集合** （ $Q$ ）。如果把一个 DFA 看成一张有向图，那么 DFA 中的状态就相当于图上的顶点。 3. **起始状态** （ $start$ ）， $start\in Q$ ，是一个特殊的状态。起始状态一般用 $s$ 表示，为了避免混淆，本文中使用 $start$ 。 4. **接受状态集合** （ $F$ ）， $F\subseteq Q$ ，是一堆特殊的状态。 -5. **转移函数** （ $\delta$ ）， $\delta$ 是一个接受两个参数返回一个值的函数，其中第一个参数和返回值都是一个状态，第二个参数是字符集中的一个字符。如果把一个 DFA 看成一张有向无环图（DAG），那么 DFA 中的转移函数就相当于顶点间的边，而每条边上都有一个字符。 +5. **转移函数** （ $\delta$ ）， $\delta$ 是一个接受两个参数返回一个值的函数，其中第一个参数和返回值都是一个状态，第二个参数是字符集中的一个字符。如果把一个 DFA 看成一张有向图，那么 DFA 中的转移函数就相当于顶点间的边，而每条边上都有一个字符。 DFA 的作用就是识别字符串，一个自动机 $A$ ，若它能识别（接受）字符串 $S$ ，那么 $A(S)=True$ ，否则 $A(S)=False$ 。 -- 2.11.0