用户工具

站点工具


01-基础学习:课程:编译原理:实验:实验一:dfa的概念

确定型有穷自动机

DFA的定义

DFA是一个五元组(Q,Sigma,delta,q_0,F),其中:

  1. Q是一个有穷集合,叫做状态集。
  2. Sigma是一个有穷集合,叫做字母表。
  3. delta: Q * Sigma right Q是转移函数。
  4. q_0 in Q 是起始状态。
  5. F subset Q 是接受状态集。

一个DFA例子

M1状态图:

形式描述:

M1=(Q,Sigma,delta,q_0,F),其中

  • Q = lbrace q_1,q_2,q_3 rbrace
  • Sigma = lbrace 0,1 rbrace
  • delta
 <WRAP center box 8%><m> tabular{11111}{1111}{ { } 0 1 q_1 q_1 q_2 q_2 q_3 q_2 q_3 q_2 q_2} </m></WRAP>

* q_1是起始状态。

  • F = {q_2}是接受状态。
01-基础学习/课程/编译原理/实验/实验一/dfa的概念.txt · 最后更改: 2020/04/07 06:34 由 annhe