Automata Theory 简明教程
Automata Theory Introduction
Automata – What is it?
术语“自动机”源自希腊语单词“αὐτόματα”，意思是“自作用”。自动机（复数形式为 Automata）是一种抽象的自驱动计算设备，它自动执行预定的操作序列。
The term "Automata" is derived from the Greek word "αὐτόματα" which means "self-acting". An automaton (Automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically.
具有有限状态数的自动机称为 Finite Automaton (FA) 或 Finite State Machine (FSM)。
An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM).
Formal definition of a Finite Automaton
自动机可以用 5 元组 (Q, ∑, δ, q0, F) 表示，其中 −
An automaton can be represented by a 5-tuple (Q, ∑, δ, q0, F), where −
-
Q is a finite set of states.
-
∑ is a finite set of symbols, called the alphabet of the automaton.
-
δ is the transition function.
-
q0 is the initial state from where any input is processed (q0 ∈ Q).
-
F is a set of final state/states of Q (F ⊆ Q).
Related Terminologies
Alphabet
-
Definition − An alphabet is any finite set of symbols.
-
Example − ∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and ‘d’ are symbols.
String
-
Definition − A string is a finite sequence of symbols taken from ∑.
-
Example − ‘cabcad’ is a valid string on the alphabet set ∑ = {a, b, c, d}
Length of a String
-
Definition − It is the number of symbols present in a string. (Denoted by |S|).
-
Examples − If S = ‘cabcad’, |S|= 6 If |S|= 0, it is called an empty string (Denoted by λ or ε)
Kleene Star
-
Definition − The Kleene star, ∑*, is a unary operator on a set of symbols or strings, ∑, that gives the infinite set of all possible strings of all possible lengths over ∑ including λ.
-
Representation − ∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪……. where ∑p is the set of all possible strings of length p.
-
Example − If ∑ = {a, b}, ∑* = {λ, a, b, aa, ab, ba, bb,………..}