- BÀI 5: NGÔN NGỮ KHÔNG CHÍNH QUY. - Ngôn ngữ chính quy: Ngôn ngữ được đoán nhận bởi một DFA nào đó. - Ngôn ngữ không chính quy là gì?. - Ví dụ: Xét các ngôn ngữ sau trên bộ chữ Σ= {0,1} là chính quy hay không chính quy. - Ví dụ: Xét các ngôn ngữ sau trên bộ chữ Σ= {0,1}. - Không chính quy. - Chính quy. - Làm sao để chứng minh một ngôn ngữ là không chính quy?. - Chu trình. - ra đó sẽ nằm trong ngôn ngữ mà FSM đó đoán nhận. - Nếu ta bỏ qua chu trình đó thì chuỗi được sinh ra vẫn sẽ nằm trong ngôn ngữ mà FSM đó đoán nhận. - Ví dụ. - Tất cả các chuỗi s được sinh ra có dạng s = xy i z đều thuộc ngôn ngữ A mà máy FSM đoán nhận. - Độ dài dẫn xuất. - Nếu A là ngôn ngữ chính quy và s là một xâu đủ dài thuộc A (|s. - Tất cả các ngôn ngữ chính quy có một thuộc tính đặc biệt Nếu ngôn ngữ không có thuộc tính này → Là ngôn ngữ không chính quy. - Nếu A là một ngôn ngữ chính quy, thì tồn tại một số p sao cho nếu s là một xâu bất kỳ thuộc A có độ dài ít nhất là p, thì s có thể được chia ra làm 3 phần s=xyz thỏa mãn các điều kiện sau:. - Sử dụng bổ đề Bơm để chứng minh một ngôn ngữ A là không chính quy. - Giả sử A là chính quy. - p) có thể chia làm 3 đoạn s = xyz. - Mâu thuẫn, do đó kết luận A không phải là chính quy. - Ví dụ 1. - Cho ngôn ngữ B = {0 n 1 n | n ≥ 0}. - Hãy chứng minh ngôn ngữ B là không chính quy Chứng minh:. - Giả sử B là chính quy → B có một độ dài dẫn xuất p. - Có các mâu thuẫn nên giả thiết là sai → B là ngôn ngữ không chính quy. - Ví dụ 2. - Cho ngôn ngữ C = {w| w có số ký hiệu 0 bằng số ký hiệu 1}. - Hãy chứng minh ngôn ngữ C là không chính quy. - Ngôn ngữ chính quy được đoán nhận bởi. - Biểu thức chính quy biểu diễn. - Thế nào là ngôn ngữ không chính quy
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt