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

Vậy, mọi văn phạm tuyến tính trái hay phải đều sinh ra một tập hợp chính quy.

Thí dụ 4.3 : NFA được xây dựng từ Định lý 4.1 cho văn phạm tuyến tính phải (1) ở thí dụ 4.2 có dạng như hình 4.1 sau :

Xét văn phạm tuyến tính trái (2) ở thí dụ 4.2, nếu đảo ngược các vế phải luật sinh, ta có:

S  01S 0

Hình 4.1 - NFA chấp nhận ngôn ngữ 0(10)*

Áp dụng các bước xây dựng NFA cho văn phạm này theo Định lý 4.1, ta có sơ đồ chuyển như Hình 4.2 (a). Nếu chúng ta đảo ngược các cạnh của NFA này và chuyển đổi vị trí các trạng thái bắt đầu và kết thúc, chúng ta sẽ có một NFA khác chấp nhận ngôn ngữ 0(10)*

Hình (a)

Hình (b)

Hình 4.2 - Xây dựng NFA cho 0(10)* từ văn phạm tuyến tính trái

ĐỊNH LÝ 4.2 : Nếu L là một tập hợp chính quy, thì L được sinh từ một văn phạm tuyến tính trái hoặc một văn phạm tuyến tính phải nào đó.

Chứng minh

Đặt L = L(M) với DFA M(Q, , , q0, F).

Trước hết, ta giả sử rằng trạng thái q0 không phải là trạng thái kết thúc. Kế tiếp, ta đặt L = L(G) với văn phạm tuyến tính phải G(V, , P, q0), trong đó P chứa các luật sinh dạng p  aq nếu (p, a) = q và luật sinh dạng p  a nếu (p, a) là một trạng thái kết thúc. Rõ ràng (p, w) = q khi và chỉ khi có chuỗi dẫn xuất p * wq. Nếu wa được chấp nhận bởi M, ta đặt (q0, w) = p, suy ra dẫn xuất q0 * wq. Tương tự, nếu (p, a) là trạng thái kết thúc, vì p  a là một luật sinh, nên q0 * wa. Ngược lại, đặt q0 * x. Ta có x = wa và q0 * wq  wa với mọi p. Và vì (q0, w) = p và (p, a) là trạng thái kết thúc nên do đó x  L(M). Hay nói cách khác : L(M) = L(G) = L.

Bây giờ, xét q0  F, vì thế chuỗi rỗng  thuộc L. Lưu ý rằng văn phạm G vừa định nghĩa ở trên chỉ sinh ra ngôn ngữ L – {}. Chúng ta có thể sửa đổi G bằng cách thêm vào một ký hiệu bắt đầu S mới với luật sinh S  q0  . Văn phạm thu được vẫn có dạng tuyến tính phải và phát sinh ngôn ngữ L.

Để phát sinh một văn phạm tuyến tính trái cho L, ta bắt đầu với một NFA cho LR và sau đó đảo ngược chuỗi vế phải cho tất cả mọi luật sinh của văn phạm tuyến tính phải vừa thu được.

Thí dụ 4.4 : Trong Hình 4.3 ta thấy sơ đồ chuyển DFA cho 0(10)*

Văn phạm tuyến tính phải sinh từ DFA này có dạng :

A  0B1D0

B  0D1C

C  0B1D0

D  0D1D

Trong văn phạm trên, biến D không có ích nên ta có thể loại bỏ D và tất cả các luật sinh liên quan tới D, rút gọn văn phạm thành :

A  0B0

B  1C

C  0B0

Hình 4.3 - DFA cho 0(10)*

Một số tính chất của tập hợp chính quy

Một câu hỏi khá quan trọng được đặt ra là: Cho ngôn ngữ L với một số tính chất đặc tả nào đó, liệu L có phải là tập chính quy không ? Phần này cung cấp một số lý thuyết giúp trả lời câu hỏi này.

Bổ đề bơm cho tập hợp chính quy

Một trong những nguyên lý hiệu quả là "Bổ đề bơm", đây là một công cụ mạnh giúp chứng minh các ngôn ngữ không là chính quy. Đồng thời, nó cũng thực sự hữu ích trong việc phát triển các giải thuật liên quan đến các ôtômát, chẳng hạn như một ngôn ngữ được chấp nhận bởi một FA cho trước là hữu hạn hay vô hạn ?

BỔ ĐỀ 4.1: (BỔ ĐỀ BƠM)

Nếu L là tập hợp chính quy thì có tồn tại hằng số n sao cho nếu z là một từ bất kỳ thuộc L và | z |  n, ta có thể viết z = uvw với | uv |  n, | v |  1 và i  0, ta có uviw  L.