Bài giảng Lý thuyết ngôn ngữ - Nguyễn Thị Thị Uyên

2/11/2014 1 TRƯỜNG ĐẠI HỌC VINH KHOA CÔNG NGHỆ THÔNG TIN --------------∽∽∽ -------------- BÀI GIẢNG LÝ THUYẾT NGÔN NGỮ Giảng viên: ThS. Nguyễn Thị Uyên Khoa Công nghệ thông tin Chương 0 Bổ túc toán 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 3/17 Nội dung I. Tập hợp II. Quan hệ III. Đồ thị và cây 2/11/2014 2 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 4/17 I. Tập hợp (Set) • Tập hợp là tập các đối tượng không có sự lặp lại. • Mỗi đối tượng trong tập hợp được gọi là phần tử (element) của tập hợp đó. 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 5/17 Biểu diễn tập hợp
Tập hữu hạn: liệt kê từng phần tử
Ví dụ: Tập hợp D xác định tập hợp các ngày trong tuần
D = { Mon, Tues, Wed, Thurs, Fri, Sat, Sun }
Các phần tử được viết cách nhau bởi dấu phẩy và đặt trong cặp dấu { và }.
Thứ tự liệt kê các phần tử là không quan trọng
Viết x ∈ A nghĩa là x thuộc A,
Viết x ∉ A nghĩa là x không thuộc A 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 6/17 Biểu diễn tập hợp
Tập vô hạn: Chỉ ra một số đặc trưng của nó.
Ví dụ:
P = { y | y là số nguyên tố }
X = { x  x > 2 }
Một trường hợp đặc biệt của tập hợp là tập hợp rỗng (empty set). Tập hợp này không có chứa bất kỳ phần tử nào, ký hiệu bởi ∅ hoặc { }. 2/11/2014 3 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 7/17 Tập con (subset)
Tập hợp A là tập hợp con () của tập hợp B khi mọi phần tử của A đều thuộc B.
Ký hiệu: A ⊆ B
Ngược lại, A không là tập con của B (A ⊄ B ).
Ví dụ { 1, 2, 4 } ⊆ { 1, 2, 3, 4, 5 }
{ 2, 4, 6 } ⊄ { 1, 2, 3, 4, 5 }
Nhận xét: tập hợp ∅ ⊆ A, ∀A 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 8/17 Tập bằng nhau
Hai tập hợp A và B được gọi là bằng nhau (A = B) khi A ⊆ B và B ⊆ A
Ví dụ :
{ 1, 2, 3, 4 } = { 2, 1, 4, 3 }
{1, 2, 3, 4 } ≠ { 2, 1, 3, 5 } 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 9/17 Tập lũy thừa
Tập hợp tất cả các tập con của tập A được gọi là tập lũy thừa (power set) của A, ký hiệu: 2A.
Ví dụ : Giả sử A = { 1, 2, 3 }
Thì 2A = { ∅, 1, 2, 3, (1,2), (2,3), (3,1), (1,2,3) } 2/11/2014 4 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 10/17 Phép toán 1. Phép hợp A ∪ B = {x | x ∈A hoặc x ∈B} 2. Phép giao A ∩ B = {x | x ∈A và x ∈B} 3. Phép trừ A \ B = {x | x ∈A nhưng x ∉B} 4. Tích Đecac A × B = {(a,b) | a ∈A và b∈B} 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 11/17 Ví dụ Cho tập A = {1, 2} và B = {2, 3} 1. A ∪ B = {1, 2, 3} 2. A ∩ B = {2} 3. A \ B = {1} 4. A × B = {(1, 2 ), (1, 3), (2, 2), (2, 3)} 5. 2A = {∅, {1}, {2}, {1, 2}} 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 12/17 II. Quan hệ
Quan hệ 2 ngôi từ tập A đến tập B là một tập con của tập tích đề các A × B.
Lưu ý: không nhất thiết tập A phải khác tập B
Ví dụ: Cho tập S = { 0, 1, 2, 3}
Quan hệ "thứ tự nhỏ hơn" trên S được xác định bởi tập L = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)}
Quan hệ "bằng nhau" trên S được xác định bởi tập: E = {(0, 0), (1, 1), (2, 2), (3, 3)} 2/11/2014 5 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 13/17 Tính chất 1. Phản xạ : nếu aRa là đúng ∀a ∈S 2. Đối xứng : nếu aRb thì bRa 3. Bắc cầu : nếu aRb và bRc thì aRc 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 14/17 Quan hệ tương đương
Một quan hệ R trên tập S có đủ các tính chất phản xạ, đối xứng và bắc cầu được gọi là quan hệ tương đương. Ví dụ: Cho tập S = { 0, 1, 2, 3} Quan hệ "bằng nhau" trên S E = {(0, 0), (1, 1), (2, 2), (3, 3)} 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 15/17 III. Đồ thị và cây
Đồ thị G = (V, E), bao gồm một tập hữu hạn các đỉnh V (còn gọi là nút) và một tập các cạnh E nối giữa 2 nút. Ví dụ V = {1, 2, 3, 4, 5} E = {(n, m) | n + m = 4 hoặc n + m = 7} 1 4 3 2 5 2/11/2014 6 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 16/17 Đồ thị có hướng
Là đồ thị mà có sự phân biệt đỉnh nào là đỉnh đầu, đỉnh nào là đỉnh cuối trong một cạnh(cung) Ví dụ: G = ( {1, 2, 3, 4 }, V ={ i → j | i < j } ) 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 17/17 Cây
Cây là một đồ thị có hướng với các tính chất sau : 1. Có một nút đỉnh gọi là nút gốc 2. Mỗi nút còn lại đều được dẫn ra từ một nút cha ở trên nó : - Các nút có dẫn ra nút con sau nó được gọi là nút trung gian hay nút trong. - Các nút không dẫn ra nút con gọi là nút lá. 3. Thứ tự duyệt trên cây là từ trái sang phải. 2/11/2014 Lý thuyết ngôn ngữ - Chương 0 Trang 18/17 Ví dụ Cây minh họa cấu trúc cú pháp của một câu đơn trong ngôn ngữ tiếng Việt "An là sinh viên giỏi" 2/11/2014 1 Chương I Ngôn ngữ hình thức và văn phạm 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 2/20 Nội dung I. Tổng quan về ngôn ngữ II. Biểu diễn ngôn ngữ III. Văn phạm và sự phân loại văn phạm 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 3/20 1.1. Các khái niệm cơ bản về ngôn ngữ a. Bảng chữ cái(alphabet) là một tập hữu hạn hoặc vô hạn các ký hiệu. Ví dụ - Bộ chữ cái Latinh {A, B, C, ... , Z, a, b, c, ... , z} - Bộ chữ số thập phân {0, 1, 2, ... , 9} b. Từ | chuỗi(word) là một dãy các ký hiệu thuộc bảng chữ cái Ví dụ : 0, 1011, 00010, ... là các từ trên bộ chữ cái Σ = {0, 1} c. Độ dài của một từ w, ký hiệu |w| là số các ký hiệu tạo thành từ w. Ví dụ Từ abca có độ dài là 4 , ký hiệu : |abca| = 4 2/11/2014 2 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 4/20 1.1. Các khái niệm cơ bản về ngôn ngữ d. Chuỗi rỗng (ký hiệu ε) là chuỗi không có ký hiệu nào, vì vậy | ε | = 0. e. Chuỗi con chuỗi v được gọi là chuỗi con của w nếu v được tạo bởi các ký hiệu liền kề nhau trong chuỗi w. Ví dụ : Chuỗi 10 là chuỗi con của chuỗi 010001 f. Tiền tố của một chuỗi là một chuỗi con bất kỳ nằm ở đầu chuỗi g. Hậu tố của một chuỗi là chuỗi con nằm ở cuối chuỗi. Ví dụ: Chuỗi abc có các tiền tố là a, ab, abc và các hậu tố là c, bc, abc 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 5/20 1.1. Các khái niệm cơ bản về ngôn ngữ h. Chuỗi nối kết (ghép) từ hai chuỗi con là một chuỗi tạo được bằng cách viết chuỗi thứ nhất sau đó là chuỗi thứ hai (không có khoảng trống ở giữa). Vd: Nối kết chuỗi Long và Int là chuỗi LongInt. ta có εw = wε = w với mọi chuỗi w. i. Chuỗi đảo ngược của chuỗi w, ký hiệu wR là chuỗi w được viết theo thứ tự ngược lại. w = a1 a2 ... an --> w R = an an-1 ... a1. Hiển nhiên : εR = ε Vd: w = abcd --> wR = dcba 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 6/20 1.2. Ngôn ngữ (Language) a. Định nghĩa: một ngôn ngữ (hình thức) L là một tập hợp các chuỗi của một bộ chữ cái Σ nào đó. b. Tập hợp chứa chuỗi rỗng (ký hiệu {ε}) và tập hợp rỗng ∅ cũng được coi là ngôn ngữ. c. Tập Σ* = Tập hợp tất cả các chuỗi (từ) kể cả chuỗi rỗng trên bộ chữ cái cố định Σ. d. Tập Σ+ = Σ* - {ε} Vd : Σ = {0, 1} thì Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, ...} Σ+ = {0, 1, 00, 01, 10, 11, 000, ...} 2/11/2014 3 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 7/20 • 1. Cho Σ = {a, c,}. Hãy mô tả tập Σ* ? • 2. Cho Σ = {a, c,}. Hãy mô tả tập Σ+ ? 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 8/20 1.3. Các phép toán trên ngôn ngữ L1 = {ab, bc}; L2 = {12, 34, ab} a. Phép hợp L1 ∪ L2 = {ab, bc, 12, 34} b. Phép giao L1 ∩ L2 = {ab} c. Phép phần bù của một ngôn ngữ L trên bộ chữ cái Σ được định nghĩa như sau : 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 9/20 1.3. Các phép toán trên ngôn ngữ d. Phép nối kết của hai ngôn ngữ L1 trên bộ chữ cái Σ1 và L2 trên bộ chữ cái Σ2 được định nghĩa bởi : L1L2 = {w1w2 | w1∈ L1 và w2 ∈ L2 } trên bộ chữ cái Σ1 ∪ Σ2 Ví dụ: L1 = {a,b}; L2 = {c,d} thì L1 L2 = {ac,ad,bc,bd} Ta viết L0 = {ε} ; L1 = L ; L2 = LL hay tổng quát Li = LLi - 1 với i > 0. L0 ={ε}, với mọi ngôn ngữ L e. Phép bao đóng của ngôn ngữ L ký hiệu L* L* = L0 ∪ L1 ∪ L2 ∪ L3 ∪ L4 … . 2/11/2014 4 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 10/20 1.3. Các phép toán trên ngôn ngữ f. Phép bao đóng dương: L+ = L1 ∪ L2 ∪ L3 ∪ L4 …. Ví dụ Cho ngôn ngữ L = { a, ba } thì L2 = { aa, aba, baa, baba} L3 = { aaa, aaba, abaa, ababa, baaa, baaba, babaa, bababa} L* = { ε, a, ba, aa, aba, baa, baba, aaa, aaba, abaa, ababa, baaa, baaba, babaa, bababa … } 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 11/20 • Cho ngôn ngữ L = {a, b, c}, tính L3?? 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 12/20 II. Biểu diễn ngôn ngữ
Một ngôn ngữ L trên một bộ chữ cái Σ là một tập con của tập Σ*.
Ngôn ngữ hữu hạn biểu diễn bằng cách liệt kê tất cả các chuỗi thuộc vào chúng.
Ví dụ: L1 = {ε}, L2 = { a, ba, aaba, bbbbb }
Ngôn ngữ vô hạn không thể liệt kê tất cả các chuỗi thuộc ngôn ngữ được
Trong trường hợp đơn giản thì ngôn ngữ được biểu diễn thông qua một phát biểu hay một tân từ.
Ví dụ: L3 = { ai  i là một số nguyên tố }
L4 = { ai bj  i ≥ j ≥ 0 } 2/11/2014 5 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 13/20  Văn phạm là cơ chế cho phép sản sinh ra mọi chuỗi của ngôn ngữ.  Automata là cơ chế cho phép đoán nhận một chuỗi bất kỳ có thuộc ngôn ngữ hay không. Cách biểu diễn ngôn ngữ tổng quát 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 14/20 III. Văn phạm và sự phân lớp văn phạm Văn phạm là một tập các quy tắc về cấu tạo từ và các quy tắc về cách thức liên kết các từ thành câu. Định nghĩa toán học của văn phạm : Văn phạm G là một hệ thống gồm bốn thành phần xác định như sau: G = (Σ, ∆, P, S)
Σ : tập hợp các ký hiệu kết thúc (terminal)
∆ : tập hợp các biến (variables) hay các ký hiệu chưa kết thúc (non terminal) (với Σ ∩ ∆ = ∅)
P :tập hữu hạn các quy tắc ngữ pháp được gọi là các luật sinh (production), mỗi luật sinh được biểu diễn dưới dạng α → β, với α, β là các chuỗi ∈ (Σ ∪ ∆)*.
S ⊂ ∆ : ký hiệu chưa kết thúc dùng làm ký hiệu bắt đầu (start) 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 15/20 Ví dụ Văn phạm G = (Σ, ∆, P, S) • ∆ = {S, B, C}, • Σ = {a, b, c} • P = {S → aSBC, S → aBC, CB → BC, aB →ab, bB → bb, bC → bc, cC → cc } Quy ước • Các chữ cái Latinh viết hoa (A, B, C, ...) thường dùng để biểu diễn các ký hiệu chưa kết thúc trong tập biến ∆. • Các chữ cái Latinh viết thường (a, b, c, ...) thường dùng để biểu diễn các ký hiệu kết thúc thuộc tập Σ. 2/11/2014 6 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 16/20 • P:{S->abA, A->aA|a, B->bB|Bc, AB->abC} 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 17/20 Dẫn xuất
Từ văn phạm, để sinh ra được các chuỗi (từ), ta định nghĩa khái niệm “dẫn xuất” như sau :
Nếu α → β là một luật sinh thì γ α δ ⇒ γ β δ gọi là một dẫn xuất trực tiếp, có nghĩa là áp dụng luật sinh α → β vào chuỗi γ α δ để sinh ra chuỗi γ β δ.
Nếu các chuỗi α1, α2, ...., αm ∈ Σ* và α1⇒ α2, α2⇒ α3, ..., αm-1 ⇒ αm thì ta nói αm có thể được dẫn ra từ α1 thông qua chuỗi dẫn xuất α1⇒ α2, α2⇒ α3, ..., αm-1 ⇒ αm hay α1 dẫn xuất (gián tiếp) ra αm, viết tắt là α1⇒* αm 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 18/20 • Bai 1: Cho văn phạm với tập luật sinh P được xác định như sau: • P = {S → abA | aA | ab; A → bAS | b} • 1. Xây dựng thành phần Σ và ∆ của văn phạm. • 2. Đưa ra dẫn xuất của văn phạm để sinh chuỗi abbbab. 2/11/2014 7 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 19/20 Ví dụ Xét văn phạm G = (Σ, ∆, P, S)
∆ = {S, A},
Σ = {a, b}
P = { S → aS, S → aA, A → bA, A → b } Một dẫn xuất từ S có dạng :
S ⇒ aS ⇒ aaS ⇒ aaaA ⇒ aaabA ⇒ aaabbA ⇒ aaabbbA ⇒ aaabbbb = a3 b4
Văn phạm này sinh ra ngôn ngữ
L(G) = {a+b+} = {anbm n, m ≥ 1 } 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 20/20 Ngôn ngữ của văn phạm
Ngôn ngữ của văn phạm G = (Σ, ∆, P, S) là tập hợp các chuỗi ký hiệu kết thúc w ∈ Σ* được sinh ra từ ký hiệu bắt đầu S của văn phạm bởi các luật sinh thuộc tập P, ký hiệu là L(G) : L (G) = {w w ∈ Σ* và S ⇒* w}
Hai văn phạm tương đương là hai văn phạm cùng sinh ra một ngôn ngữ: G1 tương đương G2 ⇔ L (G1) = L (G2) 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 21/20 Phân loại văn phạm theo Chomsky 1. Văn phạm loại 0 (Unrestricted Grammar) Là văn phạm không cần thỏa mãn ràng buộc nào trên tập các luật sinh 2. Văn phạm loại 1
Mọi luật sinh của văn phạm có dạng α → β và thỏa mãn β≥α (văn phạm cảm ngữ cảnh CSG - Context- Sensitive Grammar).
Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ cảm ngữ cảnh (CSL). 2/11/2014 8 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 22/20 • Cho văn phạm với tập luật sinh: P = {S → a | aA; A → aS | bB | cC; C → cA} • 1. Văn phạm trên là văn phạm gì? • 2. Chuỗi abab có thuộc ngôn ngữ sinh ra bởi văn phạm hay không? Vì sao? 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 23/20 Phân loại văn phạm theo Chomsky 3. Văn phạm loại 2
Là văn phạm mà mọi luật sinh có dạng A → α với A là một biến đơn (A ∈ ∆) và α ∈ (Σ ∪ ∆)* - văn phạm phi ngữ cảnh CFG (Context-Free Grammar).
Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ phi ngữ cảnh (CFL) 4. Văn phạm loại 3
Là văn phạm mà mọi luật sinh dạng A → aB hoặc A → a với A, B là các biến đơn thuộc ∆, a là ký hiệu kết thúc thuộc Σ - văn phạm chính quy RG (Regular Grammar).
Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ chính quy (RL). 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 24/20 Ví dụ Xác định loại của các văn phạm sau? a. Xét văn phạm G = {Σ, ∆, P, S} ∆ = {S, B, C}, Σ = {a, b, c} và tập P = {S → aSBC, S → aBC, CB → BC, aB →ab, bB → bb, bC → bc, cC → cc } b. Xét văn phạm G = {Σ, ∆, P, S} ∆ = {S}, Σ = {a, b} và tập P = {S → aSb, S → ab } c. Xét văn phạm G = {Σ, ∆, P, S} ∆ = {S, A}, Σ = {a, b} và tập P = { S → aS, S → aA, A → bA A → b } 2/11/2014 9 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 25/20 Bài tập Xem các ví dụ trong sách Lý thuyết ngôn ngữ hình thức và otomat Tác giả: Đặng Huy Ruận Từ trang 30 đến trang 45 Chú ý: 1. Ký hiệu V trong sách tương ứng với ký hiệu ∆ 2. Ký hiệu ^ trong sách tương ứng với ký hiệu ε 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 26/20 BÀI TẬP Bài 1: Xét văn phạm G : ∆ = {S, A}, Σ = {a, b} và tập P = { S -> aS| aA; A -> bA| b}. - Xác định văn phạm loại mấy? - Xây dựng dẫn xuất sinh ra chuỗi aaabb? Bài 2: Xét văn phạm G : ∆ = {S}, Σ = {a, b} và tập P = { S > aSb; S > ab } - Xác định văn phạm loại mấy? - Xây dựng dẫn xuất sinh ra chuỗi aaaabbbb ? 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 27/20 Bài 3: Xét văn phạm G : ∆ = {S, B, C}, Σ = {a, b, c} và tập P = { S -> aSBC| aBC; CB -> BC; aB -> ab; bB -> bb; bC -> bc; cC -> cc } - Xây dựng dẫn xuất sinh ra chuỗi aabbcc ? - Xác định L(G)? 2/11/2014 10 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 28/20 Bài 4 Cho văn phạm với tập luật sinh: P = {S → a | aA; A → aS | b| cC; C → cA} 1. Xác định các thành phần của văn phạm? 2. Văn phạm trên là văn phạm loại gì? 3. Chuỗi accb có thuộc ngôn ngữ sinh ra bởi văn phạm hay không? Vì sao? 2/11/2014 Lý thuyết ngôn ngữ - Chương I Trang 29/20 Bài 5 1. Cho ngôn ngữ L = {a,b}, tính L3. 2. Tìm chuỗi đảo ngược của chuỗi dcab. 2/11/2014 1 Chương II ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 2/44
Ôtômát hữu hạn đơn định (DFA)
Ôtômát hữu hạn không đơn định (NFA)
Sự tương đương giữa DFA và NFA
NFA với ε-dịch chuyển (NFAε)
Sự tương đương giữa NFAε và NFA
Biểu thức chính qui
Sự tương đương giữa biểu thức chính qui và NFAε Nội dung 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 3/44 GIỚI THIỆU  Automata là cơ chế cho phép đoán nhận ngôn ngữ. Với một chuỗi bất kỳ, sau một số bước làm việc, ôtômát sẽ cho câu trả lời chuỗi đó có thuộc ngôn ngữ hay không.  Mỗi bước làm việc của Automata là một sự thay thế ký hiệu, nghĩa là một bước dẫn xuất như ở trong văn phạm. 2/11/2014 2 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 4/44 Mô hình cơ chế ôtômát  Chuỗi nhập cần xác định sẽ được lưu trữ trên băng input. 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 5/44 Phân loại các ôtômát  Phân loại dựa theo hoạt động của ôtômát  Ôtômát đơn định DA (Deterministic Automata) : tại mỗi bước chuyển, nó chỉ có một khả năng duy nhất. Sự duy nhất này thể hiện tính đơn định.  Ôtômát không đơn định NDA (Non - deterministic Automata) tại mỗi bước di chuyển, nó có một vài khả năng để chọn lựa. Sự chọn lựa này thể hiện tính không đơn định. 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 6/44 Ôtômát hữu hạn (FA : Finite Automata)  Tại mỗi thời điểm, hệ thống có số trạng thái là hữu hạn  Mỗi trạng thái của hệ thống tại mỗi thời điểm sẽ thay đổi tùy thuộc vào INPUT  Ôtômát hữu hạn (FA) được chia thành 2 loại: đơn định (DFA) và không đơn định (NFA). 2/11/2014 3 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 7/44 I. Ôtômát hữu hạn đơn định - DFA (Deterministic Finite Automata) Ôtômát hữu hạn đơn định 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 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 khởi đầu  F ⊆ Q là tập các trạng thái kết thúc 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 8/44 Sơ đồ chuyển (transition diagram) Một đồ thị có hướng, gọi là sơ đồ chuyển tương ứng với một DFA như sau:  Các đỉnh của đồ thị là các trạng thái của DFA.  Nếu có một đường chuyển từ trạng thái q đến trạng thái p trên input a thì có một cung nhãn a từ đỉnh q đến đỉnh p trong sơ đồ chuyển.  Trạng thái khởi đầu q0 nhãn "Start".  Các trạng thái kết thúc trong F được chỉ ra bằng hai vòng tròn. 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 9/44 Ngôn ngữ được chấp nhận bởi DFA  Một chuỗi x được chấp nhận bởi ôtômát hữu hạn M (Q, Σ, δ, q0, F) nếu δ(q0, x) = p với p ∈ F.  Ngôn ngữ được chấp nhận bởi M L(M) = { x | δ (q0, x) ∈ F } 2/11/2014 4 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 10/44 Cơ chế hoạt động của DFA Cho xâu vào ω = x1 x2 x3 ... xn ∈ ∑*. Ta mô tả hoạt động của ôtômát như sau: ω = x1 x2 ... xn-1 xn ↑ qo → ......... Khi bắt đầu làm việc máy ở trạng thái đầu qo và đầu đọc đang nhìn vào ô có ký hiệu x1. Tiếp theo từ trạng thái qo dưới tác động của ký hiệu vào x1 máy chuyển sang trạng thái mới δ (qo, x1) = q1 ∈ Q và đầu đọc chuyển sang phải một ô, tức nhìn vào ký hiệu x2 ω = x1 x2 x3 .... xn-1 xn ↑ ↑ q0 →q1 → 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 11/44 Sau đó, ôtômát lại tiếp tục chuyển từ trạng thái q1 dưới tác động của x2 về trạng thái mới q2 = δ(q1, x2) = δ(δ(qo, x1), x2) = δ(qo, x1 x2) ∈ Q Quá trình đó sẽ tiếp tục cho tới khi đầu đọc nhìn vào ký hiệu xn với trạng thái của máy là qn-1 = δ (qn-2, xn-1) = δ (q0, x1x2 ... xn-1) ∈ Q. x1 x2 ... xn-1 xn ↑ ↑ ↑ ↑ qo → q1 .... qn-2 → qn-1 → qn Hàm chuyển lại đưa máy từ trạng thái qn-1 dưới tác động của xn về trạng thái : qn = δ(qn-1, xn) = δ(qo, x1 ... xn) ∈ Q. Khi đó ôtômát dừng lại. Nếu qn∈F thì ta nói rằng Cơ chế hoạt động của DFA 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 12/44 Ví dụ 1 Kiểm tra chuỗi 110101 Vẽ sơ đồ chuyển Kiểm tra chuỗi 1101? VD. Cho DFA: với Q = {q0, q1, q2, q3}, Σ = {0, 1}, F = {q0} và hàm chuyển δ như sau: 2/11/2014 5 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 13/44 Ví dụ 2 Cho ôtô mát đơn định M = với ∑={0,1}, Q={qo, q1, q2, q3}, qo là trạng thái ban đầu, còn F = {q3} là tập hợp trạng thái kết thúc. Hàm chuyển trạng thái được cho trong bảng sau Trạng thái Ký hiệu vào 0 1 qo q1 q2 q3 q1 q2 q3 qo q0 q3 q3 q3 Xét các xâu ω1 = 10110, ω2 = 110, ω3 = 10011. 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 14/44 Giải thuật mô phỏng hoạt động của một DFA 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 15/44 Nhận xét  Tập Q của DFA thể hiện các trạng thái lưu trữ của ôtômát trong quá trình đoán nhận ngôn ngữ, và như vậy khả năng lưu trữ của ôtômát là hữu hạn.  Hàm chuyển δ là hàm toàn phần và đơn trị, cho nên các bước chuyển của ôtômát luôn luôn được xác định một cách duy nhất.  Chính vì hai đặc điểm này mà DFA mô tả như trên được gọi là ôtômát hữu hạn đơn định. 2/11/2014 6 2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 16/44 II.Ôtômát hữu hạn không đơn định