lowsfish

• 一般我们会用状态图来描述一个有限自动机（Finite Automata）。它有且只有一个起始状态（在状态图中，一个从不知道什么地方来的箭头指向的状态），有一些接受状态（状态图中有两个圈圈起来的状态）。
• 有限自动机的输出是接受或者拒绝。
• 下图是一个有限自动机 （我们叫它 ），它能接受所有以1结尾的串。

• 有限自动机的形式定义
  • 有限自动机是一个5元组（元组的定义在文末）  ，其中
    •  是一个有限的集合，叫做状态集。
    •  是一个有限的集合，叫做字母表。
    •  （这个记号的定义在文末）是一个转移函数。
    •  是起始状态。
    •  是接受状态集。

• 一个机器  接受的全部字符串的集合  ，叫做机器  的语言（语言的定义在文末），记作  。

• 现在我们可以给出在有限自动机上的计算的定义了。
  • 设  是一台有限自动机，  是一个字符串且每个  都是字母表  中的一个字符。如果有一个  中的状态序列  满足以下3个条件：
    • 
    • 
    • 
    • 则  接受  。（想问怎么去掉这句话前面的圆点并且保持缩进）

• 一个语言如果能被某种有限自动机接受，那么它就被称为正则语言。

• 正则运算：
  • 并： 
  • 连结： 
  • 星号： 
• 正则语言类在三种正则运算下封闭，即两种正则语言（对于星号运算来说，只需要一种）做正则运算，得到的结果仍是正则语言。

附：各种定义

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