确定性有限自动机

确定性有限自动机(Deterministic Finite Automaton, DFA)

Posted by persuez on May 24, 2018

形式化定义

  1. 我们用5元组$(Q,\sum,\delta,q_0,F)$定义确定性有限自动机

  2. $Q$是状态的有限集
  3. $\sum$ 是字母表
  4. $\delta$是转移函数,映射关系为$Q×\sum \rightarrow Q$
  5. $q_0$表示开始状态
  6. $F \subseteq Q$是accept状态集
  7. 既然有了以上定义,接下来定义一个DFA$M$ accepts 字符串$w$,其中:$w = w_1w_2 … w_n, w_i \in \sum $, $r_0,r_1,…,r_n$是$Q$状态集元素的一个排列:
  8. $r_0 = q_0$
  9. $\delta(r_i, w_{i+1})=r_{i+1}, i = 0,…,n-1$
  10. $r_n \in F$
  11. $A$是一个包含所有有限自动机$M$accepts的字符串的集合,即$ A= \lbrace w \mid M\ accepts \ w \rbrace$,那么$A$就是$M$的语言,记作$L(M)=A$。对此,我们称$M$ recognizes $A$。注意:一个有限自动机可能会accepts很多字符串,但它只能recognizes一个语言。如果这个有限自动机不接受任何字符串,那它仍然recognizes一个语言,the empty language $\emptyset$。如果一个语言可以被某个有限自动机recognizes,那么这个语言被称为正则语言regular language

正则语言的操作(regular operation)

设$A$和$B$都是正则语言

  1. union并: \(A \cup B=\lbrace x \mid x \in A\ or\ x \in B \rbrace\)
  2. concatenation 连接: \(A º B=\lbrace xy \mid x \in A\ and\ y\in B \rbrace\)
  3. star: \(A^*= \lbrace x_1x_2...x_k \mid k \geq 0 \ and\ each\ x_i \in A \rbrace\) 以上三种regular operation都是封闭(closed)的。在另几篇文章中会证明封闭性。