Tiểu luận NNHT và Automata
Mục lục:
Phần mở đầu
 Mục đích của việc giải quyết đồ án được giao:
Qua việc viết chương trình kiểm tra 2 DFA có tương đương nhau không
giúp chúng ta trả lời cho câu hỏi 2 DFA khác nhau có biểu diễn cùng một
ngôn ngữ chính quy không? Vì khi 2 DFA cùng biểu diễn một ngôn ngữ thì ta
nói 2 DFA là tương đương. Từ vấn đề này, chúng ta sẽ có hướng mở rộng cho
việc cực tiểu hóa DFA: tức là xây dựng DFA có tối thiểu số trạng thái tương
đương với một DFA cho trước.
Đồng thời, việc thực hiện đồ án giúp ta củng cố một phần lý thuyết môn
học Automata và ngôn ngữ hình thức, nâng cao kỹ năng lập trình hướng đối
tượng cho bản thân.
 Các vấn đề cần giải quyết với đề tài “kiểm tra 2 DFA tương đương”:
• Thực hiện mọi thao tác nhập và xử lý dữ liệu trên form chương trình.
• Từ số trạng thái và kí tự nhập vào ở Textbox cho hiển thị bảng
chuyển trạng thái trên Panel.
Page 1
Tiểu luận NNHT và Automata
• Hiển thị đồ thị chuyển trạng thái của DFA vừa nhập.
• Lưu kết quả ở dạng ma trận {0,1} sau đó sử dụng 2 ma trận đã lưu
để kiểm tra tính tương đương của 2 ma trận DFA đó.
Phần 1: Cơ sở lý thuyết
I.1.Giới thiệu về automata hữu hạn (FA):

Automata là một mô hình toán học hay máy trừu tượng có cơ cấu và hoạt động đơn
giản nhưng có khả năng đoán nhận ngôn ngữ.
 Một finite automata (FA) là một mô hình tính toán 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;
 Một FA làm việc theo thời gian rời rạc (time steps);

0
.
• Bảng chuyển – bảng có kích cỡ |Q| × |Σ|, trong đó dòng i cột j của bảng là
hoặc bỏ trống.
• Ví dụ DFA: Cho automata A = ({q
0
; q
1
; q
2
}; {0, 1},δ, q
0
, {q
1
}) với hàm
chuyển được cho dưới dạng bảng chuyển và đồ thị chuyển như sau:
Ngôn ngữ được đoán nhận bởi automat A:
L = {1*0*01x : x ∈ {0, 1}*}
• Mở rộng của hàm chuyển:
Page 3
( )
,
i j
q a
δ
Tiểu luận NNHT và Automata
Mở rộng của một ánh xạ δ là δ’ biến đổi trạng thái, xâu sang trạng thái.
Có nghĩa là:
1. δ’(q, e) = q;
2. δ’(q, wa) = δ’(δ’(q,w), a) với " w, a.

