Báo cáo bài tập lớn Automata Đề bài : 2 DFA tương đương
MỤC LỤC
I.ÔTÔMAT HỮU HẠN VÀ AUTOMATA HỮU HẠN ĐƠN ĐỊNH
1.1. Mở đầu…………………………………………………………………………………2
1.2. Định nghĩa……………………………………………………………………………3
1.3. Phương pháp biểu diễn ôtômat hữu hạn đơn định……………4
1.4. Định nghĩa ngôn ngữ đoán nhận bởi FA……………………………7
II.HAI DFA TƯƠNG ĐƯƠNG
2.1. Định nghĩa………………………………………………………………………………….9
2.2.Các cách xác định 2 DFA tương đương …………………………………….10
2.2.1.Cùng sinh ra một ngôn ngữ …………………………………………….10
2.2.2.Dựa vào bảng đánh dấu các trạng thai tương đương……15
a.Sự tương đương của các trạng thái………………………… 15
b.Sự tương đương của 2 DFA Dựa vào bảng đánh dấu sự
tương đương của các trạng thái………………………………………17
1
Báo cáo bài tập lớn Automata Đề bài : 2 DFA tương đương
I.ÔTÔMAT HỮU HẠN VÀ AUTOMATA HỮU HẠN ĐƠN ĐỊNH
1.1. Mở đầu:
Một ôtômat hữu hạn là một mô hình tính toán thực sự hữu
hạn. Mọi cái liên quan đến nó đều có kích thước hữu hạn cố định và
không thể mở rộng trong suốt quá trình tính toán. Các loại ôtômat
khác được nghiên cứu sau này có ít nhất một bộ nhớ vô hạn về tiềm
năng. Sự phân biệt giữa các loại ôtômat khác nhau chủ yếu dựa trên
việc thông tin có thể được đưa vào bộ nhớ như thế nào.
Một ôtômat hữu hạn làm việc theo thời gian rời rạc như tất cả
các mô hình tính toán chủ yếu. Như vậy, ta có thể nói về thời điểm “kế
tiếp” khi “đặc tả” hoạtđộng của một ôtômat hữu hạn.
Trường hợp đơn giản nhất là thiết bị không có bộ nhớ mà ở mỗi
thời điểm, thông tin ra chỉ phụ thuộc vào thông tin vào lúc đó. Các
thiết bị như vậy là mô hình của các mạch tổ hợp.

− Σ là một bảng chữ, được gọi là bảng chữ vào;
− Σ là một bảng chữ, được gọi là bảng chữ vào;
− δ: D → Q, trong đó D ⊂ Q x Σ, được gọi là ánh xạ chuyển;
− q
0
∈ Q, được gọi là trạng thái đầu;
− F ⊂ Q, được gọi là tập các trạng thái kết thúc.
Trong trường hợp D = Q x Σ, ta nói A là đầy đủ. Về sau ta sẽ thấy
rằng mọi ôtômat hữu hạn đều đưa về được ôtômat hữu hạn đầy đủ
tương đương.
Hoạt động của ôtômat hữu hạn đơn định A = <Q, Σ, δ, q0, F> khi
cho xâu vào ω=a
1
a
2
… a
n
có thể được mô tả như sau:
Khi bắt đầu làm việc, máy ở trạng thái đầu q
0
và đầu đọc đang
nhìn vào ô có ký hiệu a
1
. Tiếp theo máy chuyển từ trạng thái q
0
dưới tác
động của ký hiệu vào a
1
về trạng thái mới δ(q
0

n-1
,a
n
)=q
n
∉
F hoặc tồn tại chỉ số j (j≤n) sao cho δ(q
j-1
,a
j
) không xác định, ta nói rằng
A không đoán nhận ω.
1.3. Phương pháp biểu diễn ôtômat hữu hạn đơn định:
Ánh xạ chuyển là một bộ phận quan trọng của một ôtômat hữu
hạn đơn định.Nó có thể cho dưới dạng bảng chuyển hoặc cho dưới
dạng đồ thị.
1) Phương pháp cho bảng chuyển:

