HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN
==========
BÀI TẬP LỚN: AUTOMAT VÀ NGÔN NGỮ HÌNH THỨC
ĐỀ TÀI: GIAO VÀ HIỆU CỦA 2 DFA
Nhóm thực hiện đề tài:
Đơn vị : Lớp Tin học 44
Giáo viên hướng dẫn:
Hà Nội : 07/2011
1
MỤC LỤC
ĐẶT VẤN ĐỀ
Lý thuyết ngôn ngữ hình thức và automata đóng một vai trò rất quan trọng
trong các cơ sở toán học của tin học. Ngôn ngữ hình thức được sử dụng trong
việc xây dựng các ngôn ngữ lập trình, lý thuyết về các chương trình dịch. Các
ngôn ngữ hình thức tạo thành một công cụ mô tả đối với các mô hình tính toán
cả cho dạng thông tin vào-ra lẫn kiểu thao tác. Lý thuyết ngôn ngữ hình thức,
chính vì thực chất của nó là một lĩnh vực khoa học liên ngành; nhu cầu mô tả
hình thức văn phạm được phát sinh trong nhiều ngành khoa học khác nhau từ
ngôn ngữ học đến sinh vật học.
Như chúng ta đã biết, ngôn ngữ hình thức và chương trình dịch là những
bộ môn phát triển sớm nhất so với các ngành khác trong khoa học máy tính,
khối lượng kiến thức trong các bộ môn này rất đồ sộ. Ở nước ta hiện nay, đã có
nhiều trường đại học cũng đã bắt đầu giảng dạy môn học này cho các sinh viên
ngành Công nghệ thông tin.
Để hiểu rõ hơn về ngôn ngữ hình thức và automata, trong nội dung bài tập
lớn này, chúng em xin trình bày vấn đề về: hiệu và giao của hai DFA. Chúng em
chia đề tài ra làm 3 phần chính :
1. Tìm hiểu về DFA
2. Tìm hiểu về giao và hiệu của 2 DFA
3. Chương trình minh họa.

3

Hình 1 - Sơ đồ chuyển của một DFA

Một điều cần lưu ý, DFA sử dụng mỗi trạng thái của nó để giữ chỉ một
phần của chuỗi số 0 và 1 chứ không phải chứa một số thực sự, vì thế DFA cần
dùng một số hữu hạn trạng thái.
2. Định nghĩa
Một cách hình thức ta định nghĩa ôtômát hữu hạn là bộ gồm năm thành phần
(Q, Σ, δ, q0, F), trong đó :
. Q là tập hợp hữu hạn các trạng thái.
. Σ là bộ chữ cái nhập hữu hạn.
. δ là hàm chuyển ánh xạ từ Q × Σ → Q, tức là δ(q, a) là một trạng thái
được cho bởi phép chuyển từ trạng thái q trên ký hiệu nhập a.
. q0 ∈ Q là trạng thái bắt đầu.
. F ⊆ Q là tập các trạng thái kết thúc.
3. Hàm chuyển trạng thái mở rộng
Để có thể mô tả một cách hình thức hoạt động của một DFA trên chuỗi, ta
mở rộng hàm chuyển δ để áp dụng đối với một trạng thái trên chuỗi hơn là một
trạng thái trên từng ký hiệu. Ta định nghĩa hàm chuyển δ như một ánh xạ từ Q ×
Σ* → Q với ý nghĩa δ(q, w) là trạng thái DFA chuyển đến từ trạng thái q trên
chuỗi w. Một cách hình thức, ta định nghĩa :
1. δ (q, ε) = q
2. δ (q, wa) = δ(δ (q, w), a), với mọi chuỗi w và ký hiệu nhập a.

4
Một số quy ước về ký hiệu :
- Q là tập các trạng thái. Ký hiệu q và p (có hoặc không có chỉ số) là các
trạng thái, q0 là trạng thái bắt đầu.
- Σ là bộ chữ cái nhập. Ký hiệu a, b (có hoặc không có chỉ số) và các chữ

Kết quả :
5
Chú ý :
Trạng thái của giao la kết thúc nếu cả hai trạng thái thành phần đều là trạng thái
kết thúc
2. Hiệu của 2 DFA
2.1 Định nghĩa
L
1
- L
2
= {x | x ∈ L
1
and x ∈ L
2
}
Ví dụ :
– L
1
= {0x | x ∈ {0,1}*} chuỗi bắt đầu bằng 0
– L
2
= {x0 | x ∈ {0,1}*} chuỗi kết thúc bằng 0
– L
1
∩ L
2
= {0x1| x ∈ {0,1}*} chuỗi bắt đầu là 0 và kết thúc khác 0
Chú ý :
L

}
if (txtKiTu1.Text.Length > 2)
{
MessageBox.Show("số kí tự chuyển nhỏ hơn 3");
return;
}
kiemtra1 = true;
pnKetThuc1.Controls.Clear();
pnTrangThai1.Controls.Clear();
pnDFA1.Controls.Clear();
pnDFA2.Controls.Clear();
pnGiao.Controls.Clear();
pnHieu.Controls.Clear();
//tao trang thai ket thuc
soTrangThai1 = Convert.ToInt16(cbTrangThai1.Text);
for (int i = 0; i < soTrangThai1; i++)
{
CheckBox cb = new CheckBox();
cb.Name = "cb1" + i;
cb.Text = " p" + i;
cb.Width = 50;
if (i < 2)
cb.Location = new Point(10, (i +1) * 20);
else
cb.Location = new Point(100, (i - 1) * 20);
pnKetThuc1.Controls.Add(cb);
}
//tao bang chuyen trang thai
kituchuyen1 = txtKiTu1.Text;
for (int i = 0; i <= soTrangThai1; i++)

