Bổ túc toán 3
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (258.15 KB, 31 trang )
1
Automata hữu hạn &
Biểu thức chính quy
Nội dung:
•
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
Chương 3:
2
Phân loại FA
FA
(Finite Automata)
DFA
Deterministic
Finite Automata
NFA
Nondeterministic
Finite Automata
Biểu thức
chính quy
3
Start
1
1
0
0
0
0 1
1
a b
c
d
q
1
q
0
q
3
q
2
Ví dụ:
Input
Bộ điều khiển
10100110
Q : 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
0
∈ 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
Automata hữu hạn đơn định (DFA)
4
Mở rộng hàm chuyển trạng thái
1. δ(q, ε) = q
2. δ(q, wa) = δ( δ(q,w), a) với ∀ w, a
Ngôn ngữ được chấp nhận:
L(M) = { x | δ( q
0
, x ) ∈ F }
Ngôn ngữ
chính quy
Ví dụ: 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
5
Giải thuật hình thức
•
Mục đích: kiểm tra một chuỗi nhập x có thuộc ngôn ngữ
L(M) được chấp nhận bởi automata M.
•
Input: chuỗi nhập x$
•
Output: câu trả lời ‘YES’ hoặc ‘NO’
•
Giải thuật:
q := q
0
;
c := nextchar ; {c là ký hiệu nhập được đọc tiếp theo}
While c <> $ do
begin
q := δ(q, c);
c := nextchar ;
end
If (q in F) then write("YES") else write("NO");
6
Automata hữu hạn không đơn định (NFA)
Nhận xét:
•
Ứ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
Start
0
1
1
0
1
0
q
0
q
3
q
4
1
0
q
1
q
2
0
1
•
Ví dụ: cho automata M (hình vẽ) và xét chuỗi nhập 01001
0
0
10010
1 0 0 1
1
q
0
q
0
q
0
q
0
q
0
q
0
q
3
q
1
q
3
q
3
q
1
q
4
q
4
7
Định nghĩa NFA
Chú ý: khái niệm δ(q, a) 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àm chuyển trạng thái mở rộng:
•
δ(q, ε) = {q}
•
δ(q, wa) = { p | có một trạng thái r trong δ(q, w) mà p∈δ(r, a) }
= δ( δ(q,w), a)
•
δ(P, w) = ∪
q∈P
δ(q, w) với ∀P ⊆ Q
Q : tập hữu hạn các trạng thái.
Σ : bộ chữ cái nhập.
δ : hàm chuyển ánh xạ Q x Σ → 2
Q
q
0
∈ 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)
8
Ví dụ: xét chuỗi nhập w=01001 và NFA đã cho ở trên
•
M( {q
0
, q
1
, q
2
, q
3
, q
4
}, {0, 1}, δ, q
0
, {q
2
, q
4
} )
{q
4
}{q
4
}q
4
Ø{q
4
}q
3
{q
2
}{q
2
}q
2
{q
2
}Øq
1
{q
0
,q
1
} {q
0
,q
3
} q
0
10Trạng thái
Inputδ
•
δ(q
0
, 0) = {q
0
,q
3
}
•
δ(q
0
, 01) = δ( δ(q
0
, 0), 1)
= δ({q
0
, q
3
},1) = δ(q
0
, 1)
∪ δ(q
3
, 1) = {q
0
, q
1
}
•
δ(q
0
, 010) = {q
0
, q
3
}
•
δ(q
0
, 0100) = {q
0
, q
3
, q
4
}
•
δ(q
0
, 01001) = {q
0
, q
1
, q
4
}
Do q
4
∈ F nên w=01001 ∈ L(M)
Ví dụ về NFA
9
Sự tương đương giữa DFA & NFA
Định lý 1: Nếu L là tập được chấp nhận bởi một NFA thì tồn
tại một DFA chấp nhận L.
Giả sử NFA M={Q, Σ, δ, q
0
, F} chấp nhận L
Ta xây dựng DFA M’={Q’, Σ, δ’, q
0
’, F’} chấp nhận L
•
Q’ = 2
Q
. Một phần tử trong Q’ được ký hiệu là [q
0
, q
1
,
…, q
i
] với q
0
, q
1
, …, q
i
∈ Q
•
q
0
’ = [q
0
]
•
F’ là tập hợp các trạng thái của Q’ có chứa ít nhất một
trạng thái kết thúc trong tập F của M
•
Hàm chuyển δ’([q
1
, q
2
,..., q
i
], a) = [p
1
, p
2
,..., p
j
] nếu và
chỉ nếu δ({q
1
, q
2
,..., q
i
}, a) = {p
1
, p
2
,..., p
j
}
10
Ví dụ về sự tương đương giữa DFA & NFA
Ví dụ: NFA M ({q
0
, q
1
}, {0, 1}, δ, q
0
, {q
1
}) với hàm chuyển
δ(q
0
,0) = {q
0
, q
1
}, δ(q
0
,1) = {q
1
}, δ(q
1
,0) = ∅, δ(q
1
,1) = {q
0
, q
1
}
Ta sẽ xây dựng DFA tương đương M’ (Q’, {0, 1}, δ’, [q
0
], F’)
•
Q’ = {∅, [q
0
], [q
1
], [q
0
, q
1
]}
•
F’ = {[q
1
], [q
0
, q
1
]}
•
Hàm chuyển δ’
δ’(∅, 0) = δ’(∅, 1) = ∅
δ’([q
0
], 0) = [q
0
, q
1
]
δ’([q
0
], 1) = [q
1
]
δ’([q
1
], 0) = ∅
δ’([q
1
], 1) = [q
0
, q
1
]
δ’([q
0
, q
1
], 0) = [q
0
, q
1
]
δ’([q
0
, q
1
], 1) = [q
0
, q
1
]
11
NFA với ε- dịch chuyển (NFAε)
Định nghĩa: NFAε M(Q, Σ, δ, q
0
, F)
•
δ : hàm chuyển ánh xạ Q x (Σ ∪ {ε}) → 2
Q
•
Khái niệm δ(q, a) là tập hợp các trạng thái p sao cho có
phép chuyển nhãn a từ q tới p, với a ∈ (Σ ∪ {ε})
q
0
q
1
q
2
ε
0
1
2
Start
ε
Ví dụ: xây dựng NFA chấp nhận chuỗi 0
*
1
*
2
*
q
0
q
1
q
2
0, 1
0
1
2
Start
1, 2
0, 1, 2
12
Mở rộng hàm chuyển trạng thái cho NFAε
Định nghĩa ε-CLOSURE:
●
ε-CLOSURE(q) = { p | có đường đi từ q tới p theo nhãn ε }
●
ε-CLOSURE(P) = ∪
q∈P
ε-CLOSURE(q)
Hàm chuyển trạng thái mở rộng: mở rộng δ thành δ*
•
δ* : Q x Σ* → 2
Q
•
δ*(q, w) = { p | có đường đi từ q tới p theo nhãn w, trên
đường đi có thể chứa cạnh nhãn ε }
Ta có:
•
δ*(q, ε) = ε-CLOSURE(q)
•
δ*(q,a) = ε-CLOSURE(δ(δ*(q, ε),a))
•
δ*(q, wa) = ε-CLOSURE( δ( δ*(q, w), a) )
Cách khác: δ*(q, wa) = ε-CLOSURE(P)
với P = { p | r ∈ δ*(q, w) và p ∈ δ(r, a) }
•
δ*(R, w) = ∪
q∈R
δ*(q, w)
