1
TRƯỜNG ĐẠI HỌC ĐỒNG THÁP
KHOA SƯ PHẠM TOÁN - TIN
BÀI GiẢNG MÔN HỌC
ÔTÔMÁT VÀ
NGÔN NGỮ HÌNH THỨC
Biên soạn : Ths.Nguyễn Thị Thùy Linh
E-mail : nttlinh@dthu.edu.vn
1
Giới thiệu
•Lý thuyết ngôn ngữ hình thức và ôtômát đặt nền
tảng mạnh mẽ trên lý thuyết tập hợp, hàm, ánh
xạ, quan hệ và lý thuyết đồ thị.
•Kỹ thuật mô phỏng các quá trình làm việc tương
tự trên máy tính.
2
Mục tiêu
•Nghiên cứu hai lý thuyết cơ sở trong lĩnh vực khoa học máy tính:
–Lý thuyết về ôtômát: lý thuyết cơ bản cho việc nghiên cứu
các mô hình tính toán tự động để làm tiền đề cho sự phát
triển dạng máy tính số như hiện nay.
–Lý thuyết về ngôn ngữ hình thức (Formal languages): nền
tảng cho việc thấu hiểu khái niệm về ngôn ngữ nói chung (cả
ngôn ngữ lập trình lẫn ngôn ngữ tự nhiên), và các vấn đề cơ
bản về ngôn ngữ như cách xây dựng văn phạm sinh ra ngôn
ngữ (xây dựng văn phạm cho ngôn ngữ lập trình, cho quá
trình phân tích cú pháp), dịch từ ngôn ngữ lập trình cấp cao
sang ngôn ngữ máy…
–Hai khía cạnh này có mối liên quan mật thiết với nhau trong
ứng dụng của khoa học máy tính.
3
NỘI DUNG MÔN HỌC
Chương 1: Kiến thức cơ sở
Chương 2: Ngôn ngữ, văn phạm và ôtômát.
Chương 3: văn phạm chính quy và Ôtômát hữu hạn
Chương 4: Văn phạm phi ngữ cảnh và Ôtômát đẩy xuống.
Chương 5: Máy Turing.
4
2
Đánh giá môn học
•Thi tự luận cuối kỳ: hệ số 0.7
–Hnh thức: Bài tập
–Thời gian 90 phút, được sử dụng tài liệu
•Kiểm tra thường kỳ: hệ số 0.3
–Kiểm tra bài tập tại lớp (50%)
–Tự học, tự nghiên cứu (50%)
5
Chương 1: Kiến thức cơ sở
Kiến thức nền (nhắc lại)
1. Lý thuyết tập hợp.
2. Các quan hệ.
3. Đồ thị và cây.
6
Các ký pháp về tập hợp
7
Các ký pháp về tập hợp (tt)
•x là phần tử của A, ta viết x A.
•x không là phần tử của A, ta viết x A.
•Nếu mọi phần tử của A đều là phần tử của B,
ta viết A B.
•A = B  A B và B A.
8
3
Các phép toán trên các tập hợp
•A B = {x| x A hoặc x B}
•A B = {x| x A và x B}
•A – B = {x| x A và x B}
•A x B, tích Đềcác của A và B, là tập hợp có thứ tự
(a, b) sao cho a A và b B
•2A, tập lũy thừa của A, đó là tập hợp mọi tập con
của A.
9
Các phép toán trên các tập hợp (tt)
•Thí dụ : Cho A = {1, 2} và B = {2, 3}
•A B = {1, 2, 3}
•A B = {2}
•A – B = {1}
•A x B = {(1, 2), (1, 3), (2, 2), (2, 3)}
•2A = {, {1}, {2}, {1, 2}}
•Lưu ý: Nếu A và B lần lượt có n và m phần tử thì
A x B có n x m phần tử
2A có 2n phần tử
2B có 2m phần tử 10
Các quan hệ
•ĐN: Cho 2 tập hợp A và B. Một quan hệ
giữa A và B, ký hiệu R, là một tập các cặp
(a, b) với a A và b B. Viết là R =
{(a,b) | a A, b B }
•Trường hợp A = B ta nói đó là quan hệ trên
A.
•Nếu R là một quan hệ và (a, b) là một cặp
trong R thì ta thường viết aRb.
11
Các tính chất của quan hệ
Ta nói một quan hệ R trên tập A là:
• Phản xạ nếu aRa là đúng đối với a A.
• Bất phản xạ nếu aRa là sai đối với a A.
• Truyền ứng (Bắc cầu) nếu aRb và bRc kéo
theo aRc
• Đối xứng nếu aRb kéo theo bRa.
• Phản đối xứng nếu aRb kéo theo bRa sai.
12
4
Các quan hệ tương đương
•Một quan hệ R trên tập A được gọi là quan hệ tương
đương nếu nó là quan hệ phản xạ, đối xứng và bắc
cầu.
•Nếu R là quan hệ tương đương trên tập A thì R phân
hoạch A thành các lớp tương đương không rỗng và
rời nhau. Điều đó có nghĩa là:
A = A1 A2 … trong đó với mọi i và j mà i j
thì:
1. Ai Aj =
2. Với mọi a và b cùng thuộc Ai, aRb là đúng.
3. Với mọi a Ai và mọi b Aj, aRb là sai.
13
Các quan hệ tương đương (tt)
•Thí dụ 1.4: Cho tập số tự nhiên N và R là một quan hệ
tương đương trên tập hợp N. Vậy R sẽ phân hoạch N ra
thành các lớp tương đương không rỗng và rời nhau. Đó
là các lớp nào?
•Cách 1: nRm khi m và n có cùng tính chất chia hết cho 2.
R sẽ phân hoạch N thành hai lớp tương đương là tập các
số chẵn và tập các số lẻ.
•Cách 2: nRm khi m và n có cùng tính chất là số nguyên
tố hoặc ngược lại. R sẽ phân hoạch N thành hai lớp
tương đương là tập hợp số nguyên tố và tập hợp không
phải số nguyên tố.
14
Bao đóng của quan hệ
•Cho một tập W những tính chất nào đó của các
quan hệ.
•Ta gọi bao đóng W của một quan hệ R là quan hệ
bé nhất R’ bao gồm R và các tính chất trong W.
•Bao đóng bắc cầu của R, ký hiệu R+, được định
nghĩa như sau:
1. Nếu (a, b) thuộc R, thì (a, b) thuộc R+.
2. Nếu (a, b) thuộc R+, và (b, c) thuộc R thì (a, c)
R+.
3. Không còn cặp nào khác trong R+ ngoài các cặp
thu được từ (1) và (2). 15
Bao đóng của quan hệ (tt)
Người ta còn định nghĩa một cách khác tập R+
nhờ khái niệm lũy thừa quan hệ Ri. Ri được định
nghĩa (một cách đệ quy) như sau:
1. aR1b khi và chỉ khi aRb.
2. aRib khi và chỉ khi tồn tại c sao cho aRc và
cRi-1b với i>1.
Tập R+ được định nghĩa là: R+ = R1 R2 …
aR0b khi và chỉ khi a = b.
16
5
Bao đóng của quan hệ (tt)
•Bao đóng phản xạ và bắc cầu của R, ký hiệu
là R*, được định nghĩa: R* = R0 R+.
•Ví dụ: Cho R = {(1, 2), (2, 2), (2, 3)} là một
quan hệ trên tập hợp {1, 2, 3}. Thế thì:
•R+ = {(1, 2), (2, 2), (2, 3), (1, 3)}.
•R* = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3,
3)}.
17
Bài tập
•Cho R = { (1,2), (2,3), (2,4)} là qh
trên tập {1,2,3,4}. Tm R+ và R*
•Cho R = {(a,b),(b,c),(c,a)} là 1 quan
hệ trên {a,b,c}. Tm R*
18
Đồ thị
19
Một đồ thị, ký hiệu G = (V, E), gồm
một tập hữu hạn V các đỉnh và một
tập E các cặp nút gọi là các cạnh.
Một đường đi trên đồ thị là một dãy
các nút v1, v2, … vk, k 1, sao cho có
một cạnh (vi, vi+1) đối với mỗi i, 1 i
k. Độ dài của đường đi là k-1. Nếu
v1 = vk thì đường được gọi là chu
trình.
Đồ thị (tt)
20
1 2
4
5
3
Ví dụ : Hãy vẽ đồ thị G(V,E)
V = {1, 2, 3, 4, 5} và
E = {(n, m)| n + m = 4 hay n + m = 7}