Bài giảng Ôtômát và ngôn ngữ hình thức - Chương 1: Kiến thức cơ sở

TRƯỜNG ĐẠI HỌC ĐỒNG THÁP

KHOA SƯ PHẠM TOÁN - TIN

Giới thiệu

BÀI GiẢNG MÔN HỌC

• 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ị.

ÔTÔMÁT VÀ

NGÔN NGỮ HÌNH THỨC

• Kỹ thuật mô phỏng các quá trình làm việc tương

tự trên máy tính.

Biên soạn : Ths.Nguyễn Thị Thùy Linh

E-mail

: [email protected].vn

1

2

NỘI DUNG MÔN HỌC

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…

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.

– 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

4

1

Đánh giá môn học

Chương 1: Kiến thức cơ sở

• Thi tự luận cuối kỳ: hệ số 0.7

– Hꢀnh thức: Bài tập

Kiến thức nền (nhắc lại)

1. Lý thuyết tập hợp.

– Thời gian 90 phút, được sử dụng tài liệu

2. Các quan hệ.

• 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%)

3. Đồ thị và cây.

5

6

Các ký pháp về tập hợp

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.

7

8

2

Các phép toán trên các tập hợp

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 = {x| x  A hoặc x  B}

• A  B = {x| x  A và x  B}

• A – B = {x| x  A và x  B}

• A  B = {2}

• A – B = {1}

• A x B = {(1, 2), (1, 3), (2, 2), (2, 3)}

• 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

• 2^A= {, {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ử

• 2^A, tập lũy thừa của A, đó là tập hợp mọi tập con

của A.

2^Acó 2ⁿphần tử

2^Bcó 2^mphần tử

9

10

Các tính chất của quan hệ

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 }

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.

• 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.

• Phản đối xứng nếu aRb kéo theo bRa sai.

11

12

3

Các quan hệ tương đương

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?

•

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 = A₁ A₂ … trong đó với mọi i và j mà i  j

thì:

1. A_i A_j= 

2. Với mọi a và b cùng thuộc A_i, aRb là đúng.

3. Với mọi a  A_ivà mọi b  A_j, aRb là sai.

• 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ố.

13

14

Bao đóng của quan hệ

Bao đóng của quan hệ (tt)

•

Cho một tập W những tính chất nào đó của các

quan hệ.

 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ệ Rⁱ. Rⁱđược định

nghĩa (một cách đệ quy) như sau:

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. aR¹b khi và chỉ khi aRb.

2. aRⁱb khi và chỉ khi tồn tại c sao cho aRc và

cR^i-1b với i>1.

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⁺.

 Tập R⁺được định nghĩa là: R⁺= R¹ R² …

 aR⁰b khi và chỉ khi a = b.

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

16

4

Bao đóng của quan hệ (tt)

Bài tập

• Bao đóng phản xạ và bắc cầu của R, ký hiệu

là R^*, được định nghĩa: R^*= R⁰ 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ì:

• 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*

•

R⁺= {(1, 2), (2, 2), (2, 3), (1, 3)}.

R^*= {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3,

3)}.

17

18

Đồ thị (tt)

Đồ thị

 Ví dụ : Hãy vẽ đồ thị G(V,E)

V = {1, 2, 3, 4, 5} và

 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.

E = {(n, m)| n + m = 4 hay n + m = 7}

1

2

 Một đường đi trên đồ thị là một dãy

các nút v₁, v₂, … v_k, k  1, sao cho có

một cạnh (v_i, v_i+1) đối với mỗi i, 1  i

 k. Độ dài của đường đi là k-1. Nếu

v₁= v_kthì đường được gọi là chu

3

5

4

19

20

trình.

5

Đồ thị có hướng

Các khái niệm khác

• Liên thông.

 Một đồ thị định hướng, ký hiệu G = (V, E), gồm

một tập hữu hạn V các nút và một tập E các cặp

nút có thứ tự gọi là cung. Ta ký hiệu một cung từ v

tới w bởi v  w.

• Không liên thông.

• Chu trình.

• Đỉnh cô lập

• Đỉnh treo

1

• Khuyên

2

3

4

• Bậc của 1 đỉnh

21

22

Đồ thị có hướng (tt)

Cây

 Một cây (hay nói rõ hơn là cây định hướng có thứ

tự) là một đồ thị có hướng với các tính chất sau:

Một đường trong đồ thị có hướng là

một dãy các nút v₁, v₂, …, v_k, k  1,

sao cho với mọi i, 1  i  k, có một

cung từ v_itới v_i+1.

1. Có một nút, gọi là nút gốc, không có nút

trước.

2. Mỗi nút khác nút gốc có đúng một nút

trước.

Nếu v  w là một cung thì v được gọi

3. Các nút sau của một nút đều được sắp

xếp thứ tự (từ trái qua phải).

là nút trước của w và w được gọi là nút

sau của v.

 Ví dụ: Cây sau diễn tả cấu trúc cú pháp của một câu

23

24

tiếng Việt: “An là sinh viên giỏi”.

6

Cây (tt)

Phân tích văn phạm Tiếng Việt

• <Câu đơn>  <Chủ ngữ> <Vị ngữ>

• <Chủ ngữ>  <Danh từ>

• <Danh từ>  Sinh viên | Lớp | Tôi | Cô ấy | bạn | An

• <Vị ngữ>  <Động từ> <Bổ ngữ>

• <Động từ>  thì | là | đi | học | chạy

• <Bổ ngữ>  <Danh từ> <Trạng từ> <Tính từ> | <Danh từ>

<Tính từ>

• <Trạng từ>  rất | quá

• <Tính từ>  đẹp | giỏi | tốt

25

26

7

Bài giảng Ôtômát và ngôn ngữ hình thức - Chương 1: Kiến thức cơ sở - Nguyễn Thị Thùy Linh