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à:
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.
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ó
đượ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ó.