VĂN PHẠ M VÀ NGÔN NG Ữ HÌNH TH Ứ C
Các khái ni ệm cơ bả n v ề ngôn ng ữ hình th ứ c
1.1.1 B ả ng ch ữ cái Định nghĩa 1.1 Tập Σ khác rỗng gồm hữu hạn hay vô hạn các ký hiệu được gọi là bảng chữ cái Mỗi phần tử a∈Σđược gọi là một chữ cái hay một ký hiệu
Ví d ụ 1.1 Dưới đây là các bảng chữ cái:
1.1.2 T ừ Định nghĩa 1.2 Giả sử có bảng chữ cái Σ = {a 1 , a 2 , …, am}, một dãy các chữ cái α
Một từ hay xâu trên bảng chữ cái Σ được ký hiệu là a i1 a i2 …ait, trong đó a ij thuộc Σ (1 ≤ j ≤ t) Độ dài của từ α, ký hiệu là |α|, được xác định bởi tổng số vị trí của các ký hiệu xuất hiện trong xâu này.
Một từ từ bảng chữ cái Σ là một xâu hữu hạn, bao gồm ít nhất một chữ cái của Σ, trong đó mỗi chữ cái có thể xuất hiện nhiều lần.
Xâu không có chữ cái nào được gọi là từ rỗng và được ký hiệu là ε Rõ ràng từ rỗng là từ thuộc mọi bảng chữ cái
Hai từα = a1a 2 …anvà β = b1b 2 …bmđược gọi là bằng nhau và được ký hiệu là α = β, nếu n = m và a i = b i với mọi i = 1, 2, …, n.
Nếu α là một từ trong bảng chữ cái Σ, thì α cũng thuộc bảng chữ cái mở rộng Tập hợp tất cả các từ trên bảng chữ cái Σ được ký hiệu là Σ*, trong khi tập hợp các từ không rỗng được ký hiệu là Σ+ Do đó, Σ+ = Σ* \{ε} và Σ* = Σ+ ∪ {ε} Cả hai tập hợp Σ* và Σ+ đều là vô hạn.
Cấu trúc đại số của Σ * là một vị nhóm tự do được sinh ra từ Σ với đơn vị là từ rỗng ε, trong khi Σ + là một nửa nhóm tự do cũng được sinh ra từ Σ Có thể chứng minh rằng các tập hợp Σ * và Σ + đều là vô hạn đếm được.
1 Ta có ε , 0, 01, 101, 1010, 110011 là các từ trên bảng chữcái Г = {0,1};
2 Các xâu ε, beautiful, happy, holiday là các từ trên bảng chữcái Σ = {a, b, c,…, z}
1.1.3 Ngôn ng ữ Định nghĩa 1.3 Cho bảng chữ cái Σ, mỗt tập con L ⊆ Σ * được gọi là một ngôn ngữ hình thức (hay ngôn ngữ) trên bảng chữcái Σ.
Tập rỗng, ký hiệu ∅, là một ngôn ngữ không chứa bất kỳ từ nào, được gọi là ngôn ngữ rỗng Ngôn ngữ rỗng đại diện cho một ngôn ngữ tồn tại trên mọi bảng chữ cái.
Chú ý rằng ngôn ngữ rỗng: L = ∅ là khác với ngôn ngữ chỉ gồm một từ rỗng: L = {ε}.
1 Σ * là ngôn ngữ gồm tất cả các từ trên Σ còn Σ + là ngôn ngữ gồm tất cả các từ khác từ rỗng trên Σ
2 L = { ε, 0, 1, 01, 10, 00, 11, 011, 100} là một ngôn ngữ trên bảng chữ cái Г {0, 1}
3 L = {a, b, c, aa, ab, ac, abc} là ngôn ngữ trên bảng chữcái Σ = {a, b, c}
4 L 1 = {ε, a, b, abb, aab, aaa, bbb, abab}, L2 = {a n b n | n∈ N} là hai ngôn ngữ trên bảng chữΣ = {a, b}, L1 là ngôn ngữ hữu hạn trong khi L 2 là ngôn ngữ vô hạn Mỗi từ thuộc ngôn ngữ L2 có số chữ cái a bằng số chữ cái b với a và b không xen kẽ, a nằm ở phía trái và b ở phía phải của từ.
Các phép toán trên các từ
Các phép toán dưới đây thực hiện trên các từ trên cùng một bảng chữcái Σ, tạo nên các từ mới cũng thuộc cùng một bảng chữ cái
1.2.1 Phép nhân ghép Định nghĩa 2.1 Tích ghép (hay nhân ghép) của hai từ α = a1a2…am và từ β b 1 b 2 …bn trên bảng chữcái Σ, là từ γ = a1a 2 …amb 1 b 2 …bn trên bảng chữcái Σ.
Kí hiệu phép nhân ghép là γ = α.β (hay γ = αβ).
Nh ậ n xét: Từđịnh nghĩa 2.1, ta thấy:
- Từ rỗng là phần tử đơn vị đối với phép nhân ghép, tức là: ωε = εω = ω đúng với mọi từω;
- Phép nhân ghép có tính kết hợp, nghĩa là với mọi từα, β, γ, ta có (αβ)γ = α(βγ);
- Ký hiệu ω n , với n là số tựnhiên, được dùng theo nghĩa quen thuộc:
- Đối với phép nhân ghép thì hàm độ dài có một số tính chất hình thức của lôgarit: với mọi từα, β và mọi số tự nhiên n, thì:
Và rõ ràng là với phần tử đơn vị, tức là từ rỗng ε, thì | ε | = 0
Một vài khái niệm liên quan:
- Đối với các từ ω, t1, θ, t2 trên bảng chữ cái Σ mà ω = t1 θ t2 thì *θ * (* không phải là một ký hiệu của Σ) gọi là một vị trí của θ trên Σ;
- Xâu θ được gọi là một từ con trong ω nếu tồn tại ít nhất một vị trí của θ trong ω;
Nếu t1 = ε, thì θ là tiền tố của từ ω; nếu t2 = ε, thì θ là hậu tố của từ ω Từ rỗng ε đóng vai trò là phần đầu, phần cuối và là từ con của bất kỳ từ ω nào trên bảng chữ cái Σ.
- Trường hợp |θ| = 1, tức là θ chỉ gồm 1 ký hiệu, chẳng hạn θ = b ∈ Σ, thì *b* được gọi là một vị trí của b trong từω, cũng gọi là một điểm trong ω;
- Số vị trí của kí hiệu a trong từ ω được ký hiệu là I a (ω) hay |ω|a hoặc đơn giản hơn là ω|a
1 Trên bảng chữ cái W = {if, then, else, a, b, c, d, e, f, +, −, ∗, /, =, ≠}, ta có các từα = if a + b = c then c∗d = e và β = else c/d = f , còn αβ là từ: if a + b = c then c∗d e else c/d = f
2 Cho Σ = {a, b, c}, khi đó: Từω = abcbcb chứa 2 vị trí của bcb, đó là a*bcb*cb và abc*bcb*, θ = bcb là một từ con của ω Từ ω chứa một vị trí của ký hiệu a, đó là
3 Từω = 010111001 trên bảng chữcái {0, 1} có độ dài 9, trong đó 0101 là tiền tố và 11001 là hậu tố của ω
1.2.2 Phép l ấ y t ừ ngượ c Định nghĩa 2.2 Giả sử có từ khác rỗng ω = a 1 a 2 …am trên bảng chữ cái Σ, khi đó từ a m a m-1 …a2 a 1 được gọi là từngược (hay từsoi gương) của từω, và được ký hiệu là Khi ω = ε ta quy ước ε R = ε.
Nh ậ n xét: Dễ thấy rằng phép lấy từngược có các tính chất sau:
1.Cho các từ α = 100110 và β = aabb trên bảng chữ cái {0,1,a,b}, theo định nghĩa ta có: α R = 011001 và (α R ) R = (011001) R = 100110 = α β R = bbaa và (β R ) R = (bbaa) R = aabb = β
2.Cho các từ happy và oto trên bảng chữcái ∑ = {a, b, c, …x, y, z}, khi đó ta có:
(happy) R = yppah và (oto) R = oto Ngoài ra ta có: | (happy) R | = | yppah| = | happy | = 3
Phép toán ngắt bỏ phần đầu hoặc phần cuối của một từ được gọi là phép chia Cụ thể, phép chia trái của từ α cho từ β, ký hiệu là β \ α, cho kết quả là phần còn lại của từ α sau khi loại bỏ phần đầu β Tương tự, phép chia phải của từ α cho từ γ, ký hiệu là α / γ, cho kết quả là phần còn lại của từ α sau khi cắt bỏ phần cuối γ.
Nh ậ n xét: Dễ thấy rằng các phép chia từ có tính chất sau:
Trong phép chia trái giữa hai từ, từ β phải là tiền tố của từ α, trong khi đó, trong phép chia phải, từ γ phải là hậu tố của từ α.
Chứng minh các kết quả trên là khá dễdàng, xin dành cho sinh viên như là bài tập
Ví d ụ 2.3 Cho các từα = abcaabbcc, β = abc, γ = bcc trên bảng chữ cái ∑ = {a, b, c}, khi đó ta có:
Các phép toán trên ngôn ng ữ
Các họ ngôn ngữ cụ thể được xác định qua các phép toán trên ngôn ngữ, bao gồm việc tổ hợp từ các ngôn ngữ đã cho Mỗi ngôn ngữ được xem như một tập hợp, vì vậy có thể áp dụng các phép toán đại số tập hợp như phép giao, phép hợp, phép hiệu và phép lấy bù Ví dụ, nếu L1 và L2 là hai ngôn ngữ trên bảng chữ cái Σ, ta có thể tạo ra các ngôn ngữ mới như L1 ∪ L2 và L1 ∩ L2 trên bảng chữ cái này.
Dưới đây chúng ta sẽ trình bày các phép toán trên ngôn ngữ
1.3.1 Phép h ợ p Định nghĩa 3.1 Hợp của hai ngôn ngữ L 1 và L 2 trên bảng chữ cái ∑, ký hiệu L 1 ∪
L 2 , là một ngôn ngữ trên bảng chũ cái ∑, đó là tập từ:
Phép hợp của các ngôn ngữ L1, L2, …, Ln trên bảng chữ cái Σ được định nghĩa là tập hợp các từ ω thuộc Σ* mà ω thuộc L1 hoặc ω thuộc L2.
Nh ậ n xét: Dễ dàng thấy rằng phép hợp các ngôn ngữ có các tính chất sau:
- Phép hợp hai ngôn ngữ có tính giao hoán: L1∪ L 2 = L 2 ∪ L 1 ;
- Phép hợp các ngôn ngữ có tính kết hợp: (L1∪ L 2 ) ∪ L 3 = L 1 ∪ ( L 2 ∪ L 3 );
- Với mọi ngôn ngữL trên Σ thì: L ∪∅ = ∅ ∪ L = L và L ∪Σ * = Σ *
Chứng minh các kết quả trên là khá dễ dàng, xin dành cho sinh viên như là bài tập
1.3.2 Phép giao Định nghĩa 3.2 Giao của hai ngôn ngữ L 1 và L 2 trên bảng chữ cái ∑, ký hiệu
L 1 ∩ L 2 , là một ngôn ngữ trên bảng chữ cái ∑, đó là tập từ:
Phép giao của các ngôn ngữ L1, L2, …, Ln trên bảng chữ cái Σ được định nghĩa là tập hợp các chuỗi ω thuộc Σ* sao cho ω đồng thời thuộc cả L1 và L2 Điều này cho phép mở rộng phép giao cho một số hữu hạn các ngôn ngữ.
Nh ậ n xét: Dễ dàng thấy ràng, phép giao các ngôn ngữ có tính chất sau:
- Phép giao hai ngôn ngữ có tính giao hoán: L 1 ∩ L2 = L 2 ∩ L1;
- Phép giao các ngôn ngữ có tính kết hợp: (L 1 ∩ L2) ∩ L3 = L 1 ∩ ( L2∩ L3);
- Phép giao các ngôn ngữ có tính phân phối đối với phép hợp:
- Với mọi ngôn ngữL trên Σ thì: L ∩ ∅ = ∅∩ L = ∅và L ∩ Σ * = L
Chứng minh các kết quả trên là khá dễdàng, xin dành cho sinh viên như là bài tập
1.3.3 Phép l ấ y ph ầ n bù Định nghĩa 3.3 Ngôn ngữ phần bù của ngôn ngữ L trên bảng chữ cái Σ, ký hiệu
C Σ L (hay đơn giản là CL, nếu không gây nhầm lẫn), là một ngôn ngữ trên bảng chữ cái
Nh ậ n xét: Dễ dàng thấy rằng phép lấy phần bù các ngôn ngữ có các tính chất sau:
Chứng minh các kết quả trên là khá dễdàng, xin dành cho sinh viên như là bài tập
1 Cho ngôn ngữ L 1 = {ε, 0, 01}, L2 = {ε, 01, 10} trên bảng chữ cái Σ = {0, 1}, khi đó ta có: L1∪ L 2 = {ε, 0, 01, 10}.
2 Cho ngôn ngữL = {ω ∈∑*, với | ω | là một số chẵn}, khi đó ta có:
C Σ L = {ω ∈ ∑ + , với | ω | là một số lẻ}
1.3.4 Phép nhân ghép Định nghĩa 3.4 Cho hai ngôn ngữ L 1 trên bảng chữ Σ1 và L 2 trên bảng chữ Σ2
Nhân ghép hay tích của hai ngôn ngữ L 1 và L 2 là một ngôn ngữ trên bảng chữΣ1 ∪Σ2, ký hiệu L 1 L 2 , đuợc xác định bởi:
Nh ậ n xét: Dễ dàng nhận thấy phép nhân ghép (tích) các ngôn ngữ có các tính chất sau:
- Phép nhân ghép có tính kết hợp: với mọi ngôn ngữ L 1 , L 2 và L 3 , ta có:
- Phép nhân ghép có tính phân phối đối với phép hợp, nghĩa là:
Phép nhân ghép không phân phối đối với phép giao, và phép hợp cùng phép giao cũng không phân phối đối với phép nhân ghép Điều này được thể hiện qua các ví dụ trong ngữ cảnh của các ngôn ngữ L1, L2 và L3.
Ví dụ 3.2 minh họa rằng phép nhân ghép không phân phối đối với phép giao Cụ thể, phép hợp và phép giao cũng không có tính phân phối đối với phép nhân ghép.
Xét các ngôn ngữ L 1 = {0, 01}, L 2 = {01, 10}, L 3 = {0} trên bảng chữcái Σ = {0, 1}.
1 Có thể kiểm tra được rằng phép nhân ghép không có tính phân phối đối với phép giao:
Mặt khác, ta có: L 1 L 2 = {001, 010, 0101, 0110} và L 1 L 3 = {00, 010}, do đó:
Vậy L1(L2 ∩ L3) ≠ (L1L2) ∩ (L1L3), tức là phép nhân ghép không có tính phân phối đối với phép giao
2 Kiểm tra tính phân phối của phép hợp, phép giao đối với phép nhân ghép:
Mặt khác, ta cũng có: L 1 ∪ L 2 = {0, 01, 10} và L 1 ∪ L 3 = {0, 01}, do đó:
Vậy: L 1 ∪ (L 2 L 3 ) ≠ (L1 ∪ L 2 )(L 1 ∪ L 3 ), tức là phép hợp không có tính phân phối đối với phép nhân ghép
Tương tự, đối với phép giao, ta có: L 2 L 3 = {010, 100}, do đó:
Vậy: L 1 ∩ (L2L 3 ) ≠ (L1∩ L2)(L 1 ∩ L3) Tức là phép giao không có tính phân phối đối với phép nhân ghép
Vì phép ghép ngôn ngữ có tính kết hợp nên ký hiệu L n được dùng với mọi ngôn ngữ L và số tự nhiên n theo nghĩa quen thuộc sau:
1.3.5 Phép l ặ p Định nghĩa 3.5 Cho ngôn ngữ L trên bảng chữ cái Σ, khiđó:
* + ∪ ∪ ∪ ∪ ∪ ⋃ Được gọi là ngôn ngữ lặp của ngôn ngữ L (hay bao đóng ghép của ngôn ngữ L), ký hiệu L *
Vậy ngôn ngữ lặp của L là hợp của mọi luỹ thừa của L:
∪ ∪ ∪ ∪ ⋃ Được gọi là ngôn ngữ lặp cắt của ngôn ngữ L, ký hiệu L +
Vậy ngôn ngữ lặp cắt của L là hợp của mọi luỹ thừa dương của L:
1.Xét ngôn ngữ L = {0, 1} trên bảng chữ Σ = {0, 1} Ta có:
L 2 = {00, 01, 10, 11}, tập hợp các xâu nhịphân độ dài 2;
L 3 = {000, 001, 010, 011, 100, 101, 110, 111}, tập hợp các xâu nhịphân độ dài 3 Tương tự, L n là tập hợp các xâu nhịphân độ dài n
Vì vậy, L * là tập hợp tất cả các xâu nhị phân
2.Xét hai ngôn ngữ trên bảng chữ Σ = {a}:
1.3.6 Phép l ấ y ngôn ng ữ ngượ c Định nghĩa 3.6 Cho ngôn ngữ L trên bảng chữ cái Σ, khi đó ngôn ngữ ngược của L là một ngôn ngữ trên bảng chữ cái ∑, được ký hiệu là L R hay L ^ , là tập từ:
Nh ậ n xét: Dễ dàng thấy rằng phép lấy ngôn ngữngược có các tính chất sau:
Ví d ụ 3.4 Cho L = {ε, ab, abc, cbaa} là một ngôn ngữ trên bảng chữ cái Σ = {a, b, c}, khi đó L R = {ε, ba, cba, aabc} là ngôn ngữngược của L
1.3.7 Phép chia ngôn ng ữ Định nghĩa 3.7 Cho ngôn ngữ X và Y trên bảng chữ cái Σ, khi đó thương bên trái của ngôn ngữ X cho ngôn ngữ Y là một ngôn ngữtrên ∑, được ký hiệu là Y \ X , là tập từ:
Thương của ngôn ngữ X cho ngôn ngữ Y, ký hiệu là X / Y, được định nghĩa là tập hợp các chuỗi z thuộc Σ* sao cho tồn tại x thuộc X và y thuộc Y với x có thể được biểu diễn dưới dạng yz.
Nh ậ n xét: Dễ dàng thấy rằng phép chia ngôn ngữ có các tính chất sau:
Chứng minh các kết quả trên là khá dễ dàng, xin dành cho sinh viên như là bài tập
Ví d ụ 3.5 Cho X = {a, b, abc, cab, bcaa} và Y = {ε, c, ab} là các ngôn ngữ trên bảng chữ cái Σ= {a, b, c}, khi đó:
Văn phạ m và ngôn ng ữ sinh b ởi văn phạ m
Văn phạm có thể được xem như một "thiết bị tự động" có khả năng tạo ra một tập hợp từ dựa trên một bảng chữ cái nhất định Mỗi từ được sinh ra thông qua một chuỗi bước hữu hạn, tuân theo các quy tắc của văn phạm.
Việc xác định một ngôn ngữ trên bảng chữ cái cho trước có thể được thực hiện bằng một trong các cách thức sau:
Để tạo ra từ ngữ trong ngôn ngữ đã cho, chúng ta có thể thiết lập một quy trình hoạt động cho “thiết bị tự động”, cho phép nó dừng lại và sinh ra từ sau một số bước nhất định.
- Cách 2 “Thiết bị tựđộng” có khảnăng lần lượt sinh ra tất cả các từ trong ngôn ngữđã cho;
Trong lý thuyết văn phạm, có ba phương pháp để xác định xem một từ ω có thuộc ngôn ngữ đã cho hay không, và các phương pháp này được chứng minh là tương đương Chúng ta sẽ tập trung vào phương pháp đầu tiên, coi văn phạm như một “thiết bị tự động” sinh ra các từ Do đó, các “thiết bị tự động” này còn được gọi là văn phạm sinh.
Việc tạo ra từ ngữ có thể diễn ra qua nhiều phương pháp khác nhau, bao gồm việc sử dụng ngữ pháp, các máy tự động, và các mô hình hình thức như máy Turing Trong bài viết này, chúng ta sẽ tập trung vào lý thuyết của Noam Chomsky được phát triển trong giai đoạn 1956-1957.
1 4.1 Định nghĩa văn phạ m Định nghĩa 4.1 Văn phạm G là một bộ sắp thứ tự gồm 4 thành phần:
Σ là một bảng chữ cái cơ bản, được biết đến với tên gọi bảng chữ cái kết thúc, trong đó mỗi phần tử được gọi là ký hiệu kết thúc hoặc ký hiệu cơ bản.
Bảng ký hiệu phụ, hay còn gọi là bảng chữ cái không kết thúc, là một tập hợp ký tự trong đó ∩ Σ = ∅ Mỗi phần tử trong bảng này được gọi là ký hiệu không kết thúc hoặc ký hiệu phụ.
- S ∈ được gọi là ký hiệu xuất phát hay tiên đề;
P là tập hợp các quy tắc sinh có dạng α→ β, trong đó α được gọi là vế trái và β là vế phải của quy tắc Cả α và β đều thuộc tập hợp (Σ∪ ) *, và α phải chứa ít nhất một ký hiệu không kết thúc.
Trong ngữ cảnh của ngôn ngữ Σ = {0,1} và tập hợp các ký hiệu {S, A, B}, các quy tắc như S → 0S1A, 0AB → 1A1B, và A → ε được coi là hợp lệ vì vế trái của chúng luôn chứa ít nhất một ký hiệu phụ thuộc Ngược lại, các quy tắc như 0 → A và 01 → 0B không đáp ứng tiêu chí này và do đó được xem là không hợp lệ.
4 G 4 = , trong đó: Σ = {tôi, anh, chị, ăn, uống, cơm, phở, sữa, café}
= {, , , , , , }
P = {→, →tôi, →anh, →chị,
→, →, →ăn,
→uống, →cơm, →phở, →sữa,
Chú ý rằng nếu các quy tắc có vế trái giống nhau, chúng ta có thể viết gọn lại Ví dụ, hai quy tắc α→ β và α→ γ có thể được tổng hợp thành α→ β | γ Cụ thể, trong văn phạm G1 ở ví dụ 4.1, hai quy tắc có thể được diễn đạt là S→0S1 | ε.
1.4.2 Ngôn ng ữ sinh b ởi văn phạ m Định nghĩa 4.2 Cho văn phạm G = < Σ, , S, P > và η, ω ∈ (Σ ∪ ) * Ta nói ω được suy dẫn trực tiếp từη trong G, ký hiệu η├ G ω hay ngắn gọn là η├ω (nếu không sợ nhầm lẫn), nếu tồn tại quy tắc α→β∈ P và γ, δ∈ (Σ ∪ ) * sao cho η = γαδ, ω = γβδ. Điều này có nghĩa là nếu η nhận vếtrái α của quy tắc α→β như là từ con thì ta thay α bằng β đểđược từ mới ω. Định nghĩa 4.3 Cho văn phạm G = < Σ, , S, P > và η, ω∈(Σ ∪ )* Ta nói ω được suy dẫn từ η trong G, ký hiệu η╞ G ω hay ngắn gọn là η╞ ω (nếu không sợ nhầm lẫn), nếu η = ω hoặc tồn tại một dãy D = ω0, ω1, …, ωk ∈ (Σ ∪ )* sao cho ω0= η, ω k
Dãy D = ω0, ω1,…, ωk được xác định là một dẫn xuất của ω từ η trong G, với k là độ dài của dẫn xuất Khi ω0 = S và ωk thuộc Σ*, dãy D được coi là dẫn xuất đầy đủ.
Nếu chuỗi ωi được tạo ra từ chuỗi ωi-1 thông qua việc áp dụng một quy tắc p trong văn phạm G, thì quy tắc p được coi là đã được áp dụng ở bước thứ i Theo định nghĩa 4.4, một văn phạm G được biểu diễn dưới dạng G = < Σ, , S, P > Một chuỗi ω thuộc tập Σ* được gọi là sinh ra bởi văn phạm G nếu có sự suy dẫn từ S đến ω, ký hiệu là S╞ ω Ngôn ngữ sinh ra bởi văn phạm G, ký hiệu là L(G), bao gồm tất cả các chuỗi được sinh ra từ văn phạm G.
L(G) = {ω∈Σ * | S ╞ G ω} Định nghĩa 4.5 Hai vă n phạm G 1 = < Σ1, 1 , S 1 , P 1 > và G 2 = < Σ2, 2, S 2 , P 2 > được gọi là tương đương nếu L(G 1 ) = L(G 2 )
1 Xét văn phạm G 1 trong ví dụ 4.1 Từ ω = 00001111 được suy dẫn từ S bằng dãy dẫn xuất độ dài 5: S├ 0S1├ 00S11├ 000S111├ 0000S1111 ├ 00001111 (có thể viết ngắn gọn là ω = 0 4 1 4 )
Bằng việc sử dụng n lần (n ≥ 0) quy tắc 1 rồi quy tắc 2, ta có: S╞ 0 n 1 n
2 Xét văn phạm G 2 trong ví dụ 4.1 Sử dụng quy tắc 1, rồi n lần (n ≥ 0) quy tắc
2, sau đó quy tắc 3 để kết thúc, ta có: S├ Ab╞ a n Ab n b├ a n b n+1
3 Xét văn phạm G 3 trong ví dụ 4.1 Sử dụng quy tắc 1, rồi m -1 lần (m ≥ 1) quy tắc 2, n-1 lần (n ≥ 1) quy tắc 3, k-1 lần (k ≥ 1) quy tắc 4 (các quy tắc có thể xen kẻ), sau đó kết thúc bởi các quy tắc 5, 6, 7, ta có: S ├ ABC ╞ a m Ab n Bc k C ╞ a m b n c k
Tập hợp L(G4) bao gồm các câu sau: "tôi ăn cơm", "anh ăn cơm", "chị ăn cơm", "tôi ăn phở", "anh ăn phở", "chị ăn phở", "tôi uống sữa", "anh uống sữa", "chị uống sữa", "tôi uống café", "anh uống café", và "chị uống café".
Ta có thể biểu diễn việc dẫn xuất từ đến một từ trong L(G 4 ), chẳng hạn
Câu "tôi ăn cơm" có thể được biểu diễn bằng cây dẫn xuất hay cây phân tích cú pháp Theo quan điểm phân tích cú pháp thực tế, quy tắc được xem xét từ phải qua trái, nghĩa là cây này được xử lý từ dưới lên trên thay vì từ trên xuống dưới.
Hình 1.1 Cây dẫn xuất cho ví dụ 4.2
Ví d ụ 4.3 Cho hai văn phạm G3= , G 4 =
Các tính ch ấ t c ủa văn phạ m và ngôn ng ữ sinh b ởi văn phạ m
1.5.1 M ộ t s ố tính ch ấ t c ủa văn phạ m và d ẫ n xu ấ t
Trong phần này, chúng ta sẽ khám phá những tính chất quan trọng của các dẫn xuất và văn phạm Định lý 5.1 khẳng định rằng, với mọi văn phạm G = < Σ, Δ, S, P >, luôn tồn tại một văn phạm G’ tương ứng.
= < Σ’,Δ’,S’, P’ > tương đương với văn phạm G, tức là L(G) = L(G’).
Giả sử có một văn phạm G = < Σ, Δ, S, P >, ta có thể xây dựng một văn phạm G’ = < Σ’, Δ’, S’, P’ > với Σ’ = Σ và bổ sung các ký hiệu đối ngẫu ̅ cho mỗi a ∈ Σ, trong đó Г = { ̅ | a ∈ Σ} Ta có Δ’ = Δ ∪ Г, S’ = S, và P’ = P1 ∪ P2, với P1 = { ̅→ a | ∀a ∈ Σ} và P2 = { ̅→ ̅ | ∀α→β ∈ P }, trong đó ̅ và ̅ là các xâu α và β đã được thay các ký hiệu thuộc Σ bằng các ký hiệu đối ngẫu của chúng Điều này cho thấy rằng L(G) = L(G’).
Chúng ta sẽ chứng minh rằng L(G) ⊆ L(G’) Đối với bất kỳ ω ∈ L(G), có S ╞ G ω, tức là tồn tại một dãy suy dẫn trực tiếp trong G: S = ω0├ G ω1├ G … ├ G ωk = ω Trong dãy suy dẫn này, chúng ta thay thế mọi quy tắc trong các suy dẫn ωi ├ G ωi+1 (với 0 ≤ i ≤ k-1) bằng các quy tắc tương ứng trong P1 và P2, từ đó nhận được dãy suy dẫn trong G’: S = ω’0├ G’ ω’1.
Để chứng minh rằng L(G) ⊆ L(G’), ta có S╞ G’ ω, tức là ω ∈ L(G’) Ngược lại, để chứng minh L(G’) ⊆ L(G), giả sử ω ∈ L(G’), từ đó ta có một dãy suy dẫn trong G’: S = ω’0├ G’ ω’1 ├ G’ … ├ G’ ω’k = ω Trong các suy dẫn ωi├ G’ ωi+1, ta thay mọi ký hiệu ̅∈ Г bằng các ký hiệu tương ứng a ∈ Σ1, do đó mọi quy tắc đều thuộc P Kết quả là ta nhận được dãy suy dẫn trực tiếp trong G: S ω0├ G ω1├ G … ├ G ωk= ω, dẫn đến S╞ G ω, tức là ω ∈ L(G) Như vậy, ta có L(G’) ⊆ L(G).
Ví d ụ 5.1 Cho văn phạm G 1 = , ta có thể xây dựng G2 tương đương với G1 như sau:
Dễdàng có được L(G 1 ) = L(G 2 ) = {a n b n | n ≥ 1}, hay G1 và G 2 là tương đương.
Mỗi văn phạm G cho phép chúng ta thay thế các quy tắc chứa ký hiệu xuất phát ở vế phải, từ đó tạo ra một văn phạm tương đương Điều này được thực hiện nhờ vào bổ đề liên quan đến quy tắc thay thế trong lý thuyết ngôn ngữ hình thức.
Trong văn phạm G = < Σ, Δ, S, P >, nếu trong tập quy tắc P tồn tại quy tắc có ký hiệu xuất phát S ở vế phải, thì có thể xây dựng một văn phạm G’ tương đương với G mà không chứa ký hiệu xuất phát ở vế phải trong các quy tắc của nó.
Lấy S’∉Σ ∪, xét văn phạ m G’ = , trong đó P’ = P ∪{S’→α | S→α ∈ P} Rõ ràng trong P’ không chứa quy tắc nào có S’ ở vế phải
Ta chứng minh: L(G) = L(G’). a./ Lấy ω∈L(G): Khi đó ta có S╞ G ω, giả sử dãy dẫn xuất trong G của ωlà S ├ α
Vì S├ G α nên S’→α∈P, dẫn đến S’├ G’ α╞ G’ ω Do P ⊂ P’, ta có S’╞ G’ ω, tức là ω∈L(G’), cho thấy L(G) ⊆ L(G’) Khi ω∈L(G’), ta có S’╞ G’ ω và giả sử dãy dẫn xuất trong G’ là S’├ G’ α ╞ G’ ω Vì S’├ G’ α, nên S’→α ∈ P, từ đó tồn tại S→α ∈ P Hơn nữa, trong α không chứa S’, vì vậy các suy dẫn trực tiếp trong α╞ G’ ω chỉ sử dụng các quy tắc của P.
Vậy ta có S ╞ G ω hay ω∈ L(G), vậy L(G’) ⊆ L(G)
Mỗi văn phạm G cho phép ta thay thế các quy tắc có ký hiệu cơ bản ở vế trái, từ đó tạo ra một văn phạm tương đương không chứa ký hiệu cơ bản ở vế trái của các quy tắc.
Bằng cách xây dựng một văn phạm G' tương đương với văn phạm G = < Σ, Δ , S, P >, chúng ta có thể đảm bảo rằng tất cả các quy tắc trong G' đều không chứa ký hiệu cơ bản ở vế trái Điều này cho phép tối ưu hóa cấu trúc của văn phạm mà vẫn giữ nguyên ý nghĩa và khả năng sinh của nó.
Giả sử có văn phạm G = < Σ, Δ, S, P >, với mỗi ký hiệu cơ bản a xuất hiện trong vế trái của một quy tắc, ta bổ sung một ký hiệu ̅∉ Σ ∪ Δ, gọi là đối ngẫu của a Đặt Г = { ̅ | a ∈ Σ, a xuất hiện ở vế trái quy tắc nào đó}.
Văn phạm G’ được xây dựng dưới dạng G’ = < Σ’, Δ’, S’, P’ >, trong đó Σ’ = Σ, Δ’ = Δ ∪ Г, S’ = S, và P’ = P 1 ∪ P 2 Tập P 2 được định nghĩa là { ̅→ ̅ | ∀ ̅→ ̅∈ P }, với β là các xâu α và β đã được thay thế các ký hiệu a ∈ Σ xuất hiện ở vế trái của một quy tắc nào đó bằng các ký hiệu đối ngẫu ̅ của chúng.
Văn phạm G’ tương đương với văn phạm G theo định lý 5.1, và trong cấu trúc của G’, tất cả các vế trái sẽ không chứa ký hiệu cơ bản.
Trong bài viết này, chúng tôi trình bày hai khái niệm về dẫn xuất trong văn phạm G = < Σ, Δ, S, P > Định nghĩa đầu tiên cho rằng hai dãy dẫn xuất D = ω0, ω1, …, ωk và D’ = ω’0, ω’1, …, ω’m được coi là đồng lực nếu ω0 = ω’0 và ωk = ω’m Định nghĩa thứ hai chỉ ra rằng dẫn xuất D là không lặp nếu không tồn tại cặp (ωi, ωj) với i khác j.
≠ j mà ωi = ωj Đị nh lý 5.2 Với mọi dẫn xuất trong văn phạm G tùy ý, luôn luôn tồn tại một dẫn xuất không lặp và đồng lực với nó
Giả sử D = ω0, ω1, …, ωi-1, ωi, ωi+1, …, ωm, có hai trường hợp cần xem xét Thứ nhất, nếu trong D không tồn tại cặp (ωi, ωj) với i ≠ j mà ωi = ωj, thì D là dẫn xuất không lặp và đồng lực với chính nó Thứ hai, nếu có cặp (ωi, ωj) với i ≠ j mà ωi = ωj, ta sẽ tạo dẫn xuất D’ = ω0, ω1, …, ωi-1, ωj, ωj+1, …, ωm, điều này cho thấy D’ cũng là dẫn xuất không lặp và đồng lực với D Quá trình này sẽ tiếp tục cho đến khi mọi xâu trong D là khác nhau từng đôi một, từ đó tạo ra một dẫn xuất mới không lặp và đồng lực với dẫn xuất ban đầu.
1.5.2 Tính đóng củ a l ớ p ngôn ng ữ sinh b ởi văn phạ m
Giả sử L1 và L2 là hai ngôn ngữ được sinh ra bởi văn phạm, và "o" là một phép toán trên các ngôn ngữ như phép hợp, phép giao, hay phép lấy ngôn ngữ bù Nếu ngôn ngữ L1 o L2 cũng được sinh ra từ một văn phạm, thì lớp ngôn ngữ do văn phạm sinh ra được coi là đóng đối với phép toán o.
OTOMAT HỮ U H Ạ N VÀ NGÔN NG Ữ CHÍNH QUY
Otomat hữu hạn đơn định
Otomat hữu hạn là một mô hình tính toán với kích thước cố định và không thể mở rộng trong suốt quá trình tính toán Các loại otomat khác, được nghiên cứu sau này, có khả năng lưu trữ thông tin với bộ nhớ vô hạn Sự phân biệt giữa các loại otomat chủ yếu dựa trên cách thức thông tin được đưa vào bộ nhớ.
Một otomat hữu hạn hoạt động trong thời gian rời rạc, tương tự như các mô hình tính toán khác Do đó, có thể xác định thời điểm "kế tiếp" khi mô tả hoạt động của một otomat hữu hạn.
Trong trường hợp đơn giản nhất, thiết bị không có bộ nhớ và thông tin đầu ra chỉ phụ thuộc vào thông tin đầu vào tại thời điểm đó Các thiết bị này được coi là mô hình của các mạch tổ hợp.
Thông tin được sinh ra bởi một otomat hữu hạn không chỉ phụ thuộc vào thông tin đầu vào hiện tại mà còn liên quan đến các thông tin đầu vào trước đó Điều này cho thấy otomat có khả năng ghi nhớ một phần thông tin từ quá khứ của nó.
Mỗi otomat có một số trạng thái hữu hạn được lưu trữ trong bộ nhớ nội bộ Tại mỗi thời điểm i, otomat sẽ ở một trong các trạng thái đó, ký hiệu là qi Trạng thái kế tiếp qi+1 tại thời điểm sau được xác định bởi trạng thái hiện tại qi và thông tin đầu vào ai tại thời điểm i Thông tin đầu ra tại thời điểm i được xác định bởi trạng thái qi, hoặc có thể dựa vào cả ai và qi.
2.1.1 Otomat h ữ u h ạn đơn đị nh Định nghĩa 1.1 Một otomat hữu hạn đơn định (Deterministic Finite Automata- DFA) là một bộnăm:
+ Q là một tập hữu hạn khác rỗng, được gọi là tập các trạng thái;
+ Σ là một bảng chữ cái, được gọi là bảng chữ vào;
+ δ: D → Q, là một ánh xạ từ D vào Q, trong đó D ⊆ Q × Σ, được gọi là hàm chuyển trạng thái (hay hàm chuyển);
+ q 0 ∈Q, được gọi là trạng thái khởi đầu;
+ F ⊆Q được gọi là tập các trạng thái kết thúc
Trong trường hợp D = Q × Σ , ta nói A là otomat đầy đủ Sau này ta sẽ thấy rằng mọi otomat hữu hạn đều đưa vềđược otomat hữu hạn đầy đủtương đương.
Hoạt động của otomat hữu hạn đơn định A = khi cho xâu vào ω
= a 1 a 2 … an có thểđược mô tảnhư sau:
Khi bắt đầu làm việc, otomat khởi động ở trạng thái q0 và đầu đọc quét ô có ký hiệu a1 Từ trạng thái q0, otomat chuyển sang trạng thái mới q1 thông qua ký hiệu a1, theo hàm chuyển δ(q0, a1) = q1, và đầu đọc di chuyển sang ô có ký hiệu a2 Tiếp theo, otomat tiếp tục chuyển từ trạng thái q1 sang trạng thái q2 bằng hàm chuyển δ(q1, a2) Quá trình này sẽ tiếp diễn cho đến khi gặp một trong các tình huống nhất định.
- Otomat A đọc hết xâu vào ω và δ(q n-1 ,a n ) = q n ∈ F, ta nói rằng A đoán nhận xâu ω;
- Hoặc otomat A đọc hết xâu vào ω và δ(q n-1 ,a n ) = q n ∉ F, ta nói A không đoán nhận xâu ω;
- Hoặc khi otomat A đọc đến aj , (j ≤ n) và hàm δ(qj-1, a j ) không xác định, ta cũng nói A không đoán nhận xâu ω
Hình 2.1 Mô tảquá trình đoán nhận xâu ω của otomat A
2.1.2 Bi ể u di ễ n otomat h ữ u h ạn đơn đị nh
Hàm chuyển trạng thái đóng vai trò quan trọng trong việc xác định chức năng của một otomat hữu hạn đơn định Để mô tả một otomat, người ta thường sử dụng hàm chuyển trạng thái, có thể được trình bày dưới dạng bảng chuyển hoặc đồ thị chuyển.
- Cho otomat b ằ ng b ả ng chuy ể n:
Cho một otomat A = , với Q = {q0, q1, q2, …, qm} là tập trạng thái và bảng chữ cái Σ = {a1, a2, …, an} Hàm chuyển δ được thể hiện qua một bảng, trong đó ô tại dòng i và cột j sẽ trống nếu (qi, aj) không thuộc tập D, tức là δ(qi, aj) không xác định.
} Hình 2.2 Bảng chuyển trạng thái của otomat A
Cho bảng chuyển trạng thái, và chỉ rõ tập trạng thái kết thúc F, ta sẽ xác định được otomat A
- Cho otomat b ằng đồ th ị chuy ể n:
Cho otomat A = Hàm chuyển δ có thể cho bằng một đa đồ thị có hướng, có khuyên G sau đây, được gọi là đồ thị chuyển của otomat A Tập đỉnh của
Trong đồ thị chuyển, các đỉnh được gán nhãn bởi các phần tử thuộc tập Q, trong khi các cung được gán nhãn bởi các phần tử thuộc tập Σ Cụ thể, nếu a ∈ Σ và trạng thái q chuyển sang trạng thái p theo công thức δ(q, a) = p, thì sẽ có một cung từ đỉnh q tới đỉnh p được gán nhãn a Đỉnh vào của đồ thị tương ứng với trạng thái ban đầu q0, được thể hiện bằng một mũi tên đi vào Các đỉnh được khoanh bởi các vòng tròn, trong đó đỉnh kết thúc được phân biệt bằng vòng tròn đậm hoặc hình vuông.
Nói chung, với việc cho đồ thị chuyển là hoàn toàn xác định được otomat A
Ví d ụ 2.1 Cho hai otomat hữu hạn đơnđịnh:
Với δ(q0, a) = q 0 , δ(q0, b) = q 1, δ(q1, a) = q 0 , δ(q1, b) = q 2 , δ(q2, a) = q 2 , δ(q2, b) q 2 Ta có bảng chuyển trạng thái và đồ thị chuyển trạng thái của otomat A 1 như sau:
Hình 2.3 Bảng chuyển trạng thái của A 1
Hình 2.4 Đồ thị chuyển trạng thái của A 1
Dãy trạng thái của otomat A1 trong quá trình đoán nhận xâu vào α = ababbab là:
Hình 2.5 Quá trình đoán nhận xâu α = ababbab của A 1
Như vậy, xâu α được đoán nhận bởi otomat A 1
Ta có bảng chuyển trạng thái và đồ thị chuyển trạng thái của otomat A2 được cho trong hình 3.6 và 3.7:
Hình 2.6 Bảng chuyển trạng thái của A 2
Hình 2.7 Đồ thị chuyển trạng thái của A 1
Dãy trạng thái của otomat A 2 trong quá trình đoán nhận xâu vào β = 1010100 là:
Hình 2.8 Quá trình đoán nhận xâu vào β = 1010100
Như vậy, otomat A 2 không chấp nhận xâu β.
Ta có thể mô tả quá trình đoán nhận xâu vào của otomat hữu hạn đơn định đầy đủ A bằng thuật toán mô phỏng sau:
- Một xâu ω, kết thúc bởi ký hiệu kết thúc file là eof;
- Một otomat hữu hạn đơn định đầy đủ A với trạng thái đầu q0 và tập trạng thái kết thúc là F
- Trả lời “Đúng” nếu A đoán nhận xâu ω;
- Trả lời “Sai” nếu A không đoán nhận xâu ω
C:= ký hiệu tiếp theo; While C < > eof do begin
C:= ký hiệu tiếp theo; end; if S in F return (True) else return (False);
2.1.3 Ngôn ng ữ được đoán nhậ n b ởi otomat đơn đị nh Để mô tả hình thức quá trình đoán nhận một từ (xâu vào), người ta đưa vào ánh xạ mở rộng δ ’ từ D ⊆ Q × Σ * vào Q như trong định nghĩa sau: Định nghĩa 1.2 Cho otomat hữu hạn đơnđịnh A = Mở rộng δ ’ của δ là một ánh xạ từ D ⊆Q × Σ * vào Q được xác định như sau:
2 δ ’ (q, ωa) = δ(δ ’ (q, ω), a), ∀a∈Σ, ∀q∈Q, ∀ω ∈Σ * sao cho δ ’ (q, ω) được xác định Chú ý rằng, ánh xạδ chỉ khác ánh xạδ’ khi ký hiệu vào là ε, hoặc là một xâu kí hiệu vào ω, do điều kiện 2/ trên Q × Σ , ta có thể đồng nhất δ ’ với δ Nếu không cần phân biệt, từđây về sau ta viết δ thay cho δ ’ , và được hiểu là ánh xạδ trên miền Q × Σ, là ánh xạδ’ trên miền Q × Σ * Định nghĩa 1.3 Cho otomat hữu hạn đơn định A = , và một xâu ω ∈ Σ * Ta nói:
+ ω được đoán nhận bởi A nếu δ(q0, ω) ∈ F;
+ Ngôn ngữđược đoán nhận bởi otomat A và ký hiệu là T(A), là tập từ:
Trong đồ thị chuyển của A, một chuỗi ω ∈ Σ* được chấp nhận bởi A khi và chỉ khi ω là một chuỗi các nhãn tương ứng với một đường đi từ đỉnh q0 đến một trong các đỉnh kết thúc.
Cụ thể, nếu ω = a1a 2 …anthì đường đi là (q0, q 1 ,…, q k ) với cung (q i-1 , q i ) có nhãn a i (với
Tập hợp T(A) bao gồm tất cả các chuỗi được ghi lại trên các đường đi từ trạng thái khởi đầu q0 đến các đỉnh kết thúc Hai otomat hữu hạn A = và A’ = được coi là tương đương khi tập hợp chuỗi T(A) bằng với T(A’).
Ví d ụ 1.2 Cho otomat hữu hạn: A 3 = với δ(q0,0) = q 0 , δ(q0,1) = q 1 , δ(q1,0) = q 3 , δ(q1,1) = q 2 , δ(q2,0) = q 2 , δ(q2,1) = q 2 , δ(q3,1) = q 3 , δ(q4,0) = q 2 , δ(q4,1) = q 3 Đồ thị chuyển của A 3 là:
Hình 2.9 Đồ thị chuyển của otomat A 3
Trước tiên, không có đường đi từ trạng thái q0 đến trạng thái kết thúc q4, nghĩa là không có từ nào được A3 chấp nhận tại q4 Hơn nữa, không tồn tại đường đi từ q0 đến bất kỳ trạng thái kết thúc nào mà đi qua q3 Do đó, chúng ta có thể loại bỏ các trạng thái q3 và q4 mà không làm ảnh hưởng đến khả năng chấp nhận từ của otomat A3 Vì vậy, otomat A3 tương đương với otomat A4.
Trong đó: δ(q0,0) = q 0 , δ(q0,1) = q 1 , δ(q1,1) = q 2 , δ(q2,0) = q 2 , δ(q2,1) = q 2 Đồ thị chuyển của A4 được cho trong hình 3.10:
Hình 2.10 Đồ thị chuyển của otomat A 4
Ngôn ngữ được nhận bởi các otomat là tập hợp các xâu bắt đầu từ trạng thái q0 và kết thúc tại trạng thái q1 với định dạng 0^n1, trong đó n ≥ 0 Đồng thời, các xâu từ q0 đến trạng thái q2 có định dạng 0^n11ω, với n ≥ 0 và ω thuộc {0, 1}*.
B ổ đề 1.1 Cho otomat hữu hạn đơn định A = Khi đó ∀ω1, ω2 ∈ Σ*, ∀q ∈ Q sao cho δ(q, ω1ω2) xác định, ta có: δ(q, ω1ω2) = δ(δ(q, ω1), ω2)
Otomat h ữ u h ạn không đơn đị nh
2.2.1 Định nghĩa Otomat h ữ u h ạn không đơn đị nh Định nghĩa 2.1 Một otomat hữu hạn không đơn định (Nondeterministic Finite Automata-NFA) là một bộnăm:
Trong đó, Q, Σ, q0, F như trong định nghĩ a 1.1 và δ: Q × Σ → 2 Q , ở đây 2 Q (hay P(Q), là ký hiệu tập hợp các tập con của Q) gọi là ánh xạ chuyển
Rõ ràng ở đây ánh xạ δ là một hàm đa trị (hàm không đơn định), vì vậy otomat A trong định nghĩa trên đây được gọi là không đơn định
Trong trường hợp δ(q, a) xác định ∀q ∈ Q, ∀a ∈Σ, ta nói ôtômát A là đầy đủ
Trong lý thuyết tự động, nếu δ(q, a) = {p1, p2, …, pk}, thì khi otomat A ở trạng thái q gặp ký hiệu a, nó có thể chuyển đến một trong các trạng thái p1, p2, …, pk Ngược lại, nếu δ(q, a) = {p}, otomat A chỉ có thể chuyển đến trạng thái duy nhất p Trường hợp δ(q, a) không xác định (δ(q, a) = ∅), có nghĩa là khi ở trạng thái q gặp ký hiệu a, otomat A không thể chuyển đến bất kỳ trạng thái nào, tương tự như otomat hữu hạn đơn định.
Một otomat hữu hạn đơn định là một trường hợp đặc biệt của otomat hữu hạn không đơn định Hoạt động của otomat không đơn định A = khi nhận vào xâu ω = a1a2…an được mô tả như sau: Bắt đầu từ trạng thái đầu q0, đầu đọc nhìn vào ký hiệu a1 Dưới tác động của a1, otomat xác định các trạng thái tiếp theo p1, …, pk và đầu đọc chuyển sang ô tiếp theo, tức là a2 Quá trình này tiếp tục với mỗi trạng thái pi (1≤ i ≤ k) và ký hiệu a2, cho đến khi gặp một trong các tình huống kết thúc.
+Trong trường hợp tập trạng thái tiếp theo sau khi đọc a j nào đó là rỗng hoặc sau khi đọc ký hiệu a n là Q’ mà Q’∩F = ∅, ta nói rằng A không đoán nhận ω;
+Trường hợp tập trạng thái tiếp theo sau khi đọc ký hiệu a n là Q’ mà Q’∩F ≠ ∅, ta nói rằng otomat A đoán nhận ω
Một otomat hữu hạn không đơn định có thể được biểu diễn bằng bảng chuyển hoặc đồ thị chuyển, tương tự như otomat hữu hạn đơn định Khi δ(q, a) = {p1, p2, …, pk}, đồ thị chuyển sẽ có k cung từ trạng thái q đến các trạng thái p1, p2, …, pk, tất cả đều mang cùng một nhãn a.
Ví d ụ 2.1 Cho otomat hữu hạn không đơnđịnh:
Bảng chuyển trạng thái và đồ thị chuyển trạng thái của otomat A trong hình dưới:
Hình 2.11 Bảng chuyển của otomat không đơn định A
Hình 2.12 Đồ thị chuyển của otomat không đơn định A
2.2.2 Ngôn ng ữ được đoán nhậ n b ở i otomat h ữ u h ạn không đơn đị nh Định nghĩa 2.2 Cho otomat hữu hạn không đơn định A = Mở rộng của δ là ánh xạδ ’ từ tập Q × Σ * vào 2 Q được xác định như sau: δ ’ (q, ε) = {q}, ∀q ∈ Q ( ) ⋃
Trên tập hợp Q × Σ, ta có thể đồng nhất hàm chuyển trạng thái δ' với δ Do đó, tương tự như trong trường hợp của otomat hữu hạn đơn định, ký hiệu δ có thể được sử dụng thay cho δ' và được hiểu là ánh xạ δ trên miền Q × Σ, cũng như ánh xạ δ' trên Q × Σ* Định nghĩa 2.3: Cho otomat hữu hạn không đơn định A = , với ω thuộc Σ* và L là một ngôn ngữ trên Σ, chúng ta nói rằng
- ωđược đoán nhận bởi A nếu δ(q 0 , ω) ∩ F ≠ ∅;
- L được đoán nhận bởi A nếu L = {ω∈Σ * | δ(q 0 , ω) ∩ F ≠ ∅} và ký hiệu L là T(A)
Ví d ụ 2.2 Cho otomat hữu hạn không đơnđịnh:
Bảng chuyển và đồ thị chuyển của otomat A được cho trong hình 3.13 và 3.14:
Hình 2.13 Bảng chuyển của otomat A trong ví dụ 2.2
Hình 3.14 Đồ thị chuyển của otomat A trong ví dụ 2.2
Có thể kiểm tra được rằng từ ω = a n b n ∈ T(A), tuy nhiên otomat A không đoán nhận ngôn ngữ L = { a n b n | ∀n ≥ 1}.
Ngôn ngữđược đoán nhận bởi otomat A là:
2.2.3 Đơn đị nh hóa các otomat
Hai ôtômát hữu hạn A và A’ được coi là tương đương khi chúng nhận cùng một ngôn ngữ, tức là T(A) = T(A’) Điều này áp dụng cho cả ôtômát đơn định và không đơn định.
Giả sử A = là một otomat không đơn định, chúng ta có thể xây dựng một otomat đơn định và đầy đủ M tương đương với A, nghĩa là chúng nhận cùng một ngôn ngữ Quá trình xây dựng M được thực hiện thông qua thuật toán đơn định hóa otomat.
Thu ật toán đơn đị nh hóa:
Input: Otomat hữu hạn không đơnđịnh A =
Output: Otomat hữu hạn đơnđịnh M =
- Bước 1: Xây dựng hàm hai biến T: 2 Q × Σ → 2 Q thỏa mãn các điều kiện:
- Bước 2: Xác định tập trạng thái mới Q’ = {s0, s 1,… , s k | k ≤ 2 | Q | -1}:
3/ Nếu otomat A là không đầy đủ, đặt s k = ∅ và thêm vào hàm chuyển δ’ các giá trịδ’(sk, a) = s k ∀ a ∈ Σđểotomat M là otomat đầy đủ
4/ Trạng thái khởi đầu của otomat M là s 0
5/ Tập trạng thái kết thúc của otomat M là F’ = {s ∈Q’ | s ∩ F ≠ ∅ }
- Bước 3: Xác định hàm chuyển δ’: Q’ × Σ→Q’ của otomat M:
Việc chứng minh T(A) = T(M) là khá dễdàng, dành cho sinh viên như là bài tập
Cho otomat A = với hàm chuyển δ cho bởi bảng sau:
Hình 2.15 Bảng chuyển của otomat A trong thí dụ 2.3
Hãy xây dựng otomat M = đơn định và đầy đủ, tương đương với otomat A
- Trạng thái khởi đầu của M là s 0;
- Tập trạng thái kết mới: F’ = {s1, s 2 , s 3 , s 4 }
3/ Hàm chuyển mới δ’: Q’ × Σ → Q’ được xác định như sau:
Hình 2.16 Bảng chuyển của otomat đơn định M trong ví dụ 2.3
Rõ ràng otomat M = với hàm chuyển δ’ cho bởi bảng trên là otomat hữu hạn đơn định và đầy đủ Có thể thây rằng otomat M là tương đương với otomat A
Ví d ụ 2.4 Cho otomat không đơn định: A = , trong đó δ(q0, a) = {q 0 }, δ(q0, b) = {q 0 , q 1 }, δ(q1, a) = {q 0 , q 1 }, δ(q1, b) = ∅ Đồ thị chuyển của A là:
Hình 2.17 Đồ thị chuyển của otomat A trong ví dụ 2.4
Ta xây dựng otomat M = tương đương với A theo thuật toán đơn định hóa, ta có:
Ta có bảng chuyển của M:
Hình 2.18 Bảng chuyển của otomat đơn định M trong thí dụ 2.4
+ Do t 1 ∩ F = {q1} ≠ ∅ , t 2 ∩ F ={q1} ≠ ∅nên F’ = {t1, t 2 } Rõ ràng otomat M là đơn định và có đồ thị chuyển như sau:
Hình 2.19 Đồ thị chuyển của otomat M trong ví dụ 2.4
Dựa vào bảng chuyển và đồ thị chuyển của otomat M, có thể thấy rằng không tồn tại đường đi nào từ trạng thái t0 đến đỉnh kết thúc t1 Do đó, otomat M tương đương với otomat M’ có đồ thị chuyển tương ứng.
Hình 2.20 Đồ thị chuyển của otomat M’ trong ví dụ 2.4 và ta có T(A) = T(M) = T(M’) = {a n bω | n ≥ 0, ω∈{a, b} * }
2.2.4 S ự tương đương giữa otomat đơn định và otomat không đơn đị nh
Các định lý dưới đây chứng minh sự tương đương giữa otomat hữu hạn đơn định và không đơn định Theo định lý 2.1, nếu một ngôn ngữ L được nhận diện bởi một otomat hữu hạn không đơn định, thì sẽ tồn tại một otomat hữu hạn đơn định có khả năng nhận diện ngôn ngữ L đó.
Định lý này được chứng minh thông qua thuật toán đơn định hóa các otomat Theo định lý 2.2, lớp ngôn ngữ sinh ra bởi otomat hữu hạn đơn định hoàn toàn trùng khớp với lớp ngôn ngữ sinh ra bởi otomat hữu hạn không đơn định.
Chúng ta cần chứng minh rằng lớp ngôn ngữ sinh L_N được tạo ra bởi các ôtômat hữu hạn không đơn định, trong khi lớp ngôn ngữ sinh L_D được hình thành từ các ôtômat hữu hạn đơn định Mục tiêu là xác nhận rằng L_N là một lớp ngôn ngữ sinh.
= L D Ta sẽ chứng minh hai bao hàm thức:
Trong lý thuyết ngôn ngữ hình thức, ta có mối quan hệ giữa hai lớp ngôn ngữ: L N và L D, với L N ⊆ L D Giả sử L là một ngôn ngữ thuộc lớp L N, nghĩa là tồn tại một otomat không đơn định A nhận L, tức là T(A) = L Theo định lý 2.1, có một otomat đơn định M tồn tại sao cho L = T(M), từ đó suy ra rằng L thuộc lớp L D, khẳng định rằng L N là tập con của L D.
Trong lý thuyết ngôn ngữ hình thức, nếu L là một ngôn ngữ thuộc lớp L D, thì tồn tại một otomat đơn định M nhận L với T(M) = L Hàm chuyển đơn định δ(q, a) = p trong otomat đơn định có thể được coi là một trường hợp đặc biệt của hàm chuyển không đơn định δ(q, a) = {p} trong otomat không đơn định Điều này cho thấy rằng otomat đơn định là một trường hợp cụ thể của otomat không đơn định, và do đó, ngôn ngữ L cũng được nhận bởi otomat không đơn định Kết luận, ta có LD ⊆ L N và từ đó suy ra LD = L N, hoàn thành việc chứng minh định lý.
Ngôn ng ữ chính quy và bi ể u th ứ c chính quy
Trong chương trước, chúng ta đã tìm hiểu về các ngôn ngữ chính quy thông qua văn phạm chính quy Ở phần này, chúng ta sẽ định nghĩa các ngôn ngữ chính quy dựa trên các khái niệm ngôn ngữ và chứng minh rằng những định nghĩa này tương đương Bên cạnh đó, chúng ta cũng sẽ giới thiệu khái niệm về biểu thức chính quy, một công cụ quan trọng để biểu diễn các ngôn ngữ chính quy.
2.3.1 Ngôn ng ữ chính quy và bi ể u th ứ c chính quy Đị nh nghĩa 3.1 Cho bảng chữ cái Σ = {a 1 , a 2 ,…, a n }, khi đó ngôn ngữ chính quy (regular languages) được định nghĩađệquy như sau:
1 Các ngôn ngữ ∅ và {a i } (i = 1, 2,…, n) được gọi là các ngôn ngữ chính quy trên bảng chữ cái Σ
2 Nếu R và S là hai ngôn ngữ chính quy trên bảng chữ cái Σ thì R ∪ S; R.S; R + (hay S + ) là các ngôn ngữ chính quy trên bảng chữ cái Σ
3 Không có các ngôn ngữ chính quy nào khác trên bảng chữ cái Σ ngoài các ngôn ngữ chính quy được định nghĩa như trên
Định nghĩa 3.1 tương đương với định nghĩa ngôn ngữ chính quy thông qua các văn phạm chính quy, cho thấy rằng các văn phạm này có khả năng sinh ra các ngôn ngữ như ∅ và {a} Hơn nữa, lớp ngôn ngữ chính quy cũng được chứng minh là đóng đối với các phép toán hợp, nhân ghép và lặp Do đó, lớp ngôn ngữ chính quy được định nghĩa ở đây trùng khớp với lớp ngôn ngữ chính quy đã được xác định theo văn phạm.
Theo định nghĩa 3.1, ta có thể khẳng định rằng mọi ngôn ngữ chính quy trên bảng chữ cái Σ đều có thể được tạo ra từ các ngôn ngữ hữu hạn thông qua một số hữu hạn lần áp dụng các phép toán hợp, nhân ghép và phép lặp.
Các văn phạm chính quy không bao gồm các quy tắc sinh từ rỗng, tức là các quy tắc có dạng A → ε, với A là ký hiệu phụ Do đó, ngôn ngữ chính quy cũng không chứa từ rỗng ε.
Ngôn ngữ chính quy suy rộng bao gồm các ngôn ngữ chính quy có chứa từ rỗng ε, trong khi văn phạm chính quy có chứa quy tắc rỗng được gọi là văn phạm chính quy suy rộng Để diễn đạt các ngôn ngữ chính quy, ta sử dụng khái niệm biểu thức chính quy, được định nghĩa dựa trên bảng chữ cái Σ = {a1, a2, …, an}.
(regular expresions) được định nghĩađệquy như sau:
1/ ∅ và a (với a ∈ Σ) là các biểu thức chính quy trên bảng chữ cái Σ biểu diễn ngôn ngữ∅ và ngôn ngữ {a};
2/ Nếu r và s là hai biểu thức chính quy biểu diễn các ngôn ngữ chính quy R và
S trên bảng chữ cái Σ thì:
- r + s là biểu thức chính quy trên bảng chữ cái Σ biểu diễn ngôn ngữ R ∪S;
- r.s là biểu thức chính quy trên bảng chữ cái Σ biểu diễn ngôn ngữ R.S;
- r + (hay s + ) là biểu thức chính quy trên bảng chữ cái Σ biểu diễn ngôn ngữ R + (hay S + )
3/ Không có các biểu thức chính quy nào khác trên bảng chữ cái Σ ngoài các biểu thức chính quy được định nghĩa như trên.
Theo định nghĩa về ngôn ngữ chính quy và biểu thức chính quy, một ngôn ngữ trên bảng chữ cái Σ được coi là chính quy nếu và chỉ nếu nó có thể được biểu diễn bằng một biểu thức chính quy.
Biểu thức chính quy suy rộng chấp nhận ε, biểu diễn ngôn ngữ {ε}, và cho phép phép toán lặp (*) Nếu r là biểu thức chính quy biểu diễn ngôn ngữ chính quy R, thì r * sẽ là biểu thức chính quy suy rộng biểu diễn ngôn ngữ chính quy suy rộng R * Trong nhiều trường hợp, khái niệm “biểu thức chính quy” được sử dụng chung cho cả “biểu thức chính quy” và “biểu thức chính quy suy rộng”.
Trong biểu thức chính quy, có thể loại bỏ dấu ngoặc và quy tắc thứ tự thực hiện các phép toán được xác định như sau: phép lặp được thực hiện trước, tiếp theo là phép nhân ghép, và cuối cùng là phép hợp.
Nếu r, s, t là các biểu thức chính quy thì ta có các kết quả sau:
Có thể chứng minh rằng hai biểu thức chính quy ở hai vế của mỗi đẳng thức đều biểu diễn cùng một ngôn ngữ chính quy Việc chứng minh này sẽ được giao cho sinh viên như một bài tập.
Ví d ụ 3.1 Xác định ngôn ngữ chính quy được biểu diễn bởi biểu thức r (01 * +02)1
Vậy ngôn ngữ chính quy biểu diễn bởi r là:
2.3.2 S ự liên h ệ gi ữ a otomat h ữ u h ạ n và ngôn ng ữ chính quy
Trong chương trước, chúng ta đã khám phá rằng mỗi ngôn ngữ chính quy đều có một văn phạm chính quy tương ứng, và ngược lại, các ngôn ngữ được sinh ra từ văn phạm chính quy cũng chính là ngôn ngữ chính quy.
Trong phần này, chúng ta sẽ khám phá mối liên hệ giữa otomat hữu hạn và ngôn ngữ chính quy Định lý 3.3 chỉ ra rằng nếu L là một ngôn ngữ chính quy, thì sẽ tồn tại một otomat hữu hạn không đơn định A nhận diện ngôn ngữ L, tức là L = T(A).
Giả sử L là ngôn ngữ bởi văn pham chính quy G = , tức là L = L(G) Xét otomat hữu hạn không đơn định A = < Q, Σ, δ, q0, F>, trong đó:
+ Q = Δ ∪ {E}, với E là ký hiệu mới và E ∉ Σ∪ Δ;
+ F = {E} nếu quy tắc S → ε ∉ P và F = {E, S} nếu S → ε ∈ P;
• Nếu ω = ε: Trong văn phạm G có quy tắc S→ε ∈P, do đó S ∈ F Trong trường hợp này δ(S, ε) = {S} nên ε ∈ T(A)
• Nếu ω = a1a 2 …an ≠ ε: Ta có suy dẫn S├ a1A 1 ├ a1a 2 A 2 ├…├ a1a 2 …an-1A n-1 ├ a 1 …an-1a n
Do đó tồn tại dãy quy tắc S→a1A 1 , A 1 →a2A 2 ,…, A n-1 →an trong P Từđịnh nghĩa của δ, ta có A1∈ δ(S, a1), A 2 ∈ δ(A1, a 2 ),…, An-1∈ δ(An-2, a n-1 ), E ∈ δ(An-1, a n )
Như vậy: E ∈δ(S, a 1a 2 … an) hay ω ∈ T(A) Vậy L ⊆ T(A)
• Nếu ω = ε: δ(S, ε)∩F ≠ ∅ hay S∈F, vậy có quy tắc S→ε∈P, do đó ε∈ L(G);
• Nếu ω = a1a 2 …an ≠ ε: δ(S, ω)∩F ≠ ∅ với ω ≠ ε hay E ∈ δ(S, ω), do đó tồn tại các trạng thái A 1 , A 2 ,…, A n-1 ∈ sao cho A 1 ∈δ(S, a1), A 2 ∈δ(A1, a 2 ),…, An-1∈ δ(An-2, a n-
Từ đó ta có: S→a1A 1 , A 1 →a2A 2 ,…, A n-1 →an ∈ P hay trong G có một suy dẫn là S├ a1A 1 ├ a1a 2 A 2 ├ …├ a1a 2 …an-1A n-1 ├ a1…an-1a n = ω Vì vậy, ω ∈ L Hay T(A) ⊆ L
Vậy ta đã chứng minh L = T(A), tức là tồn tại một otomat hữu hạn không đơn định đoán nhận L
Ví d ụ 3.2 Cho ngôn ngữL = {ωab n ab | n ≥ 0, ω ∈ {a, b} * } Ta có L = L(G) trong đó G = là văn phạm chính quy
Xây dựng otomat hữu hạn không đơn định A = , trong đó δ(S, a) = {S, A}, δ(S, b) = {S}, δ(A, a) = {B}, δ(A, b) = {A}, δ(B, a) = ∅, δ(B, b) {E}, δ(E, a) = ∅, δ(E, b) = ∅ Đồ thị chuyển của A được cho trong hình 2.21:
Hình 2.21 Đồ thị chuyển của otomat A trong thí dụ 3.2
Theo định lý trên, otomat A đoán nhận ngôn ngữ chính quy L, thật vậy ta có:
T(A) = {ωab n ab | n ≥ 0, ω∈{a, b} * } = L Đị nh lý 3.4 Nếu L là ngôn ngữ được đoán nhận bởi một otomat hữu hạn đơn định thì L là một ngôn ngữ chính quy
Giả sử L = T(M), với M = là một otomat hữu hạn đơn định Xét văn phạm G = , trong đó P = {q→ap | δ(q, a) = p} ∪ {q→a | δ(q, a) p∈F} Khi đó G là một văn phạm chính quy
- Ta chứng minh L(G) = L, với giả thiết ε ∉ L
1 Lấy ω = a1a 2 …an∈ L(G), ω ≠ ε, trong G tồn tại suy dẫn q 0 ╞ ω hay q0├ a1q 1 ├ a 1 a 2 q 2 ├… ├ a1a 2 …an-1q n-1 ├ a1…an-1a n = ω.
Do đó: q0→a1q 1 , q 1 →a2q 2 ,…, qn-1→an-1q n-1 , q n-1 →an ∈ P hay ta có p 1 = δ(q0, a 1 ), p 2 = δ(q1, a 2 ),…, q n-1 = δ(qn-2, a n-1 ), q n ∈F
2 Lấy ω = a1a 2 …an ∈L, ω ≠ ε, khi đó tồn tại dãy trạng thái q 1 , q 2 , …, q n sao cho δ(q0, a 1 ) = p 1, δ(q1, a 2 ) = q 2 ,…, δ(qn-2, a n-1 ) = q n-1 , δ(qn-1, a n ) = q n ∈ F Do đó, trong G có các quy tắc q 0 →a1q 1 , q 1 →a2q 2 ,…, q n-1 →an-1q n-1 , q n-1 →an∈ P, ta có suy dẫn trong G: q 0
Khi ε thuộc tập hợp L, chúng ta xây dựng ngữ pháp G’ tương ứng với G, trong đó ký hiệu xuất phát không xuất hiện trong bất kỳ vế phải nào của quy tắc Đồng thời, chúng ta thêm quy tắc q0→ε vào G’ để tạo ra ngữ pháp chính quy G’ với L(G’) = L(G) ∪ {ε} Do đó, ta có L(G) = L, từ đó định lý được chứng minh.
Ví d ụ 3.3 Cho otomat hữu hạn đơn định A = , trong đó δ(q0, 0) = q 1 , δ(q1, 0) = q 2 , δ(q1, 1) = q 0 , δ(q2, 1) = q 0 Đồ thị chuyển của A là:
Hình 2.22 Đồ thị chuyển của otomat A trong thí dụ 3.3
Dễ thấy rằng T(A) = {ω00 | ω∈{01, 001} * } là ngôn ngữ chính quy
K ế t lu ậ n: Từ các đị nh lý trên ta có kết luận về sự liên hệ giữa otomat hữu hạn và ngôn ngữchính quy như sau:
1 Gọi D là lớp các ngôn ngữ được đoán nhận bởi otomat hữu hạn đơn định, N là lớp các ngôn ngữđược đoán nhận bởi otomat hữu hạn không đơn định và R là lớp các ngôn ngữ chính quy Định lý 2.1 cho biết D = N Định lý 3.3 cho biết R ⊂ N Định lý 3.4 cho biết D ⊂
2 Ngôn ngữ L là chính quy khi và chỉ khi: a Tồn tại một biểu thúc chính quy biểu diễn L; b Tồn tại một văn phạm chính quy sinh ngôn ngữ L; c Tồn tại một otomat hữu hạn đoán nhận L
Ví d ụ 3.4 Với ngôn ngữ chính quy L = {01 n , 021 | n ≥ 1}, ta có:
• Biểu thức chính quy biểu diễn L (xem ví dụ 3.2) là: r = 01*1+021
• Văn phạm chính quy sinh ngôn ngữ L:
• Otomat hữu hạn A đoán nhận L có đồ thị chuyển là:
Hình 2.23 Đồ thị chuyển của otomat A trong ví dụ 3.4
Điề u ki ệ n c ầ n c ủ a ngôn ng ữ chính quy
Ngôn ngữ được gọi là chính quy nếu nó có thể được đoán nhận bởi một otomat hữu hạn, được sinh ra từ một văn phạm chính quy, hoặc được xác định bởi một biểu thức chính quy Việc chứng minh một ngôn ngữ là chính quy khá đơn giản thông qua các phương pháp này Tuy nhiên, để khẳng định một ngôn ngữ L không phải là ngôn ngữ chính quy lại phức tạp hơn, vì việc không xây dựng được otomat hữu hạn, văn phạm chính quy hay biểu thức chính quy không đồng nghĩa với việc L không phải là ngôn ngữ chính quy Do đó, cần có một tiêu chuẩn xác định để kết luận rằng một ngôn ngữ không phải là chính quy, và tiêu chuẩn này chính là điều kiện cần của ngôn ngữ chính quy.
Trong ngôn ngữ chính quy L, có thể tồn tại nhiều otomat hữu hạn nhận diện nó Tuy nhiên, chúng ta chủ yếu quan tâm đến các otomat có số trạng thái tối thiểu nhận diện ngôn ngữ L Otomat có số trạng thái ít nhất trong số các otomat hữu hạn cùng nhận diện ngôn ngữ L được gọi là otomat tối tiểu của ngôn ngữ L.
Nh ậ n xét: Dễ thấy rằng với mỗi ngôn ngữ L, otomat tối tiểu của nó có thể không duy nhất
Ví d ụ 4.1 Giả sử ta có otomat M = , với:
Otomat M là đơn định, có 4 trạng thái và có đồ thị chuyển như sau:
Hình 2.24 Đồ thị chuyển của otomat M trong thí dụ 4.1
Dễ thấy rằng otomat M đoán nhận ngôn ngữ:
L = T(M) = {a^n b^ω | n≥0, ω∈{a, b}*} Dựa vào đồ thị chuyển của M, dễ dàng nhận thấy không tồn tại đường đi nào từ trạng thái t0 đến đỉnh kết thúc t1 Do đó, otomat M tương đương với otomat M’ có đồ thị chuyển khác.
Hình 2.25 Đồ thị chuyển của otomat tối tiểu M’ trong thí dụ 4.1
Rõ ràng là otomat M’ cũng đoán nhận ngôn ngữ L = T(M’) = {a n bω | n ≥ 0, ω ∈ {a, b} * }, M’ chỉ có hai trạng thái và là otomat tối tiểu của ngôn ngữ L = {a n bω | n ≥ 0, ω∈ {a, b} * }
2.4.2 Điề u ki ệ n c ầ n c ủ a ngôn ng ữ chính quy Đị nh lý 4.1 Nếu L là ngôn ngữ chính quy thì tồn tại số nguyên dương n sao cho với mọi ω ∈ L mà |ω | ≥ n đều có thểphân tích được dưới dạng ω = uvw, (với |v| ≥ 1 hay v ≠ ε) mà với mọi chỉ số i = 0, 1, 2, … ta có uv i w ∈ L
Ngôn ngữ L là một ngôn ngữ chính quy, và tồn tại một otomat hữu hạn nhận diện nó Giả sử L = T(A), với A = < Q, Σ, δ, q0, F > là một otomat tối thiểu có n trạng thái, tức là |Q| = n Chúng ta sẽ chứng minh rằng n là số tự nhiên cần tìm.
Giả sử ω = a1a2…am ∈ L với m ≥ n, ta có δ(q0, ω) ∈ F, nghĩa là tồn tại các trạng thái q0, q1,…, qm ∈ Q sao cho δ(qi-1, ai) = qi với 1 ≤ i ≤ m và qm ∈ F Vì m ≥ n, trong dãy trạng thái q0, q1,…, qm có ít nhất hai trạng thái trùng nhau, giả sử qi = qk với i < k ≤ n, trong đó k là số nhỏ nhất thỏa mãn điều kiện này Đặt u = a1…ai, v = ai+1…ak, w = ak+1…am, ta có ω = uvw và |v| = |ai+1…ak| ≥ 1, do đó i < k.
< k) Ngoài ra ta có: δ(q 0 , u) = q i = q k = δ(q 0 , uv)
Theo bổđề 1.1: δ(q 0 , u) = δ(q 0 , uv) = δ(δ(q 0 , u), v) = δ(δ(q 0 , uv), v) = δ(q 0 , uv 2 ) Tương tự, ta có: δ(q 0 , u) = δ(q 0 , uv 2 ) = δ(δ(q 0 , u), v 2 ) = δ(δ(q 0 , uv), v 2 ) = δ(q 0 , uv 3 )
Tiếp tục ta được: δ(q 0 , u) = δ(q 0 , uv i ), ∀i∈N
Cuối cùng ta có: δ(q 0 , uv i w) = δ(δ(q 0 , uv i ), w) = δ(δ(q 0 , uv), w) = δ(q 0 , uvw) ∈
F Vậy uv i w ∈ L, ∀i = 0, 1, 2 Định lý được chứng minh
H ệ qu ả 4.1 Cho A là otomat hữu hạn đơn định có n trạng thái và L là ngôn ngữ được đoán nhận bởi A Khi đó L ≠ ∅ khi và chỉ khi ∃ ω ∈L sao |ω| < n
Ch ứ ng minh: Điều kiện đủ là hiển nhiên Bây giờ cho L ≠∅ Giả sử mọi từ trong L đều có độ dài
Gọi α là từ có độ dài nhỏ nhất trong ngôn ngữ L với |α| ≥ n Theo định lý 4.1, ta có thể phân tích α thành uvw, trong đó |v| ≥ 1 và với mọi i = 0, 1, 2…, uv^i w thuộc L Khi i = 0, ta có uw thuộc L nhưng |uw| lại nhỏ hơn |α|, điều này dẫn đến mâu thuẫn với tính chất nhỏ nhất của |α| Do đó, tồn tại một từ ω trong L sao cho |ω| nhỏ hơn n.
H ệ qu ả 4.2 Tồn tại một ngôn ngữ phi ngữ cảnh mà không được đoán nhận bởi bất kỳ một otomat hữu hạn đơn định nào
Xét ngôn ngữ L = {a n b n | n ≥ 1} trên bảng chữΣ = {a, b} Ta có L = L(G), trong đó G = là văn phạm phi ngữ cảnh Giả sử L = T(A) với
A = là một otomat hữu hạn đơn định Với n đủ lớn, α = a n b n có |α| ≥
|Q| Theo định lý 1.1, ta có thể bi ểu diễn a n b n = uvw, trong đó |v| ≥ 1, uv i w∈L, ∀i 0, 1, 2… Ta hãy tập trung phân tích từ v và v i :
- Nếu v chỉ chứa a (|v|a >0 và |v| b = 0) thì với i đủ lớn |uv i w| a > | uv i w| b ;
- Nếu v chỉ chứa b (|v| b >0 và |v| a = 0) thì với i đủ lớn | uv i w| b > |uv i w| a ;
- Nếu |v| a >0 và |v| b > 0 thì với i = 2 ta có v = (ab) 2 = abab, tức là a và b xen kẽ nhau trong uv i w, khi đó uv i w không thể có dạng a n b n
Tất cả ba trường hợp đều mâu thuẫn với điều kiện uv i w∈L, do đó không tồn tại một automata hữu hạn đơn định nào có thể nhận diện ngôn ngữ L Kết luận này cho thấy rằng L không phải là một ngôn ngữ chính quy.
Hệ quả này chứng minh rằng một ngôn ngữ không phải là chính quy nếu không đáp ứng điều kiện cần của ngôn ngữ chính quy.
Hệ quả này chỉ ra rằng có sự tồn tại của ngôn ngữ phi ngữ cảnh không phải là ngôn ngữ chính quy, cho thấy rằng tập hợp các ngôn ngữ chính quy thực chất là một tập con của các ngôn ngữ phi ngữ cảnh.
1.Hãy xây dựng các otomat hữu hạn có đồ thị chuyển sau và xác định các ngôn ngữđược đoán nhận bởi chúng
2.Hãy xây dựng các otomat hữu hạn đơn định đoán nhận các ngôn ngữ sau: a L = {a n b m | n ≥ 1, m≥1}; b L = {(01) n , (010) n | n ≥ 0}; c L = {(aab) n (baa) m | n ≥ 1, m ≥ 1}
3.Hãy xây dựng các otomat hữu hạn đơn định đoán nhận các ngôn ngữ sau: a.L 1 = {ω∈{0, 1} * | ω bắt đầu đúng 3 chữ số 0}; b.L 2 = {ω∈{0, 1} * | ω không bắt đầu bởi hai chữ số 1 liên tiếp}
4.Hãy xây dựng các otomat hữu hạn đoán nhận các ngôn ngữ phần bù của các ngôn ngữ L 1 và L 2 trong bài tập 3
Chú ý: Otomat hữu hạn đơn định và đầy đủ thì phần bù của nó la otomat đổi két thành không kết và ngược lại
5 Hãy xây dựng các otomat hữu hạn không đơn định đoán nhận các ngôn ngữ sau: a L = {ω1abaω2 | ω1, ω2 ∈ {a, b} * }; b L = {ω∈ {0, 1} * | ω bắt đầu bằng lũy thừa dương của 101}; c L = {(1111) n ω | ω∈{0, 1} * , n ≥ 0}
Để xây dựng các văn phạm chính quy cho hai ngôn ngữ được xác định bởi các otomat hữu hạn không đơn định, chúng ta xem xét hai trường hợp Đối với ngôn ngữ A = , hàm chuyển trạng thái δ được định nghĩa như sau: δ(q0, a) = {q0, q1}, δ(q0, b) = {q0, q1}, δ(q1, a) = ∅, δ(q1, b) = {q2}, δ(q2, a) = {q2}, δ(q2, b) = {q2}, δ(q3, a) = {q4}, δ(q3, b) = ∅, δ(q4, a) = {q4}, δ(q4, b) = {q4} Đối với ngôn ngữ A = , hàm chuyển trạng thái δ được xác định như sau: δ(q0, 0) = {q0, q1}, δ(q0, 1) = {q1}, δ(q1, 0) = ∅, δ(q1, 1) = {q0, q1}.
7.Hãy xây dựng các otomat hữu hạn đơn định đoán nhận các ngôn ngữmà được sinh bởi các văn phạm chính quy sau: a G =
