[go: up one dir, main page]
Scribd
Upload
14 views27 pages

Week 2

The document discusses finite automata including definitions, examples, and how they recognize languages. Finite automata have a finite set of states and recognize strings over an alphabet based on transitions between states. Examples of state diagrams and languages recognized are provided.

Uploaded by

14mervekaya01
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views27 pages

Week 2

The document discusses finite automata including definitions, examples, and how they recognize languages. Finite automata have a finite set of states and recognize strings over an alphabet based on transitions between states. Examples of state diagrams and languages recognized are provided.

Uploaded by

14mervekaya01
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 27

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.

You might also like