0
;
C:= ký hiệu tiếp theo của chuỗi;
while (C < > ε) do {
S:= δ(S, C);
C:= ký hiệu tiếp theo của chuỗi;
};
if (S in F) return (true);
else return (false);
I.3.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.
Page 4
Tiểu luận NNHT và Automata
Lưu ý, chúng ta không yêu cầu δ
*
(p, 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
Page 5
Tiểu luận NNHT và Automata
không được sử dụng. Ban đầu, khô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ạng thá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ảng đánh dấu các cặp trạng thái phân biệt cho Ví dụ
I.4.Sự tương đương của các DFA:
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.

Page 6
Tiểu luận NNHT và Automata
I.4.1.Dựa vào bảng đánh dấu sự tương đương của các trạng thái:
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 M
1
và M
2
. Xét DFA mới là hợp của hai DFA M
1
và M
2

∩ L
2
từ các DFA thừa nhận L
1
và L
2
.
Giả sử M
1
= (Q
1
, Σ
1
, δ
1
, q
01
, F
1
) và M
2
= (Q
2
, Σ
2
, δ
2
, q
02
, F

1
và M
2
cùng đoán nhận xâu vào. Như vậy, M được xây dựng như sau:
M=(Q
1
× Q
2
, Σ
1
∪ Σ
2
, δ, (q
01
, q
02
), F
1
× F
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(M1) ∩ L(M2).
Thật vậy, δ
*
((q
01
, q
02
), w) = (δ

chấp
nhận w và M
2
chấp nhận w. Vậy chấp nhận L(M
1
) ∪ L(M
2
)
Ví dụ: Cho L
1
là ngôn ngữ chính quy có chứa ít nhất một kí hiệu 0 được thừa
nhận bởi DFA M
1
(a) và L
2
là ngôn ngữ chính quy có ít nhất một kí hiệu 1 được
thừa nhận bởi DFA M
2
(b). Chúng ta chỉ ra DFA M (c) thừa nhận ngôn ngữ giao
của L
1
và L
2
.
Page 8
Tiểu luận NNHT và Automata
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.


Page 9
Tiểu luận NNHT và Automata
DFA biểu diễn
1
L
A
DFA biểu diễn
2
L
C D
DFA biểu diễn
2
L

E
Page
10

B

E

D

C
Tiểu luận NNHT và Automata
DFA biểu diễn
1
L
∩

B,D

A,C
Tiểu luận NNHT và Automata
Phần II: Chương trình
II.1.Cấu trúc chương trình:
Chương trình được viết bằng ngôn ngữ c# trên ứng dụng WindowsForm của
chương trình visual studio 2008
Chương trình được viết trên 3 form(class):
 Form Giao_Dien.cs: dùng để giới thiệu tên đồ án môn học, tên giáo viên hướng
dẫn và các học viên thực hiện đề tài. Đồng thời có tab Menu để lựa chọn các
chức năng người dùng muốn thao tác.
 Form Tao_DFA: đây là giao diện để hiển thị chương trình chính là tạo các
DFA.
 Form DrawingDFA: giao diện dùng để thể hiện đồ thị chuyển trạng thái của
DFA.
II.1.1.Cấu trúc của Form Giao_Dien:
Form Giao_Dien gồm màn hình hiển thị thông tin liên quan tới đề tài như tên
đề tài, giáo viên hướng dẫn, học viên thực hiện. Ngoài ra còn có menustrip Menu
gồm các chỉ mục: Nhập DFA1, Nhập DFA2, Kiểm tra, Thoát.
Ứng với chỉ mục Nhập DFA1 và Nhập DFA2, ta sẽ mở form tiếp theo để thực
hiện thao tác nhập từng DFA vào.
Với chỉ mục Kiểm tra, ta sẽ có được kết quả so sánh cho 2 DFA vừa nhập xem
chúng có tương đương hay không.
Chỉ mục Thoát dùng để thoát khỏi chương trình.
II.1.2.Cấu trúc của Form Tao_DFA:
Gồm 2 textbox Các chữ cái nhập vào và Số trạng thái, 4 button Tao DFA, Lưu,
Đồ thị, Thoát, 2 panel Trạng thái kết thúc và Sơ đồ chuyển dịch trạng thái.
Page
12

true
Page
14
Bắt đầu
Nhập DFA1 và DFA2
Gán bảng chuyển trạng thái
bằng ma trận {0,1}
So sánh hàng đầu của 2 ma
trận trên
Kết quả
Tiểu luận NNHT và Automata
II.3.Giao diện chính của chương trình:
II.3.1.Màn hình giao diện Menu:
Hình 1.1: Màn hình giao diện khởi động
Page
15
Tiểu luận NNHT và Automata
Hình 1.2: Màn hình giao diện Menu
II.3.2.Màn hình giao diện tạo DFA:
Hình 2: Màn hình nhập DFA
II.3.3.Màn hình giao diện đồ thị DFA
Page
16
Tiểu luận NNHT và Automata
Hình 3: Màn hình đồ thị chuyển trạng thái
II.3.4.Màn hình giao diện kết quả:
Page
17
Tiểu luận NNHT và Automata
Hình 4.1 và 4.2: MÀn hình kết quả so sánh 2 DFA

//Tao DFA
public void btnTaoDFA_Click(object sender, EventArgs e)
{
if(txtSotrangthai.Text==""||txtNhapchucai.Text=="")
{
MessageBox.Show("Vui lòng nhập chữ cái và số trạng thái!");
return;
}
lblNote.Visible = true;
btnDoThiChuyen.Visible=true;
So_TrangThai_Nhap = Convert.ToInt32(txtSotrangthai.Text);
pnlTrangthai.Controls.Clear();
pnlDichchuyen.Controls.Clear();
for (int i = 0; i < So_TrangThai_Nhap; i++)
{
CheckBox chkStatus = new CheckBox();
chkStatus.Name = "chkStatus" + i;
chkStatus.Text = "Q" + i;
chkStatus.Width = 60;
chkStatus.Location = new Point(20, (i + 1) * 30);
pnlTrangthai.Controls.Add(chkStatus);
}
strChuCai = txtNhapchucai.Text;
for (int i = 0; i <= So_TrangThai_Nhap;i++ )
{
for(int j=0;j<=strChuCai.Length;j++)
{
if (!(i == 0 && j == 0))
{
GroupBox grpMatrixLocal = new GroupBox();

for (int k = 0; k < So_TrangThai_Nhap; k++)
cboStatus.Items.Add("Q" + k);
cboStatus.Width = 50;
cboStatus.SelectedIndex = 0;
cboStatus.Location = new Point(20, 20);
grpMatrixLocal.Controls.Add(cboStatus);
}
}
}
}
}
private void txtNhapchucai_TextChanged(object sender, EventArgs e)
{
string strChuCai = txtNhapchucai.Text;
string strChuCaiNew = "";
foreach (char c in strChuCai)
{
if (!strChuCaiNew.Contains(c.ToString()))
strChuCaiNew += c.ToString();
}
txtNhapchucai.Text = strChuCaiNew;
}
private void btnLuu_Click(object sender, EventArgs e)
{
this.SoTrangThai = int.Parse(this.txtSotrangthai.Text);
if (this.txtNhapchucai.Text.Length != 0)
{
this.ChuCai = new char[this.txtSotrangthai.Text.Length];
ChuCai = this.txtSotrangthai.Text.ToCharArray();
//int tmp = 0;

}
}
}
}
}
private void btnThoat_Click(object sender, EventArgs e)
{
if (MessageBox.Show("Bạn có muốn thoát hay không ?", "Thông báo",
MessageBoxButtons.YesNo) == DialogResult.Yes)
{
this.Dispose();
}
}
private void btnDoThiChuyen_Click(object sender, EventArgs e)
{
DataTable DT_diagram = new DataTable();
foreach (char c in strChuCai)
DT_diagram.Columns.Add(c.ToString());
for (int i = 0; i < So_TrangThai_Nhap; i++)
{
DataRow row = DT_diagram.NewRow();
for (int j = 0; j < strChuCai.Length; j++)
{
ComboBox cboStatus =
(ComboBox)this.Controls.Find("cboStatus" + i + "_" + j, true)[0];
if (cboStatus.Text == "")
row[j] = Convert.ToInt32(null);
else
row[j] = cboStatus.Text.Substring(1);
}

“Phần III: Tài liệu tham khảo
1.Tài liệu slide bài giảng “Ngôn ngữ hình thức và Automata” của thầy Hà Chí Trung
- Bộ môn Khoa học máy tính - Khoa Công nghệ thông tin – Học viện Kỹ thuật quân
sự.
2.Code nguồn trên website http://google.com.vn/
3.Tài liệu Automata của ĐHBK Đà Nẵng.
Page
23