0.5 Văn phạm chính quy và các tính chất  (Page 5/5)

Điều này dẫn đến sự mâu thuẫn, vậy giả thiết ban đầu là sai. Suy ra L không là tập chính quy.

Câu hỏi :

?

Hãy tự liên hệ một số tập ngôn ngữ khác mà bạn nghĩ chúng không thuộc lớp

ngôn ngữ chính quy vì không thể thỏa mãn các tính chất của Bổ đề bơm ?

Tính chất đóng của tập hợp chính quy

Có nhiều phép toán trên ngôn ngữ chuyên sử dụng cho tập hợp chính quy, mà cho phép khi áp dụng chúng vào tập hợp chính quy thì vẫn giữ được các tính chất của tập chính quy. Nếu một lớp ngôn ngữ nào đó "đóng" với một phép toán cụ thể, ta gọi đó là tính chất đóng của lớp ngôn ngữ này.

ĐỊNH LÝ 4.3 : Tập hợp chính quy đóng với các phép toán: hợp, nối kết và bao đóng Kleen.

Chứng minh

Hiển nhiên từ định nghĩa của biểu thức chính quy.

ĐỊNH LÝ 4.4 : Tập hợp chính quy đóng với phép lấy phần bù. Tức là, nếu L là tập chính quy và L  * thì * - L là tập chính quy.

Chứng minh

Gọi L là L(M) cho DFA M (Q, 1, , q0, F) và L  *.

Trước hết, ta giả sử 1 =  vì nếu có ký hiệu thuộc 1 mà không thuộc  thì ta có thể bỏ các phép chuyển trong M liên quan tới các ký hiệu đó. Do L  * nên việc xóa như vậy không ảnh hưởng tới M. Nếu có ký hiệu thuộc  nhưng không thuộc 1 thì các ký hiệu này không xuất hiện trong L. Ta thiết kế thêm một trạng thái "chết" d trong M sao cho (d, a) = d, a  và (q, a) = d, q  Q và a   - 1.

Bây giờ, để chấp nhận * - L, ta hoàn thiện các trạng thái kết thúc của M. Nghĩa là, đặt M’ = (Q, , , q0, Q - F). Ta có M’ chấp nhận từ w nếu (q0,w)  Q - F, suy ra w Î * - L.

ĐỊNH LÝ 4.5: Tập hợp chính quy đóng với phép giao

Chứng minh

Do ta có công thức biến đổi :

$L_1$  $L_2$ = $\overline{\begin{array}{cc}\overline{L_1}& \overline{L_2}\end{array}}$

Nên theo các định lý trên, suy ra được tập L1  L2 là tập chính quy.

Các giải thuật xác định tập hợp chính quy

Một vấn đề khác, cũng rất cần thiết là xác định các giải thuật giúp giải đáp nhiều câu hỏi liên quan đến tập hợp chính quy, chẳng hạn như : Một ngôn ngữ cho trước là rỗng, hữu hạn hay vô hạn ? Ngôn ngữ chính quy có tương đương với ngôn ngữ nào khác không ? ... Để xác định các giải thuật này, trước hết cần giả sử mỗi tập chính quy thì được biểu diễn bởi một ôtômát hữu hạn. Như đã biết, biểu thức chính quy dùng đặc tả cho tập hợp chính quy, do đó chỉ cần cung cấp thêm một cơ chế dịch từ dạng biểu thức này sang dạng ôtômát hữu hạn. Một số định lý sau có thể xem là nền tảng cho việc chuyển đổi này.

ĐỊNH LÝ 4.6: Tập hợp các chuỗi được chấp nhận bởi ôtômát M có n trạng thái là:

1) Không rỗng nếu và chỉ nếu ôtômát chấp nhận một chuỗi có độ dài<n.

2) Vô hạn nếu và chỉ nếu ôtômát chấp nhận một chuỗi có độ dài l với n  l<2n.

Chứng minh

1) Phần "nếu " là hiển nhiên.

