tailieunhanh - Lý thuyết văn phạm, ngôn ngữ và ôtômát - Chương 3

Tài liệu tham khảo bài giảng Lý thuyết văn phạm, ngôn ngữ và ôtômát gồm 4 chương - Chương 3 Nguồn và otomat hữu hạn | c Âư ma3 - c0lớbtỉiìệw cẨunq Phần đầu của chương này trình bày về nguồn và các phép toán trên nguồn đó chính là dạng hình học của otomat hữu hạn. Phần hai cho chúng ta thấy mối quan hệ tương đương giữa nguồn với ôtomat hữu hạn văn phạm chính quy và biểu thức chính quy. Mối quan hệ này không chỉ biểu hiện ở mặt sinh ra ngôn ngữ mà còn thể hiện ở các phép toán trên chúng. Phần này cũng cho ta một thuật toán cụ thể để tìm ngôn ngữ được sinh bởi một nguồn và do vậy nó cũng cho ta thuật toán xác định ngôn ngữ sinh ra văn phạm chính quy mà chương 1 ta chưa đề cập đến. Phần cuối cùng của chương 3 trình bày về điều kiện cần điều kiện cần và đủ của ngôn ngữ chính quy nó cho phép ta có thể kiểm tra xem một ngôn ngữ có phải là ngôn ngữ chính quy hay không. Bài giảng Lý thuyết Văn phạm Ngôn ngữ và Ôtomat. Nguyễn Quốc Thắng-Nguyễn Lâm Tùng - ĐẠI HỌC THẢNG LONG - Ngày 15 tháng 1 năm 2006 - 201 Định nghĩa. Nguồn I trên bảng chữ cái E là một đa đồ thị có hướng có khuyên trên đó có Một đỉnh vào V I đánh dấu bằng mũi tên . Một tập đỉnh ra F I đánh dấu bằng cách đặt trong hình tròn kép các đỉnh còn lại đặt trong hình tròn. - Trên mỗi cung ghi một ký hiệu thuộc E u A . - Cung trên đó ghi từ rỗng gọi là cung rỗng còn lại là cung cốt yếu. Ký hiệu tập tất cả các đỉnh của nguồn I là Aựỵ Nguồn I được gọi là đơn định nếu nó không chứa cung rỗng và hai cung bất kỳ xuất phát từ một đỉnh được ghi bằng hai ký hiệu khác nhau. - Nguồn I được gọi là đầy đủ nếu Va e E E Aự luôn tồn tại cung đi ra từ s và ghi a trên đó. - Nguồn I được gọi là đơn định và đầy đủ nếu nó vừa đơn định vừa đầy đủ. Bài giảng Lý thuyết Văn phạm Ngôn ngữ và Ôtomat. Nguyễn Quốc Thắng-Nguyễn Lâm Tùng - ĐẠI HỌC THẢNG LONG - Ngày 15 tháng 1 năm 2006 - 201 Bài giảng Lý thuyết Văn phạm Ngôn ngữ và Ôtomat. Nguyễn Quốc Thắng-Nguyễn Lâm Tùng - ĐẠI HỌC THẢNG LONG - Ngày 15 tháng 1 năm 2006 - .