Ktl-icon-tai-lieu

Lý thuyết thông tin phần 3

Được đăng lên bởi Duy Khanh
Số trang: 8 trang   |   Lượt xem: 311 lần   |   Lượt tải: 0 lần
t

0 1 1 0 0 1 0 1

q

q

a

i

k

h

i

u

ñ
b

• Khái niệm DFA & NFA

Trạng thái bắt ñầu

0

Trạng thái kết thúc

3

2

q

1

q

0

• Sự tương ñương giữa DFA & NFA

✏

B

0

✖

1

✒

0

1
0

n

Start

u

p

n

I

c
1

1

x

d

• Biểu thức chính quy

Phép chuyển trên nhãn x

: tập hữu hạn các trạng thái (p, q…)
: bộ chữ cái nhập (a, b … ; w, x, y …)
: hàm chuyển, ánh xạ: Q x Σ → Q
∈ Q : trạng thái bắt ñầu.
F ⊆ Q : tập các trạng thái kết thúc.
3

• Các tính chất của tập chính quy

0

M=(Q, Σ, δ, q0, F)
1

ε
∀

0

A

F

D

eterministic
inite utomata

utomata)

A

Ngôn ngữ

A

ondeterministic
inite utomata
F

N

F

( inite

∈

2

Printed with FinePrint - purchase at 

•
•
•
•
•
•

chính quy
chuỗi nhập w=110101
δ(q0, 1) = q1
δ(q0, 11) = δ(q1, 1) = q0
δ(q0, 110) = δ(q1, 10) = δ(q0, 0) = q2
δ(q0, 1101) = δ(q1, 101) = δ(q0, 01) = δ(q2, 1) = q3
δ(q0, 11010) = … = δ(q3, 0) = q1
δ(q0, 110101) = … = δ(q1, 1) = q0 ∈ F

4

: tập hữu hạn các trạng thái.
: bộ chữ cái nhập.
M=(Q, Σ, δ, q0, F)
: hàm chuyển ánh xạ Q x Σ →
∈ Q : trạng thái bắt ñầu.
F ⊆ Q : tập các trạng thái kết thúc.
: khái niệm
là tập hợp tất cả các trạng thái p
sao cho có phép chuyển từ trạng thái q trên nhãn a.

}

h

o

e

t

i

t

p

ñ

c

c

ư

✎

✏

ñ

☛
p

n

c

u

h

✟

i

ý

h

k

l

{

à

✒

q := q0 ;
c := nextchar ;
While c <> $ do
begin
q := δ(q, c);
c := nextchar ;
end
If (q in F) then write("YES") else write("NO");

0

•
•
•

Q

kiểm tra một chuỗi nhập có thuộc ngôn ngữ
ñược chấp nhận bởi automata .
chuỗi nhập
câu trả lời ‘
’ hoặc ‘ ’

•
•

ε
mà p∈

có một trạng thái r trong

•

∪

q

•

với ∀ ⊆

∈P

5

•

7

δ

q1

4

2

0

4

Trạng thái

0

1

q0

{q0,q3}

{q0,q1}

q1

Ø

{q2}

q2

{q2}

{q2}

q3

{q4}

Ø

q4

{q4}

{q4}

1

q0

0

q3

q3

q1

0

1

2

q4

• Ứng với một trạng thái và một ký tự nhập, có thể có
không, một hoặc nhiều phép chuyển trạng thái.
• DFA là một trường hợp ñặc biệt của NFA
Printed with FinePrint - purchase at 

q4

Do
6

4

0
1

• δ(q0, 0) = {q0,q3}

Input

1

0

q0

q

q3

q0
0

q0
1

q0
0

1

q

q0

0

1

0

1

1

3

q

2

•

4

3

0

0

q

0

q

Start

1
0

0

1
0

1

cho automata M (hình vẽ) và xét chuỗi nhập

∈

nên

∈

• δ(q0, 01) = δ( δ(q0, 0), 1)
= δ({q0, q3},1) = δ(q0, 1)
∪ δ(q3, 1) = {q0, q1}
• δ(q0, 010) = {q0, q3}
• δ(q0, 0100) = {q0, q3, q4}
• δ(q0, 01001) = {q0, q1, q4}
8

ε
NFA chấp nhận chuỗi 0+1+2+
0

1

Start

0

q

1

2

3

1

0

0

2

Giả sử
chấp nhận L
Ta xây dựng
chấp nhận L
Một phần tử trong
ñược ký hiệu là [q...
1
Khái niệm DFA & NFA
Sự tương ñương giữa DFA & NFA
Biểu thức chính quy
Các tính chất của tập chính quy
2
( inite utomata)
eterministic
inite utomata
ondeterministic
inite utomata
3
Start
1
1
0
0
0
0 1
1
a b
c
d
ñ
1
0
1
0
0
1
1
0
: tập hữu hạn các trạng thái (p, q…)
: bộ chữ cái nhập (a, b … ; w, x, y …)
: hàm chuyển, ánh xạ: Q x Σ → Q
Q : trạng thái bắt ñầu.
F Q : tập các trạng thái kết thúc.
M=(Q, Σ, δ, q
0
, F)
Trạng thái bắt ñầu
Trạng thái kết thúc
x
Phép chuyển trên nhãn x
4
ε
εε
ε
Ngôn ngữ
chính quy
chuỗi nhập w=110101
δ(q
0
, 1) = q
1
δ(q
0
, 11) = δ(q
1
, 1) = q
0
δ(q
0
, 110) = δ(q
1
, 10) = δ(q
0
, 0) = q
2
δ(q
0
, 1101) = δ(q
1
, 101) = δ(q
0
, 01) = δ(q
2
, 1) = q
3
δ(q
0
, 11010) = … = δ(q
3
, 0) = q
1
δ(q
0
, 110101) = … = δ(q
1
, 1) = q
0
F
Printed with FinePrint - purchase at www.fineprint.com
Lý thuyết thông tin phần 3 - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Lý thuyết thông tin phần 3 - Người đăng: Duy Khanh
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
8 Vietnamese
Lý thuyết thông tin phần 3 9 10 532