Tài liệu tham khảo Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức trường đaị học Bách Khoa khoa Công nghệ thông tin - Chương 4 Các tính chất Ngôn ngữ chính qui,Vật lý học một cách tổng quát nhất đó là khoa học nghiên cứu về "vật chất" và "sự tương tác".Cụ thể thì Vật lý khoa học nghiên cứu về các quy luật vận động của tự nhiên, từ thang vi mô (các hạt cấu tạo nên vật chất) cho đến thang vĩ mô (các hành tinh, thiên hà và vũ trụ). Trong tiếng Anh, từ. | Chương 4 Các tính chất của ngôn ngữ chính qui NNCQ tổng quát là như thế nào Có phải chăng mọi ngôn ngữ hình thức đều là chính qui Khi chúng ta thực hiện các phép toán trên NNCQ thì kết quả sẽ như thế nào có còn là một NNCQ không Một ngôn ngữ nào đó có hữu hạn không Có rỗng không Làm thế nào để biết một ngôn ngữ đã cho có là chính qui không Trang 130 Lý thuyết Ôtômát NNHT - Khoa Công Nghệ Thông Tin Chương 4 Các tính chất của ngôn ngữ chính qui Tính đóng của ngôn ngữ chính qui. Các câu hỏi cơ bản về ngôn ngữ chính qui. Nhận biết các ngôn ngữ không chính qui Trang 131 Lý thuyết Ôtômát NNHT - Khoa Công Nghệ Thông Tin Tính đóng của NNCQ Đóng dưới các phép toán tập hợp đơn giản. Định lý - Nếu L1 và L2 là các NNCQ thì LpjL 2. L1nL2 L1L2 L và L1 cũng vậy. Chúng ta nói răng họ NNCQ là đóng dưới các phép hội giao kết nối bù và bao đóng-sao. Chứng minh Nếu L1 L2 là chính qui thì 3 các BTCQ r1 r2 sao cho L1 L r1 L2 L r2 . Theo định nghĩa r1 r2 r1r2 và r1 là các BTCQ định nghĩa các ngôn ngữ L1oL2 L1L2 và L1 . Vì vậy họ NNCQ là đóng đối với các phép toán này. Để CM tính đóng đối với phép bù cho M Q s ô q0 F là dfa chấp nhận L1 thì dfa M Q s ỗ q0 Q - F chấp nhận L. Trang 132 Lý thuyết Ôtômát NNHT - Khoa Công Nghệ Thông .