ComboBox trangthaiden = new ComboBox();
trangthaiden.Name = "trangthai1" + (i-1)+(j-1);
trangthaiden.Items.Add(" ");
for (int k = 0; k < soTrangThai1; k++)
trangthaiden.Items.Add(" q" + k);
trangthaiden.Width = 40;
trangthaiden.SelectedIndex = 0;
trangthaiden.Location = new Point(5, 10);
bangTrangThai.Controls.Add(trangthaiden);
}
}
}
}
}
2.2 Hàm vẽ sơ đồ của DFA vừa tạo
private void btnDFA1_Click(object sender, EventArgs e)
{
try
{
if (kiemtra1 == false)
{
MessageBox.Show("nhập đủ thông tin DFA1");
return;
}
int x = 30, y = 70, w = 40, h = 40, r = 90, a = 10, b = 10;
int yy = y + h / 2;
Pen pen = new Pen(Color.Black, 2);
Brush brush1 = new SolidBrush(Color.Black);
Brush brush2 = new SolidBrush(Color.White);
Font f = new Font("Tahoma", 11);

if (r1[i].ToString() == "True")
sottketthuc1++;
}
ketthuc1.Rows.Add(r1);
#endregion tao bang
#region ve trang thai va xuat phat
//ve cac trang thai
for (int i = 0; i < soTrangThai1; i++)
{
DataRow rr = vitri1.NewRow();
rr["xb"] = x;
rr["xe"] = x + w;
vitri1.Rows.Add(rr);
if (Convert.ToBoolean(ketthuc1.Rows[0][i]) == true)
{
g1.FillEllipse(new SolidBrush(Color.Red), x, y, w, h);
g1.DrawString("q" + i, f, brush2, x + a, y + b);
}
else
{
g1.DrawEllipse(pen, x, y, w, h);
g1.DrawString("q" + i, f, brush1, x + a, y + b);
}
x += r + w;
}
//ve duong bat dau
pen.Width = 3;
pen.EndCap = LineCap.ArrowAnchor;
g1.DrawLine(pen, new Point(5, yy), new Point(30, yy));
#endregion ve trang thai va xuat phat

- q) * sll);
int n = Convert.ToInt16(arr1.Rows[0]
[q.ToString()]);
if (n == 0)
{
g1.DrawCurve(pen, new Point[] { pb, pc,
pe });
g1.DrawString(c.ToString(), f, brush1, pc.X
- 8, pc.Y - 17);
}
else
{
g1.DrawString("," + c.ToString() + " ", f,
brush1, pc.X - 10 + 10 * n, pc.Y - 17);
}
arr1.Rows[0][q.ToString()] = n + 1;
}
else if (i == q)
{
Point pb = new
Point(Convert.ToInt16(vitri1.Rows[i]["xe"]) - 5, yy - 17);
Point pe = new
Point(Convert.ToInt16(vitri1.Rows[i]["xb"]) + 5, yy - 17);
Point pc1 = new Point((pb.X + pe.X) / 2 + 5, yy
- 40);
Point pc2 = new Point((pb.X + pe.X) / 2 - 5, yy
- 40);
if (flag == 0)
{
g1.DrawCurve(pen, new Point[] { pb, pc1,

{
g1.DrawString("," + c.ToString() + " ", f,
brush1, pc.X - 10 + (10 * n), pc.Y - 1);
}
arr2.Rows[0][q.ToString()] = n + 1;
}
//}
}
}
#endregion ve cung
}
catch
{
MessageBox.Show("nhập đủ thông tin DFA1");
}
}
2.3 Hàm tạo giao
2.4 Hàm tạo hiệu
TÀI LIỆU THAM KHẢO
1. Giáo trình AUTOMATA ngôn ngữ hình thức và nguyên lý chương trình
dịch – PGS.TS Nguyễn Văn Xuất ( Học viện Kỹ thuật Quân sự).
12
2. Slide bài giảng của thầy Hà Chí Trung ( Bộ môn Khoa học máy tính –
Khoa Công nghệ thông tin - HVKTQS)
3. Lý thuyết automata và ngôn ngữ hình thức – Nguyễn Gia Định ( Đại Học
Huế)
4. Tài liệu tham khảo khác
13