Lý thuyết automata và ngôn ngữ hình thức

Grammar

Automata

Ngôn ngữ hình thức

G I Ả N G V I Ê N : T S . H À C H Í T R U N G B Ộ M Ô N : K H M T K H O A C N T T , H V K T Q S Đ T : 0 1 6 8 . 5 5 8 . 2 1 . 0 2 E M A I L : H C T 2 0 0 9 @ Y A H O O . C O M

©copyright by PhD. C.T.Ha, Le Quy Don Technical University

Bài 1. Nhập môn Theory of automata and formal languagues – TA&FL (AL)

MỤC ĐÍCH:

 Trang bị những hiểu biết chung nhất về môn học;  Khái quát lại một số khái niệm, cơ sở toán học làm cơ sở

học tập môn học.

YÊU CẦU:

 Về nhà, sinh viên phải hệ thống lại các kiến thức cơ sở về

toán liên quan và kiến thức lập trình.

©copyright by PhD. C.T.Ha, Le Quy Don Technical University

Bài 1. Nhập môn TA&FL

1.1. Giới thiệu về môn học TA&FL

1.2. Yêu cầu với môn học

1.3. Tài liệu tham khảo môn TA&FL

1.4. Bổ túc một số khái niệm toán học

1.4.1. Tập hợp

1.4.2. Quan hệ

1.4.3. Phép chứng minh

1.4.4. Đồ thị và cây

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

Bài 1. Nhập môn TA&FL

1.1. Giới thiệu về môn học TA&FL

1.2. Yêu cầu với môn học

1.3. Tài liệu tham khảo môn TA&FL

1.4. Bổ túc một số khái niệm toán học

1.4.1. Tập hợp

1.4.2. Quan hệ

1.4.3. Phép chứng minh

1.4.4. Đồ thị và cây

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.1. Giới thiệu về môn học TA&FL

 Ngôn ngữ hình thức (Formal Languages) là môn học cơ

sở của ngành công nghệ thông tin:  Turing, Post Church,... nghiên cứu xây dựng mô hình toán học

cho các máy tính toán (30,40th–XXc.);

 Chomsky với mục đích xây dựng mô hình toán cho ngôn ngữ

tự nhiên (50th–XXc.).

 Môn học trang bị cho người học những kiến thức cơ bản về thuật toán, ngôn ngữ thuật toán, các kỹ thuật xây dựng chương trình, xây dựng các hệ thống tự động và phương pháp tư duy liên quan đến khoa học máy tính.

 Kiến thức về ngôn ngữ hình thức và automat là nền tảng cho nhiều lĩnh vực của khoa học máy tính và CNTT.

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.1. Giới thiệu về môn học TA&FL

 Ứng dụng của lý thuyết ngôn ngữ hình thức và automata:

 Dùng trong xử lý từ vựng và cú pháp ngôn ngữ tự nhiên;  Dùng trong xây dựng ngôn ngữ lập trình ctd;  Dùng trong nhận dạng (đối với những mẫu nhận dạng có

cấu trúc);

 Dùng trong tin sinh học (Bio-informatics);  Dùng trong tính toán phân tử (DNA Computing);  Dùng trong xử lý ảnh (nén ảnh Fractal,...);  Dùng trong công nghệ phần mềm ( mã hóa dữ liệu, mô hình hoá các hệ thống động, các tiến trình hệ thống…);

 Trong lĩnh vực trí tuệ nhân tạo…

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.1. Giới thiệu về môn học TA&FL

 Nội dung chính của môn học TA&FL: 1. Cơ sở toán học của môn TA&FL 2. Văn phạm và ngôn ngữ hình thức 3. Automata hữu hạn và ngôn ngữ hình thức 4. Văn phạm chính quy và các tính chất 5. Văn phạm phi ngữ cảnh 6. Pushdown automata (automata đẩy xuống) 7. Máy Turing 8. Phần bài tập lý thuyết và thực hành

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

Bài 1. Nhập môn TA&FL

1.1. Giới thiệu về môn học TA&FL

1.2. Yêu cầu với môn học

1.3. Tài liệu tham khảo môn TA&FL

1.4. Bổ túc một số khái niệm toán học

1.4.1. Tập hợp

1.4.2. Quan hệ

1.4.3. Phép chứng minh