Ta chứng minh "chỉ nếu": Giả sử M chấp nhận một tập không rỗng. Gọi w là chuỗi ngắn nhất được chấp nhận bởi M. Theo bổ đề bơm, ta có | w |<n vì nếu w là chuỗi ngắn nhất và | w |  n thì ta có thể viết w = uvy, và uy là chuỗi ngắn hơn trong L hay | uy |<| w |  Mâu thuẫn.

2) Nếu w  L và n  | w |<2n thì theo bổ đề bơm ta có w = w1w2w3 và w1w2 i w3  L với mọi i  0, suy ra L(M) vô hạn .

Ngược lại, nếu L(M) vô hạn thì tồn tại w  L(M) sao cho | w |  n. Nếu | w |<2n thì xem như đã chứng minh xong. Nếu không có chuỗi nào có độ dài nằm giữa n và 2n-1 thì gọi w là chuỗi có độ dài ít nhất là 2n nhưng ngắn hơn mọi chuỗi trong L(M), nghĩa là | w |  2n. Một lần nữa, cũng theo bổ đề bơm, ta có thể biểu diễn w = w1w2w3, trong đó 1  | w2 |  n và w1w3  L(M). Ta có hoặc w không phải là chuỗi ngắn nhất có độ dài  2n, hoặc là n  | w1w3 |  2n-1  Mâu thuẫn. Vậy có tồn tại chuỗi có độ dài l sao cho n  l<2n.

ĐỊNH LÝ 4.7 : Có giải thuật để xác định hai ôtômát tương đương (chấp nhận cùng một ngôn ngữ).

Chứng minh

Đặt M1, M2 là hai ôtômát chấp nhận L1, L2.

Theo các định lý 4.3, 4.4, 4.5, ta có ( $L_1$  $\overline{L_2}$ )  ( $\overline{L_1}$  $L_2$ ) được chấp nhận bởi ôtômát M3 nào đó. Dễ thấy M3 chấp nhận một chuỗi nếu và chỉ nếu L1  L2. Theo định lý 4.6, ta thấy có giải thuật để xác định xem liệu L1 = L2 hay không.

Tổng kết chương IV: Qua chương này, chúng ta có thể thấy rõ hơn các tính chất của lớp ngôn ngữ chính quy và cách xác định chúng bằng một số giải thuật. Mối liên quan giữ hai cơ chế đoán nhận ngôn ngữ (ôtômát hữu hạn) và phát sinh ngôn ngữ (văn phạm) cũng đã được thiết lập và chứng minh rõ ràng. Đây là lớp ngôn ngữ nhỏ nhất theo sự phân cấp của Noam Chomsky. Trong những chương tiếp theo, chúng ta sẽ khảo sát những lớp ngôn ngữ rộng lớn hơn chứa cả ngôn ngữ chính quy trong nó.

BÀI TẬP CHƯƠNG IV

4.1. Xây dựng văn phạm tuyến tính trái và tuyến tính phải cho các ngôn ngữ sau :

a) (0 + 1)*00(0 + 1)*

b) 0*(1(0 + 1))*

c) (((01 + 10)*11)*00)*

4.2. Xây dựng văn phạm chính quy sinh ra các ngôn ngữ trên bộ chữ cái  = {0,1} như sau :

a) Tập các chuỗi có chứa 3 con số 0 liên tiếp.

b) Tập các chuỗi kết thúc bằng 2 con số 0.

4.3. Xây dựng văn phạm chính quy sinh ra các ngôn ngữ sau :

a) { w  w  (0 + 1)* }

b) { am bn  m, n>0 }

4.4. Chứng tỏ rằng ngôn ngữ L = {0n1n  n là số nguyên dương} không chính qui.

4.5. Ngôn ngữ nào trong các ngôn ngữ sau không là ngôn ngữ chính qui? Chứng minh câu trả lời:

1. L = {02n  n là số nguyên dương }
2. L = {0n1m0 n+m  m, n là số nguyên dương}
3. L = {0n  n là số nguyên tố }