Giáo trình giới thiệu một cách hệ thống những khái niệm cơ bản và các tính chất chung của ôtômát và ngôn ngữ hình thức. Sau mỗi Chương có các bài tập hệ thống hoá lại kiến thức và thông qua đó, học viên nắm bắt được các khái niệm cơ bản, các kiến thức chủ yếu của từng Chương và cuối cùng là để nâng cao sự hiểu biết về ôtômát và ngôn ngữ hình thức, đồng thời phát triển khả năng ứng dụng chúng trong nghiên cứu và triển khai ứng dụng Công nghệ thông tin. Mời các bạn cùng tham khảo nội dung phần 2 dưới đây. | Ôtômát và ngôn ngữ hình thức CHƯƠNG 4. TẬP CHÍNH QUI VÀ VĂN PHẠM CHÍNH QUI Chương bốn đề cập đến Tập chính qui và ôtômát hữu hạn trạng thái Bổ đề Bơm cho các tập chính qui và ứng dụng Quan hệ giữa tập chính qui văn phạm chính qui ôtômát hữu hạn Các biểu thức chính qui Biểu thức chính qui được sử dụng để biểu diễn tập các xâu trong các cấu trúc đại số. Biểu thức chính qui mô tả những ngôn ngữ đoán nhận được bởi ôtômát hữu hạn trạng thái. Định nghĩa. Biểu thức chính qui trên bảng chữ được định nghĩa đệ qui như sau 1. Mọi ký hiệu kết thúc a và tập rỗng đều là biểu thức chính qui. Khi một ký hiệu a thì biểu thức chính qui tương ứng sẽ được ký hiệu là a. 2. Hợp của hai biểu thức chính qui R1 và R2 ký hiệu là R1 R2 cũng là biểu thức chính qui 3. Ghép hai biểu thức chính qui R1 và R2 ký hiệu là cũng là biểu thức chính qui 4. Bao đóng của một biểu thức chính qui R ký hiệu là R cũng là biểu thức chính qui 5. Nếu R là một biểu thức chính qui thì R cũng là biểu thức chính qui. 6. Biểu thức chính qui trên bảng chữ là tập tất cả các hạng thức được xây dựng một cách đệ qui trên cơ sở chỉ áp dụng các qui tắc từ 1 5 nêu trên. Chú ý i Chúng ta ký hiệu x in đậm cho biểu thức chính qui để phân biệt với ký hiệu hoặc xâu x thông thường. 63 Ôtômát và ngôn ngữ hình thức ii Cặp ngoặc đơn và trong qui tắc 5 được sử dụng để xác định thứ tự thực hiện các phép toán của các biểu thức chính qui. iii Khi không có các ngoặc đơn thì thứ tự thực hiện trong biểu thức chính qui được qui định như sau Bao đóng phép ghép rồi đến phép hợp. Định nghĩa. Tập biểu diễn cho một biểu thức chính qui được gọi là tập chính qui. Nếu a b thì 1. Biểu thức chính qui a xác định tập a nói cách khác tập a được biểu diễn bởi a 2. Biểu thức chính qui a b xác định tập a b hoặc a b được biểu diễn bởi biểu thức a b 3. Biểu thức chính qui ab xác định tập ab hoặc ab được biểu diễn bởi biểu thức ab 4. Biểu thức chính qui a xác định tập a aa aaa . hoặc a aa aaa . được biểu diễn bởi a 5. Biểu thức chính qui a b xác .