1.4.4. Đồ thị và cây

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.2. Một số yêu cầu với môn học

 Kiến thức nền:

 Toán rời rạc (tập hợp, đồ thị, cây, quan hệ, phương pháp

chứng minh,…);

 các kiến thức toán liên quan;  khả năng lập trình (C, C++, C#,…)

 Hình thức đánh giá:

 Tổng số tiết: 45;  Hình thức thi: vấn đáp;  Điểm đánh giá: c.cần 10%, t.xuyên 20%, thi 70%;  Đồ án môn: Giải bài tập và viết chương trình.

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

Bài 1. Nhập môn TA&FL

1.1. Giới thiệu về môn học TA&FL

1.2. Yêu cầu với môn học

1.3. Tài liệu tham khảo môn TA&FL

1.4. Bổ túc một số khái niệm toán học

1.4.1. Tập hợp

1.4.2. Quan hệ

1.4.3. Phép chứng minh

1.4.4. Đồ thị và cây

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.3. Tài liệu môn học

1. Bài giảng của giảng viên. 2. Nguyễn Gia Định. Lý thuyết ngôn ngữ hình thức và ôtômát. Đại học khoa học Đại học Huế - 2004.

3. Nguyễn Văn Xuất. Giáo trình Automata, ngôn ngữ hình thức và nguyên lý chương trình dịch - HVKTQS – 2004. 4. Hồ Văn Quân – Giáo trình lý thuyết ôtômát và ngôn ngữ hình thức – Nhà xuất bản Đại học quốc gia Tp. Hồ Chí Minh – 2002.

5. John E. Hopcropft, Rareev Motwani, Jeffrey D. Ullman.

Introduction to Automata Theory, Languages, and Computation (2nd Edition) -Addison-Wesley.-2001.

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

Bài 1. Nhập môn TA&FL

1.1. Giới thiệu về môn học TA&FL

1.2. Yêu cầu với môn học

1.3. Tài liệu tham khảo môn TA&FL

1.4. Bổ túc một số khái niệm toán học

1.4.1. Tập hợp

1.4.2. Quan hệ

1.4.3. Phép chứng minh

1.4.4. Đồ thị và cây

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.4.1. Tập hợp

ĐN 1.1: Tập hợp là một nhóm các đối tượng rời rạc và không

có sự lặp lại.

Ví dụ 1.1:

D = {Mon, Tue, Wed, Thu, Fri, Sat, Sun};

Phần tử

- các phần tử là rời rạc - các phần tử không lặp lại

D = {1, 2, 3}

Hình thức biểu diễn tập hợp:  Liệt kê phần tử:  Mô tả tính chất đặc trưng: D = { x | x là một ngày trong tuần}

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.4.1. Tập hợp

 ĐN 1.2: Tập rỗng, ký hiệu là  hoặc { }  ĐN 1.3: Tập hợp con (subset)

oKý hiệu: A  B (Ngược lại: A  B ) o{ 1, 2, 4 }  { 1, 2, 3, 4, 5 } nhưng { 2, 4, 6 }  { 1, 2, 3, 4, 5 }

 ĐN 1.4: Tập hợp bằng nhau

oKý hiệu: A = B nếu ( x  A )  ( x  B ), (ngược lại: A  B ) o{ 1, 2 } = { 2, 1 } nhưng { 1, 2, 3 }  { 2, 1 }

 ĐN 1.5: Tập lũy thừa (power set)

oKý hiệu: 2A oA = { 1, 2, 3 } thì 2A = {, {1}, {2}, {3}, {1, 2}, {2, 3}, {3, 1}, {1, 2, 3} }

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.4.1. Tập hợp

 Kết quả của một số phép toán sau đây trên các tập hợp là

một tập hợp mới.

 Phần bù (complement):

A’ = { x | x  A }

 Phép hợp (Union):

A  B = { x | x  A hoặc x  B }

 Phép giao (intersection):

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

 Phép trừ (difference):

A \ B = { x | x  A nhưng x  B }

 Tích Đềcác:

A x B = { (a,b) | a  A và b  B }

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.4.1. Tập hợp

 Ví dụ 1.2: Cho A = {1, 2} và B = {2, 3}

o A  B = { 1, 2, 3 }

o A  B = { 2 }

o A \ B = { 1 }

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

o 2A = { , {1}, {2}, {1, 2} }

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

Bài 1. Nhập môn TA&FL

1.1. Giới thiệu về môn học TA&FL

1.2. Yêu cầu với môn học

1.3. Tài liệu tham khảo môn TA&FL

1.4. Bổ túc một số khái niệm toán học

1.4.1. Tập hợp

1.4.2. Quan hệ

1.4.3. Phép chứng minh

1.4.4. Đồ thị và cây

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.4.2. Quan hệ

 ĐN 1.6: Cho các tập hợp A1, A2, ..., An. Một quan hệ

(relations) n-ngôi trên các các tập hợp này là tập hợp con của tích Đềcác A1◦A2 ◦... ◦ An mà thỏa mãn một số tính chất nào đó. Các tập hợp A1, A2, ..., An được gọi là miền của quan hệ và n gọi là bậc của quan hệ.

 Ví dụ 1.3: Cho R là một quan hệ gồm bộ 3 số nguyên (a, b, c)

thỏa mãn a < b < c trên tập nguyên dương.

 Ví dụ 1.4: Cho R là một quan hệ gồm bộ 2 số nguyên (a, b) thỏa

mãn a ≡ b mod 3 trên tập nguyên dương.

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.4.2. Quan hệ

 ĐN 1.7: Cho hai tập hợp A và B. Một quan hệ (relations) hai

ngôi R giữa A và B là tập hợp chứa tất cả các tập hợp con của A × B mà thành phần thứ nhất A được gọi là miền xác định (domain) của R, còn B gọi là miền giá trị (range) của R.

 Nếu miền xác định và miền giá trị cùng thuộc một tập hợp S,

gọi là một quan hệ trên S. Nếu R là một quan hệ và (a,b) là một cặp trong R thì ta viết aRb.

R( A  B ) = aRb miền xác định (domain)

 miền giá trị (range)

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.4.2. Quan hệ

 Các tính chất của quan hệ:  Phản xạ (reflexive): nếu aRa là đúng với aS  Đối xứng (symmetric): nếu aRb thì bRa  Bắc cầu (transitive): nếu aRb và bRc thì aRc  Ví dụ 1.5: cho S = {0, 1, 2, 3} o Quan hệ ‘thứ tự nhỏ hơn’:

L = { (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) } o Quan hệ ‘bằng’: E = { (0, 0), (1, 1), (2, 2), (3, 3) } o Quan hệ ‘chẵn lẻ’:

P = { (0, 0), (1, 1), (2, 2), (3, 3), (0, 2), (2, 0), (1, 3), (3, 1)}

o Tính chất: L không là quan hệ phản xạ hay đối xứng, E

và P mang tính phản xạ, đối xứng và bắc cầu Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

07/03/2012

1.4.2. Quan hệ

 ĐN 1.8: quan hệ mang tính phản xạ, đối xứng và bắc cầu

được gọi là quan hệ tương đương.

 Ví dụ 1.6: E và P là quan hệ tương đương, L không là quan

hệ tương đương.

 ĐN 1.9: Nếu R là quan hệ tương đương trên S thì R phân hoạch S thành các lớp tương đương không rỗng và rời nhau: S = S1  S2  …

 Tính chất:

o Si  Sj = ; o Nếu a, b cùng thuộc Si thì aRb đúng; o Nếu a  Si và b  Sj, i≠j thì aRb sai.

 Ví dụ 1.7: P có 2 lớp tương đương {0, 2} và {1, 3}

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.4.2. Quan hệ

 ĐN 1.10: Bao đóng của quan hệ (P-closure) là quan hệ

nhỏ nhất thỏa các tính chất trong P (tập hợp một số tính chất của các quan hệ)

 ĐN 1.11: Bao đóng bắc cầu R+: o Nếu (a,b)  R thì (a,b) R+ o Nếu (a,b)  R+ và (b,c)  R thì (a,c)  R+ o Không còn gì thêm trong R+

 ĐN 1.12: Bao đóng phản xạ và bắc cầu R*:

o R* = R+  { (a, a)  a  S }

 Ví dụ 1.8: R = { (1, 2), (2, 2), (2, 3) } trên S = {1, 2, 3}

o R+ = { (1, 2), (2, 2), (2, 3), (1, 3) } o R* = { (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3) }

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

Bài 1. Nhập môn TA&FL

1.1. Giới thiệu về môn học TA&FL

1.2. Yêu cầu với môn học

1.3. Tài liệu tham khảo môn TA&FL

1.4. Bổ túc một số khái niệm toán học

1.4.1. Tập hợp

1.4.2. Quan hệ

1.4.3. Phép chứng minh

1.4.4. Đồ thị và cây

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.4.3. Phép chứng minh

 Chứng minh trực tiếp: Áp dụng phép suy diễn lôgic (phép

kéo theo) một cách tuần từ theo từng bước: A1  A2  . . . . .  Ak B

 Ví dụ 1.9: chứng minh với mọi số nguyên n thì biểu thức:

n2 - n +5

biểu diễn một số lẻ.

07/03/2012 Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University

1.4.3. Phép chứng minh

 Chứng minh lựa chọn: áp dụng phương pháp chứng minh

trực tiếp cho tất cả các trường hợp riêng của bài toán:

Case 1: A1  B Case 2: A2  B … Case n: An  B

 Ví dụ 1.10: chứng minh với mọi số nguyên n thì biểu thức:

9n2 + 3n -2

biểu diễn một số chẵn.

1.4.3. Phép chứng minh

 Chứng minh bằng phản chứng: trong trường hợp không biết bắt đầu bằng lập luận nào hoặc không thể liệt kê các trường hợp, ta có thể áp dụng luật phủ định của phủ định, có nghĩa là chứng minh phủ định của A là sai.

 Ví dụ 1.11: chứng minh nếu n là số nguyên và n2 chẵn thì n

cũng là số chẵn.

 Ví dụ 1.12: chứng minh nếu x là số thực bất kỳ thì x2 –

4x+17 0.

1.4.3. Phép chứng minh

 Chứng minh bằng quy nạp:

o Bước 1 (cơ sở quy nạp): chứng minh P(0)

o Bước 2 (giả thiết quy nạp): giả sử P(n-1)

o Bước 3 (quy nạp): P(n - 1)  P(n),  n  1.

 Ví dụ 1.13: chứng minh:

Bài 1. Nhập môn TA&FL

1.1. Giới thiệu về môn học TA&FL

1.2. Yêu cầu với môn học

1.3. Tài liệu tham khảo môn TA&FL

1.4. Bổ túc một số khái niệm toán học

1.4.1. Tập hợp

1.4.2. Quan hệ

1.4.3. Phép chứng minh

1.4.4. Đồ thị và cây

 Khái niệm đồ thị (graph): một đồ thị là một bộ đôi G =

(V, E) (hoặc ký hiệu là G(V, E)), trong đó:

o V : tập các đỉnh (nút); o E : tập các cạnh nối giữa 2 nút.

 Nếu giữa 2 đỉnh chỉ có tối đa một cạnh, ta gọi đồ thị là đơn.  Ví dụ 1.14: đồ thị G = (V, E) dưới đây là đơn đồ thị:

1.4.4. Đồ thị và cây

 Một cạnh (u, v) của G (V, E) thường được viết là uv (hay vu), ta nói cạnh uv nối u với v, lúc đó, ta nói u và v là 2 đỉnh kề nhau. Nếu giữa 2 đỉnh có nhiều hơn 1 cạnh ta gọi chúng là cạnh bội (hoặc cạnh song song). Đồ thị G, trong trường hợp này, là đa đồ thị.

 Ví dụ 1.15: đồ thị G = (V, E) dưới đây là đa đồ thị:

1.4.4. Đồ thị và cây

 Nếu một cạnh nối 1 đỉnh với chính nó (ví dụ: uu, vv,...) ta gọi

cạnh đó là khuyên.

 Ví dụ 1.16: đa đồ thị G(V, E) đưới đây có chứa các khuyên:

1.4.4. Đồ thị và cây

 (Đa) đồ thị có hướng (directed graph) G = (V, E)

o V : tập các đỉnh (nút) o E : tập các cung có hướng v  w

 Ví dụ 1.17: đồ thị G = (V, E) dưới đây là một đa đồ thị có

hướng:

1.4.4. Đồ thị và cây

 Phân biệt dạng đồ thị:

Loại

Cạnh

Có khuyên?

Có cạnh bội?

Đơn đồ thị Đa đồ thị Giả đồ thị Đồ thị có hướng Đa đồ thị có hướng

Vô hướng Vô hướng Vô hướng Có hướng Có hướng

Không Có Có Không Có

Không Không Có Có Có

 Cây: cây là đồ thị có hướng gồm

o 1 nút gốc (root) o Các nút trung gian (nút trong: có nút cha và các nút con) o Các nút lá: không dẫn ra nút con

1.4.4. Đồ thị và cây

 Ví dụ 1.18: Cho cây sau:

 Duyệt cây:

Duyệt theo thứ tự trước: 1, 2, 5, 6, 3, 4, 7, 9, 10, 8 Duyệt theo thứ tự giữa: 5, 2, 6, 1, 3, 9, 7, 10, 4, 8 Duyệt theo thứ tự sau: 5, 6, 2, 3, 9, 10, 7, 8, 4, 1.