Giảng viên hướng dẫn:
Học viên thực hiện:
Automata Assignment
Convert NFA to DFA
4/2011
Contents
AUTOMATA
I. DFA – Automata hữu hạn đơn định
1. Định Nghĩa :
Ôtomat hữu hạn đơn định (DFA) là 1 tổ hợp M = (Q, ∑, δ, q
0
, F).
Trong đó Q là tập hữu hạn các trạng thái , ∑ là tập hữu hạn các kí tự đầu vào
gọi
là bảng ký tự, q
0
Q là trạng thái bắt đầu, F là tập hợp con của Q gọi là tập
trạng
thái kết thúc (trạng thái đoán nhận).
Và δ là hàm chuyển đổi trạng thái Q x ∑ → Q.
Một Ôtomat có thể xem là một bộ gồm 5 thành phần :
− Một thanh ghi trong đơn.
2
− Một tập hợp các giá trị cho thanh ghi.
− Một băng đầu vào
− Một đầu đọc băng vào.
− Một tập các lệnh để thực hiện chuyển đổi.
Các trạng thái của 1 DFA miêu tả hình trạng bên trong của máy và thường
biểu thị bằng q
o
,q

δ : Q x ∑ → Q.
3
Hay là δ(q
i
, a) = q
k
.Với q
i
là các trạng thái trong tập Q.
Với DFA nói riêng và các Ôtomat nói chung ta có thể đưa ra các hàm chuyển đổi
dưới dạng bảng tương ứng giữa các kí tự vào và các trạng thái của Q.

2. Ví Dụ :

Ta xét ví dụ sau để hiểu rõ hơn về vấn đề :
Cho một Ôtomat hữu hạn đơn định M có :
Q = {q0, q1}
∑ = {a,b}
F = {q1}
Và các hàm chuyển đổi sau :
δ(q0, a) = q1
δ(q0, b) = q0
δ(q1, a) = q1
δ(q1, b) = q0
Sau đây sẽ là các chuyển đổi và miêu tả về hoạt động của M khi xâu đầu vào là
aba.
q
0
aba → q
1

,q
1
,q
2
}, ∑ = {a, b}, F = { q
2
}
Và hàm chuyển đổi δ cho dưới dạng bảng sau :
5
Ta có giản đồ trạng thái như sau :

Giả sử p
w
là một đường từ q
0
đọc xâu vào w và kết thúc tại trạng thái q
w
. Định
lí sau sẽ chứng minh cho chúng ta là chỉ có một con đường duy nhất cho mọi xâu
ω thuộc bảng chữ vào ∑
*
.
b. Định lí :
Coi M = {Q, ∑, δ, q
o
, F} là một Ôtomat hữu hạn đơn định. Xâu ω tạo ra một
đường đi duy nhất p
ω
trong giản đồ trạng thái của M và δ(q
0

. Qua đó ta thấy chỉ có một con đường duy nhất từ q
o
đọc xâu ω vì p
u
là con
đường duy nhất đọc xâu u, còn chỉ có duy nhất một cung nhãn a rời q
u
.Trạng thái
kết thúc của đường đi p
ω
được quyết định bởi chuyển đổi δ(q
u
, a).Từ định nghĩa
của hàm chuyển đổi mở rộng ta có δ
*
(q
o
, ω) = δ( δ
*
(q
o
, u), a) vì
ta có δ
*
(q
o
, u) = q
u
, q
ω =

*
) và δ
*
(q
i
, a) = δ(q
i
, a).
- Bước đệ quy : Coi ω là một xâu có độ dài n > 1. Thì ω = ua và chuyển đổi
δ
*
(q
i
, ua) = δ(δ
*
(q
i
, u), a).

d. Ngôn ngữ đoán nhận :
Ngôn ngữ đoán nhận bởi Ôtomat hữu hạn đơn định M là tập các xâu trong ∑
*

