Automata Theory 简明教程

Automata Theory Introduction

Automata – What is it?

术语“自动机”源自希腊语单词“αὐτόματα”，意思是“自作用”。自动机（复数形式为 Automata）是一种抽象的自驱动计算设备，它自动执行预定的操作序列。

具有有限状态数的自动机称为 Finite Automaton (FA) 或 Finite State Machine (FSM)。

Formal definition of a Finite Automaton

自动机可以用 5 元组 (Q, ∑, δ, q0, F) 表示，其中 −

  1. Q 是一个有限的状态集。

  2. ∑ 是一个有限的符号集，称为自动机的 alphabet 。

  3. δ 是转换函数。

  4. q0 是处理任何输入的初始状态 (q0 ∈ Q)。

  5. F 是 Q 的一组终态/状态 (F ⊆ Q)。

Related Terminologies

Alphabet

  1. Definition − 一个 alphabet 是任何有限的符号集。

  2. Example − ∑ = {a, b, c, d} 是 alphabet set ，其中“a”、“b”、“c”和“d”是 symbols 。

String

  1. Definition − A string 是从 ∑ 取出的符号的有限序列。

  2. Example −“cabcad”是字母集合 ∑ = {a, b, c, d} 上的有效字符串。

Length of a String

  1. Definition −它是一个字符串中存在的符号数。（表示为 |S| ）。

  2. Examples −如果 S =“cabcad”，则 |S|= 6 如果 |S|= 0，则称为 empty string （表示为 λ 或 ε ）。

Kleene Star

  1. Definition − 克莱尼星 ∑ * 是符号或字符串集合 ∑ 上的一元运算符，该运算符提供所有可能长度的所有可能字符串的无限集合，包括 ∑ ，包括 λ 。

  2. Representation − ∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪……. 其中 ∑p 是所有长度为 p 的可能字符串的集合。

  3. Example −如果 ∑ = {a, b}，则 ∑* = {λ, a, b, aa, ab, ba, bb,………..}

Kleene Closure / Plus

  1. Definition −集合 ∑+ 是所有可能长度的所有可能字符串的无限集合，不包括 λ。

  2. Representation − ∑+ = ∑1 ∪ ∑2 ∪ ∑3 ∪…….∑+ = ∑* − { λ }

  3. Example −如果 ∑ = { a, b }，则 ∑+ = { a, b, aa, ab, ba, bb,………..}

Language

  1. Definition −语言是某些字母表的 ∑* 的子集。它可以是有限的或无限的。

  2. Example −如果该语言采用 ∑ = {a, b} 上所有可能的长度为 2 的字符串，则 L = { ab, aa, ba, bb }