跳转至

确定的有穷自动机DFA

确定的有穷自动机（DFA）

  • 具有有穷个状态，不同的状态代表不同的意义。按照实际的需要，可以在不同的状态间转换
  • 将输入字符串中的字符汇集在一起构成一个字母表。处理的所有字符串都是该字母表上的字符串
  • 在任一状态下，从输入字符串中读入一个字符，根据当前状态和读入的这个字符转到新的状态
  • 有一个开始状态
  • 有一些终止（或接受）状态，表示到目前为止所读入的字符构成的字符串是语言的一个句子

组成结构

  1. \(Q\): 有穷状态集
  2. \(\Sigma\): 有穷输入符号集或字母表
  3. \(\delta\): \(Q\times \Sigma\to Q\)状态转移函数
  4. \(q_0\in Q\): 初始状态
  5. \(F\subseteq Q\): 终结状态集或接受状态集

例：用DFA表示电视遥控开关

img

  • 字母表\(\Sigma=\{p\}\)，p——按开关键
  • 有穷状态集\(Q\)
    • 电视关(\(q_0\))
    • 电视开(\(q_1\))
  • 状态转移函数\(\delta\)
\[\delta(q_0,p)=q1,\delta(q_1,p)=q_0\]

例：设计DFA，在任何由0和1组成的字符串中，接受含有01子串的全部串

  • 字母表\(\Sigma=\{0,1\}\)
  • 有穷状态集\(Q\)
    • 初始状态\(q_0\)：还没有看到0
    • \(q_1\)：已经看到了0
    • \(q_2\)：已经看到了01
  • 状态转移函数
\[\delta(q_0,0)=q_1,\delta(q_1,1)=q_2,\delta(q_2,0)=q_2\]
\[\delta(q_0,1)=q_0,\delta(q_1,0)=q_1,\delta(q_2,0)=q_2\]

DFA设计方法

法一

  1. 从初始状态开始，对每个状态，依次确定每个字符作为输入时，可能到达的状态：

    1. 如果到达的状态是之前已出现的状态，建立当前状态到应到达状态的边；
    2. 如果到达的状态是之前未出现的状态，增加新的状态，建立当前状态到新增状态的边

  2. 确定终止状态

法二

  • 从初始状态开始，重点关注可以到达结束状态的路径，然后对每个节点补充其他字符作为输入时的边和状态

例：若\(\Sigma=\{0,1\}\)，给出接受全部含有偶数个0和偶数个1的串的DFA

img

例：设计DFA接收以下语言

\[L=\{x|x\in \{0,1\}^* \wedge x中至少包含一个子串010\}\]

img

扩展转移函数

扩展状态转移函数\(\delta\)到字符串，定义扩展转移函数\(\hat{\delta}\):

\[\hat{\delta}(q,w)=\begin{cases}q&w=\epsilon\\\delta(\hat{\delta}(q,x),a)&w=xa\end{cases}\]

上式中\(a\)是一个字符，\(w\)和\(x\)是字符串

例：接受全部含有01子串的DFA，\(\hat{\delta}处理串0101的过程\)

img

DFA语言与正则语言

若\(D=(Q,\Sigma,\delta,q_0,F)\)是一个DFA，则\(D\)接受的语言为

\[L(D)=\{w\in \Sigma^*|\hat{\delta}(q_0,w)\in F\}\]

即所有能使DFA从开始状态到达接受状态的符号串集合

如果语言\(L\)是某个DFA \(D\)的语言，则称其为正则语言

有限字符串对应的语言是正则语言
\(\Phi\)，\(\{\epsilon\}\)都是正则语言，状态转移图如下
img