được đoán nhận bởi DFA M kí hiệu L(M). Hay là được định nghĩa như sau :
L(M) = {ω Є ∑
*
|δ
*
(q
0


Các thành phần của NFA gần như là giống các thành phần của DFA chỉ khác ở
hàm chuyển đổi về số trạng thái mà Ôtomat có thể chuyển tới khi sử lí một kí tự
đầu
vào. Với DFA thì chỉ có một trạng thái được chuyển tới khi sử lí một kí tự vào từ
một trạng thái cho trước. Còn trong NFA thì có nhiều hơn một trạng thái có thể
đến được từ một trạng thái cho trước khi xử lí một kí tự đầu vào. Và dễ thấy DFA
là một trường hợp đặc biệt của NFA khi nó chỉ đi đến một trạng thái khác khi đọc
một ký tự vào.
III .Sự Tương Đương Giữa DFA Và NFA
Ta sẽ thấy rằng sự mở rộng DFA thành NFA không tăng thêm khả năng đoán
nhận ngôn ngữ. Giả sử L(DFA) và L(NFA) lần lượt trỏ lớp các ngôn ngữ đoán
nhận được bởi các DFA và bởi các NFA .Vì theo định nghĩa một DFA cũng là một
NFA, cho nên
L(DFA) ⊆ L(NFA) (*)
Ta hãy xét theo chiều ngược lại.
Định Lý 2.1: Nếu l là một ngôn ngữ được đoán nhận bởi một ÔHK thì cũng có
một ÔHĐ đoán nhận L.
Nói cách khác L(NFA) ⊆ L(DFA) (**)
Hệ Quả 2.1:L(DFA)=L(NFA)
8
Nói cách khác:lớp các ngôn ngữ đoán nhận bởi các ôtômát hữu hạn đơn định và
lớp các ngôn ngữ đoán nhận bởi các ôtômát hữu hạn không đơn định là một.Gọi
đó là các lớp ngôn ngữ chính qui ( viết tắt là lớp NNCQ ) .
Chứng Minh Đinh Lí:
Giả sử M = ( ∑ , Q , ∂, q
o
, F ) là NFA đoán nhận L .
Thành lập DFA M’ = ( ∑, Q’,∂’ , q’
o

] , a)= (q
1 ,
a) (1)
Ta sẽ chứng minh L(M) = L(M’) .
• Trước hết chứng minh rằng : L(M) L(M’) ,tức là chứng minh rằng
nếu
w L(M) thì w L(M’);
Với w = a
1
a
2
a
n
, với n 0 và có một suy dẫn trong M :
q
0
a
1
a
2
a
n

M
q
1
a
2
a
n

a
n

M’

M’
q
n-1
a
n

M’
q’
n
(3)
Ta chứng minh bằng một qui nạp rằng :
Với mọi i , 0 i n , q
i
q’
i
(4)
9
Hình : Các bước chuyển của M và M’

- Cơ sở qui nạp : q
o
q
o
’ bởi định nghĩa q
o

i+1
) ∂( q’
i
, a
i+1
)
Từ đó suy ra q
i
q’
i+1
, tức là (4) cũng đúng với i+1 , kết thúc qui nạp .
Từ (4) đã được chứng minh , suy ra q
n
q’
n
.Nhưng q
n
F , suy ra: q’
n
F’ do
định nghĩa của F’ . Điều đó chứng tỏ w L(M’) .
Bây giờ chứng minh phần ngược lại : L(M’) L(M) , tức là chứng minh rằng
nếu w L(M’) thì w L(M) .
Giả sử có một suy dẫn trong M’ :
q’
o
w
*
M’
q’ với q’ F’

*
, a ∑ và q’
o
xa
*
M’
p’ a
*
M’
q’ , trong đó ∂’( p’, a ) =
q’
Xét một trạng thái bất kì q q’ . Do định nghĩa của thì tồn tại p p’ sao cho q
∂(p , a) . Vậy theo giả thiết qui nạp , tồn tại một suy dẫn trong M q
o
xa
*
M
pa
*
M
q , cho phép kết thúc sự qui nạp .
Trở lại giả thiết w L(M’) , tức là q’
o
w
*
M’
q’ với q’ F’ .
Vì q’ F’ , nên có q q’ sao cho q F .Vận dụng kết quả vừa chứng minh có
ngay q
o

,a) có thể chia ra làm 3 thành phần như sau:
- Đầu tiên là tập các trạng thái có thể đến được từ q
i
mà không cần xử lí một kí
tự nào cả
- Sau đó là các trạng thái có thể đến đựơc khi xử lí kí tự a từ các trạng thái
trong tập các trạng thái trên.
- Cuối cùng theo các cung λ từ các trạng thái kết quả trên để sinh ra tập t(q
i
,a).
Hàm t được định nghĩa trong thuật ngữ của hàm chuyển đổi δ và đường đẫn
trong biểu đồ trạng thái, nó đọc một xâu rỗng. Nút q
j
là bao đóng của trạng thái q
i

nếu có một đường từ q
i
→ q
j
mà đọc một xâu rỗng.
Định nghĩa 1: Bao đóng λ-closure của trạng thái q
i
kí hiệu λ-closure(q
i
),
được định nghĩa đẹ quy như sau
i) Cơ sở: Trạng thái q
i
thuộc λ-closure(q

i
) của các trạng thái và hàm chuyển đổi
của NFA-λ.
Định nghĩa 2 : Hàm biến đổi đầu vào t của một NFA-λ M là một hàm từ Q x
∑ → ρ(Q) bởi :
T(q
i
,a)=U λ-closure(q
i
) với q
j
thuộc bao đóng của λ-closure(q
i
) và δ là
hàm chuyển đổi của M
2 . Giải thuật :
Giải thuật , xây dựng biểu đồ trạng thái của máy quyết định tương đương với
một NFA -λ M. Các nút của DFA, gọi là DM cho quyết định tương đương của M,
là tập các nút của M. Nút bắt đầu của DM là bao đóng λ-closure của bất kỳ nút
nào trong các nút bắt đầu của M. Chìa khoá của giải thuật ở bước 2.1 . Nó sinh ra
các nút của DM. Nếu X là nút của DM thì tập Y được tạo ra chứa toàn bộ các
trạng thái có thể tới được bằng cách sử lí kí tự a từ tất cả các trạng thái trong X.
Trong biểu đồ trạng thái của DM thì quan hệ này được thể hiện bằng một cung từ
X → Y với nhãn a. Nút X đuợc làm quyết định bằng cách tạo ra 1 cung từ nó tơi
mọi kí tự trong bảng chữ. Một nút mới được sinh ra trong bước 2.1.1 đựơc thêm
vào tập Q’ và quá trình tiếp tục cho tới khi mọi nts trong Q’ là quyết định được.
Mã giải :
Đầu vào : cho một NFA-λ M=(Q,∑,δ,q
0
,F) vào hàm dịch t của M.