trong đó dòng i cột j của bảng là ô trống nếu ( q
i
,a
j
) ∉ D, tức là
δ(q
i
,a
j
) không xác định.
4
Báo cáo bài tập lớn Automata Đề bài : 2 DFA tương đương

Ta có thể mô tả quá trình đoán nhận xâu vào của ôtômat hữu hạn
đơn định đầy đủ A bằng thuật toán mô phỏng sau:
Đầu vào:
− Một xâu ω
− Một ôtômat hữu hạn đơn định đầy đủ A với trạng thái đầu q
0
và tập
trạng thái kết thúc là F.
Đầu ra:
− “True” nếu A đoán nhận xâu ω.
− “False” nếu A không đoán nhận xâu ω.
Thuật toán:
Begin
S:=q
0
;
C:=ký hiệu tiếp theo;
While ( C < > Ø ) do
begin
S:=δ(S, C);
C:=ký hiệu tiếp theo;
end;
if ( S ∈ F ) return True
else return False;
7
Báo cáo bài tập lớn Automata Đề bài : 2 DFA tương đương
End.
1.4. Định nghĩa ngôn ngữ đoán nhận bởi DFA:
Cho ôtômat hữu hạn đơn định A = <Q, Σ, δ, q0, F>, ω ∈ Σ và L là
một ngôn ngữ trên Σ. Ta nói:

i
( 1≤ i ≤n ) và q
n
∈ F. Như vậy, L(A) là tập hợp tất cả
các đường đi từ q
0
đến các đỉnh kết thúc.
8
Báo cáo bài tập lớn Automata Đề bài : 2 DFA tương đương

II.HAI DFA TƯƠNG ĐƯƠNG :
2.1. Định nghĩa: Hai ôtômat hữu hạn đơn định A và A’ được gọi là
tương đương nếu L( A )=L( A’ ).
Ví dụ: Cho ôtômat hữu hạn đơn định:
A = <{q0, q1, q2, q3, q4}, {0, 1}, δ, q0, {q1, q2, q4}>,
trong đó δ(q0,0)=q0, δ(q0,1)=q1, δ(q1,0)=q3, δ(q1,1)=q2, δ(q2,0)=q2,
δ(q2,1)=q2, δ(q3,1)=q3, δ(q4,0)=q2, δ(q4,1)=q3.
Đồ thị chuyển của A là:
Trước hết, ta nhận thấy rằng không có đường đi từ q0 đến đỉnh
kết thúc q4, do đó ôtômat A tương đương với ôtômat A’ sau:
A’ = <{q0, q1, q2}, {0, 1}, δ, q0, {q1, q2}>,
trong đó δ(q0,0)=q0, δ(q0,1)=q1, δ(q1,1)=q2, δ(q2,0)=q2, δ(q2,1)=q2.
Đồ thị chuyển của A’ là:
9
Báo cáo bài tập lớn Automata Đề bài : 2 DFA tương đương
Các đường đi từ q0 đến đỉnh kết thúc q
1
ứng với các xâu 0
n
1, n≥0.

1
L

=
2
L

1
L
∩
2
L

=
1
L
∩
2
L
= L(M) = ∅.
DFA rỗng: Nếu không tồn tại một đường đi từ trạng thái đầu
đến một trong các trạng thái cuối thì là rỗng, ngược lại thì không
rỗng.
* T ính đóng của lớp ngôn ngữ dưới phép giao:
Định lý: Nếu L
1
và L
2
là các ngôn ngữ chính quy thì L
1

