有穷自动机的形式定义：有穷自动机是一个5元组：状态集, 字母表, 转移函数, 起始状态, 接受状态。转移函数定义了从一个状态转换到另一个状态的转换规则。
设A是机器M接受的全部字符串，称A是机器M的语言，记作L（M）=A，又称M识别A或M接受A。
设计有穷自动机：
首先，为了能做出这样的判断，必须估算出当读一个字符串时需要记住它的哪些东西。
其次，通过观察怎么根据读到的符号，从一种可能性转移到另一种可能性来设计转移函数。
再次，把起始状态设置为对应于到现在为止，还没有看到任何符号相关联的可能性状态。
最后，把接受状态设置为这样一些状态，它们对应于你打算要接受输入串的可能性。
正则运算：并、连结和星号，正则语言在正则运算下是封闭的。
非确定性有穷自动机（NFA）：允许读入空时转移。NFA和DFA是等价的，有时构造NFA比构造DFA容易，NFA可能比DFA小得多。
正则表达式的形式定义：
字母表中的任何一个元素都是正则表达式。e是是正则表达式。空集是是正则表达式。 正则表达式并上正则表达式仍是正则表达式。正则表达式连接正则表达式仍是正则表达式。正则表达式重复后仍是正则表达式。
广义的非确定性有穷自动机：转移箭头可以用任何正则表达式来标记。
关于正则语言的泵引理：言多必复。