自动机,或有穷状态的机器,是描述(或“机器”)特定类型算法的数学方法。特别地,有穷自动机可用作描述在输入串中识别模式的过程,因此也能用作构造扫描程序。当然有穷自动机与正则表达式之间有着很密切的关系,在下一节中大家将会看到如何从正则表达式中构造有穷自动机。但在学习有穷自动机之前,先看一个说明的示例。通过下面的正则表达式可在程序设计语言中给出标识符模式的一般定义(假设已定义了letter 和digit):identifier=letter (letter| digit)*它代表以一个字母开头且其后为任意字母和或数字序列的串。