= (Q
2
, Σ
2
, δ
2
, q
02
, F
2
) là các
DFA thừa nhận tương ứng L
1
và L
2
. Chúng ta sẽ xây dựng DFA M
bắt chước thực hiện đồng thời A
1
và A
2
. Mỗi trạng thái của M sẽ là
một cặp trạng thái: một trạng thái của A
1
và một trạng thái của A
2
.
Bảng chữ của M sẽ là hợp của các bảng chữ của A
1
và A
2

Trong đó, δ((p, q), a) = (δ1(p, a), δ2(q, a)), với p ∈ Q1, q∈ Q2, a
∈ Σ1 ∪ Σ2.
Dễ dàng nhận thấy rằng L(M) = L(A1) ∩ L(A2).
Thật vậy, δ
*
((q
01
, q
02
), w) = (δ
1
*
(q
01
, w), δ
2
*
(q
02
, w)), như thế M
chỉ chấp nhận w khi δ
1
*
(q
01
, w) ∈ F
1
và δ
2
*

.
11
Báo cáo bài tập lớn Automata Đề bài : 2 DFA tương đương
DFA giao của hai DFA
Chúng ta dễ dàng nhận thấy rằng, DFA thừa nhận ngôn ngữ
gồm it nhất một kí hiệu 0 và ít nhất một kí hiệu 1.
DFA biểu diễn
1
L
A
12

B
Báo cáo bài tập lớn Automata Đề bài : 2 DFA tương đương
DFA biểu diễn
2
L
C D
DFA biểu diễn
2
L

E

13

E

D



B,E

B,C

B,D

A,C
Báo cáo bài tập lớn Automata Đề bài : 2 DFA tương đương
2.2.2.Dựa vào bảng đánh dấu các trạng thai tương đương:
a.Sự tương đương của các trạng thái :
Mục đích của chúng ta là xác định xem hai trạng thái khác
nhau p và q có thể thay thế bởi một trạng thái duy nhất mà có chức
năng như p và q.
Chúng ta nói rằng, hai trạng thái p và q là tương đương nếu:
với mọi xâu w, δ
*
(p, w) cho kết quả là trạng thái kết thúc và δ
*
(q,
w) cho kết quả cũng là trạng thái kết thúc hoặc δ
*
(p, w) cho kết
quả là trạng thái không kết thúc và δ
*
(q, w) cho kết quả cũng là
trạng thái không kết thúc.
Lưu ý, chúng ta không yêu cầu δ
*
(p, w) và δ

*
(p, aw) và δ
*
(q, aw) cho cùng kết quả với δ
*
(r, w) và
δ
*
(s, w), nghĩa là {p, q} cũng là cặp trạng thái phân biệt bởi xâu aw.
Ví dụ: Xây dựng bảng đánh dấu của DFA trong hình vẽ
Trong bảng đánh dấu các trạng thái phân biệt, các cặp trạng
thái phân biệt được đánh dấu X, các cặp trạng thái tương đương
được để trống, các ô bôi đen không được sử dụng. Ban đầu, không
16
Báo cáo bài tập lớn Automata Đề bài : 2 DFA tương đương
có cặp nào bị đánh dấu. Chúng ta thực hiện việc đánh dấu theo
thuật toán đã trình bày ở trên.
Trước hết, các cặp trạng thái gồm có một trạng kết thúc và một
trạngthái không kết thúc được đánh dấu. Thực hiện bước 2 của
thuật toán,chúng ta không tìm thấy thêm cặp trạng thái phân biệt
nào nữa :
b.Sự tương đương của 2 DFA Dựa vào bảng đánh dấu sự
tương đương của các trạng thái:
Ví dụ: Xét hai DFA, hai DFA này cùng đoán nhận ngôn ngữ
gồm các xâu trên bảng chữ {0, 1} kết thúc bởi kí hiệu 0.
17
Báo cáo bài tập lớn Automata Đề bài : 2 DFA tương đương
Chúng ta dễ dàng xác định được sự tương đương của hai DFA.
Thật vậy, giả sử có hai DFA A
1