Why Automata Theory?[編輯 | 編輯原始碼]
Automata theory is for the study of abstract computing devices. The main characters are Finite State Machines.
Part 1. Basic Concepts[編輯 | 編輯原始碼]
1.1 Alphabets[編輯 | 編輯原始碼]
Definition of Alphabets:
- An alphabet is defined as a finite set of symbols.
- Denotion: "Σ";
- e.g., Σ={0,1} is a binary alphabet, Σ={a,b,c,...z} is an alphabet of the English language.
1.2 Strings[編輯 | 編輯原始碼]
Definition of Strings:
- A string is a finite sequence over an alphabet Σ.
- Empty string is denoted by {ε} (pronounced epsilon).
- e.g., 0011,01,0101,... are strings over alphabet Σ={0,1}.
1.2.1 String Operations:[編輯 | 編輯原始碼]
A. Length: |0010| = 4, |1101110| = 7, |ε| = 0;
B. Substrings:
- B-1. Prefix: aaabc, aaabc, aaabc;
- B-2. Suffix: aaabc, aaabc, aaabc;
- B-3. Substring: aaabc;
C. Multiple Strings:
- C-1. Concatenation: α = abd, β = ce → αβ = abdce;
- C-2. Exponentiation: α = abd → α^3= abdabdabd;
- C-3. Reversal: α = abd → a^R = dba;
D. Alphabets:
- D-1. Power of an Alphabet: Σ^k = set of all k-length strings formed by symbols in Σ.
- e.g., Σ = {a,b}, Σ^2 = {aa,ab,ba,bb}.
- D-2. Kleen Closure: Σ* = Σ^0 ∪ Σ^1 ∪ Σ^2 ∪ ...
- D-3. Kleen Plus: Σ+ = Σ^1 ∪ Σ^2 ∪ Σ^3 ...
- Note that Σ* = Σ+ ∪ Σ^0 = Σ+ ∪ {ε}.
1.3 Languages[編輯 | 編輯原始碼]
Definition of Languages:
- A language is a set of strings over an alphabet.
- A language (basically a set) does not have to be finite.
- e.g.:
- The set of all English words is a language over the alphabet Σ={a,b,c,....,z}.
- The set {ε} is a language over ANY alphabet.
- L1 = {0^n1^n|n>=0} is a language over Σ={0,1}.
- ...
Part 2. Finite State Machines (Finite Automata)[編輯 | 編輯原始碼]
Finite state machines (i.e. Finite Automata) is used to determine wherther a string meets a requirement.
It takes a string as an input. If the finite state machine reaches a final state, it accepts the string; otherwise it rejects the string.
2.1 Deterministic Finite Automata (DFA)[編輯 | 編輯原始碼]
Definition of a DFA:
A DFA is defined as a quintuple (Q, Σ, δ, q, F) where:
| Component | Interpretation |
|---|---|
| Q | A finite set of states. |
| Σ | A finite set of input symbols (an alphabet). |
| δ | Translation function, mapping Q x Σ → Q.
i.e., A state takes an input, transmitting to another state. |
| q0 | Unique initial state. |
| F | A set of final states. |