1. 有限自动机

  • 一般我们会用状态图来描述一个有限自动机(Finite Automata)。它有且只有一个起始状态(在状态图中,一个从不知道什么地方来的箭头指向的状态),有一些接受状态(状态图中有两个圈圈起来的状态)。
  • 有限自动机的输出是接受或者拒绝
  • 下图是一个有限自动机 (我们叫它M_1 ),它能接受所有以1结尾的串。
图1 一个有限自动机
  • 有限自动机的形式定义
    • 有限自动机是一个5元组(元组的定义在文末) (Q, \Sigma, \delta,q_0,F) ,其中
      • Q 是一个有限的集合,叫做状态集
      • \Sigma 是一个有限的集合,叫做字母表。
      • \delta:Q\times \Sigma\rightarrow Q (这个记号的定义在文末)是一个转移函数
      • q_0\in Q 是起始状态
      • F\subseteq Q 是接受状态集

 

  • 一个机器 M 接受的全部字符串的集合 A ,叫做机器 M 的语言(语言的定义在文末),记作 L(M)=A 。

 

  • 现在我们可以给出在有限自动机上的计算的定义了。
    • 设 M=(Q,\Sigma,\delta,q_0,F) 是一台有限自动机, w=w_1w_2\dots w_n 是一个字符串且每个 w_i 都是字母表 \Sigma 中的一个字符。如果有一个 Q 中的状态序列 r_0,r_1,\dots,r_n 满足以下3个条件:
      • r_0=q_0
      • \delta(r_i,w_i+1)=r_i+1, i=0,\dots,n-1
      • r_n\in F
      • 则 M 接受 w 。(想问怎么去掉这句话前面的圆点并且保持缩进)
  • 一个语言如果能被某种有限自动机接受,那么它就被称为正则语言

 

  • 正则运算
    • : A\cup B=\{x|x\in A或x\in B\}
    • 连结: A\circ B=\{xy|x\in A且y\in B\}
    • 星号: A^*=\{x_1x_2\cdots x_k|k\ge0且每一个x_i\in A\}
  • 正则语言类在三种正则运算下封闭,即两种正则语言(对于星号运算来说,只需要一种)做正则运算,得到的结果仍是正则语言。

 

附:各种定义

  • 元组:有限的序列。5元组即包含5个元素的元组。
  • A\times B :即笛卡尔积,是第一个元素属于 A ,第二个元素属于 B 的所有有序对组成的集合。
  • f:D\rightarrow R , f 称为函数或者映射,是一个输入-输出的关系。
  • 语言:一些字符串的集合。

2 条思考于 “1. 有限自动机

发表评论

电子邮件地址不会被公开。

*