CENG205 - Theory of Computation
Assist. Prof. Dr. Emre ŞATIR
Week 2
Finite Automata
Prerequisites – STRINGS and LANGUAGES
Symbol: a, b, c, 0, 1, 2, 3,… (The members of the alphabet are the symbols of the alphabet)
An alphabet is a nonempty, finite “set” of symbols. (is denoted by “Σ”(sigma))
Σ 1 = {0,1}
Σ 2 = {a, b, c, d, e, f, g, h, i, j , k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
Γ = {0, 1, x, y, z}
A string over an alphabet is a finite “sequence” of symbols from the alphabet.
0, 1, 0110, a, abba
The length of a string is the number of symbols in the string.
The length of string 𝑤 is usually written as |𝑤|
The empty string is denoted by “ε”(epsilon) and has length 0.
The empty string plays the role of 0 in a number system.
Prerequisites – STRINGS and LANGUAGES
The reverse of w is written as wR
abcd → dcba
Substring: “bc” is a substring of “abcd”
Concatenation: of “ab” and “cd” is “abcd”
xk is x...x, k times (concatenating a string with itself many times)
A language is a “set” of strings (can be finite or infinite).
Σ = {0,1}
L 1 = set of all strings of length 2 (finite set)
= {00, 01, 10, 11}
The empty language (is denoted by ø) is the set with no strings.
Prerequisites – STRINGS and LANGUAGES
Powers of Σ
Let Σ = {0,1}
Σ0 = set of all strings of length 0 → {ε} is not empty language!
Σ1 = set of all strings of length 1 → {0,1}
Σ2 = set of all strings of length 2 → {00,01,10,11}
Σ3 = set of all strings of length 3 → {000,001,010,100,101,011,110,111}
…
Σn = set of all strings of length n
Σ* = set of all possible strings of all lengths over alphabet Σ (an infinite set).
Σ* = Σ0 ∪ Σ1 ∪ Σ2 ∪ Σ3 ∪ …
(Σ* always includes ε)
FINITE AUTOMATA
Finite automata are good models for computers with an extremely limited
amount of memory.
What can a computer do with such a small memory? Many useful things!
In fact, we interact with such computers all the time, as they lie at the heart
of various electromechanical devices.
The controller for an automatic door is one example of such a device.
State diagram for an automatic door controller
State transition table for an automatic door controller
or “initial state”
“final” or “terminating” state
(edges))
Another Example
0 1
𝑀2 0,1
1
𝑞1 𝑞2 𝑞3
0
Examples: 01101 → Accept
00101 → Reject
𝑀2 accepts exactly those strings in 𝐴 where
𝐴 = {𝑤| 𝑤 contains substring 11}.
Finite Automata – Formal Definition
Defn: A finite automaton 𝑀 is a 5-tuple (𝑄, Σ, 𝛿, 𝑞0, 𝐹)
𝑄 finite set of states
Σ finite set of alphabet symbols
𝛿 transition function 𝛿: 𝑄 × Σ → 𝑄 Example:
a 𝑟
𝛿 (𝑞, 𝑎) = 𝑟 means 𝑞
𝑀1
0
𝑞0 start state 1
0,1
𝑞1 𝑞2 1 𝑞3
𝐹 set of accept states
0
𝑀1 = (𝑄, Σ, 𝛿, 𝑞1, 𝐹)
𝛿= 0 1
𝑄 = {𝑞1, 𝑞2, 𝑞3}
𝑞1 𝑞1 𝑞2
Σ = {0, 1}
𝑞2 𝑞1 𝑞3
q1 is start state 𝑞3 𝑞3 𝑞3
𝐹 = {𝑞3}
Finite Automata – Recognizing languages
A machine may accept several strings, but it always
recognizes only one language.
If the machine accepts no strings, it still recognizes one
language—namely, the empty language ø.
Recognizing languages
- 𝐿(𝑀) = {𝑤| 𝑀 accepts 𝑤}
- 𝐿(𝑀) is the language of 𝑀
- 𝑀 recognizes 𝐿(𝑀)
Say that 𝐴 is the language of 𝑀 and that 𝑀 recognizes 𝐴 and that 𝐴 = 𝐿(𝑀).
Finite Automata – Computation
Defn: 𝑀 accepts string 𝑤 = 𝑤1𝑤2 … 𝑤𝑛 each 𝑤𝑖 𝜖 Σ
if there is a sequence of states 𝑟0, 𝑟1, 𝑟2, , … , 𝑟𝑛 𝜖 𝑄
where:
- 𝑟0 = 𝑞0
- 𝑟𝑖 = 𝛿(𝑟𝑖−1 , 𝑤𝑖) for 1 ≤ 𝑖 ≤ 𝑛
- 𝑟𝑛 𝜖 𝐹
Finite Automata – Examples
M3
M3 accepts all strings that end in a 1. Thus L(M3) = {w| w ends in a 1}.
Finite Automata – Examples
MM
3
4
L(M4) = {w| w is the empty string ε or ends in a 0}.
Note that because the start state is also an accept state, M4 accepts the empty
string ε. As soon as a machine begins reading the empty string, it is at the end; so if
the start state is an accept state, ε is accepted.
Finite Automata – Examples
MM
3
4
M5
M5 accepts all strings that start and end with a or that start and end with b.
In other words, M5 accepts strings that start and end with the same symbol.
