术语“自动机”源自希腊语“αὐτόματα”，意思是“自作用”。自动机（复数自动机）是一种抽象的自驱动计算设备，可自动执行预定的操作序列。
具有有限数量状态 的自动机自动机可以用 5 元组 (Q, Σ, δ, q 0, F) 表示，其中 -
Q 是有限状态集。
Σ 是一组有限的符号，称为自动机的 字母 。
δ 是传递函数。
Q 0 是处理任何输入的初始状态 (Q 0∈Q) 。
F 是 Q (F⊆Q) 的一组最终状态。
定义–字母是任何有限的符号集。
示例 -Σ = {a,b,c,d} 是字母集 ，其中 'a'、'b'、'c' 和 'd' 是 符号。
定义–字符串是取自Σ的有限符号序列。
示例 - ‘cabcad’ 是字母集上的有效字符串 Σ = {a, b, c, d}
定义 - 字符串中存在的符号数量。 （由 | S | 表示）。
示例–
如果 S = 'cabcad', |S| = 6
定义 – 小星号 、Σ*、 是一组符号或字符串 、Σ、 给出Σ 的无限集全一元对所有可能长度包括 λ 的可能字符串进行算术运算符。
-Σ * = Σ 0 Σ Σ 1 Σ 2…的表示形式。其中 Σ p 是长度为 p 的所有可能字符串的集合。
示例-如果 Σ = {a, b}, Σ * = {λ, a, b, aa, ab, ba, bb,………..}
定义 -集Σ + 是 Σ 上所有可能字符串的无限集合，具有除 λ 之外的所有可能长度。
表示形式-Σ + = Σ 1 Σ 2 Σ Σ 3…………。
Σ + = Σ * − {λ}
示例 - 如果 Σ = {a, b}, Σ + = {a, b, aa, ab, ba, bb,……..}
定义-语言是某个字母Σ的Σ*的子集。它可以是有限的或无限的。
示例 - 如果语言在 Σ = {a, b} 上采用长度为 2 的所有可能字符串，则 L = {ab, aa, ba, bb}
