tailieunhanh - Độ phức tạp đoán nhận lớp siêu ngôn ngữ chính quy sinh bởi siêu sơ đồ sinh suy rộng.

Độ phức tạp đoán nhận lớp siêu ngôn ngữ chính quy sinh bởi siêu sơ đồ sinh suy kỳ này đánh dấu bởi sự ảnh hưởng sâu sắc của Warren McCulloch, giám đốc viện nghiên cứu Tâm lý học Đại học tổng hợp Illinois. Nhóm của anh đã đưa ra những kết luận quan trọng rằng muốn biết về tổ chức của vỏ não, hiểu được cơ chế hoạt động của não (và mô phỏng hoạt động chúng bằng máy móc) thì cần sự phối hợp của rất nhiều ngành. Chính Warren McCulloch cũng đã chuyển từ tâm lý. | Tạp chí Tin học và Đĩêu khiền học 2004 176--182 ĐỘ PHỨC TẠP ĐOÁN NHẬN LỚP SIÊU NGÔN NGỮ CHÍNH QUY SINH BỞI SIÊU Sơ ĐỒ SINH SUY RỘNG PHÙNG VĂN ỔN Trung tâm tin học Bộ Giao thông Vận tải Abstract. In 1 we have the following results for any hyper-generating schema G the complexity of a finite automation of L G is PL G h d G 1 IGI 1. In this paper we consider the hyper-generating graph with adding a set of infinitive words and we have the result PLJG h d G 1 G 1. Tóm tắt. Trong 1 chúng tôi đã có kết quả là với mỗi siêu sơ đồ sinh G độ phức tạp ôtômát hữu hạn đoán nhận siêu ngôn ngữ chính qui L G sinh bởi G là PL G h d G 1 IGI 1. Trong bài báo này chúng tôi nghiên cứu việc bổ sung tập từ vô hạn Mg ì lên các cung t của siêu đồ thị sinh G và nhận được kết quả P LOC G h d G 1 G 1. 1. ĐẶT VẤN ĐÊ Trong 1 chúng tôi đã nêu khái niệm siêu sơ đồ sinh và đánh giá độ phức tạp đoán nhận siêu ngôn ngữ chính quy sinh bởi siêu sơ đồ sinh. Trong bài báo này chúng tôi mở rộng việc xét tập từ ghi trên các cung của siêu đồ thị sinh có thể là tập các siêu từ. Siêu sơ đồ sinh xây dựng trên các siêu đồ thị sinh như vậy gọi là siêu sơ đồ sinh suy rộng. Kết quả thu nhận được là ước lượng trên của số trạng thái của siêu ôtômát đoán nhận lớp siêu ngôn ngữ chính quy sinh bởi siêu sơ đồ sinh suy rộng. 2. CÁC ĐỊNH NGHĨA . Siêu đồ thị sinh. Cho bảng chữ cái hữu hạn s ũq 0 2 . ara . Siêu đồ thị sinh trên bảng chữ cái s là một đồ thị định hướng hữu hạn G với tập các đỉnh là V có một đỉnh khởi đầu Iq G V một tập không rỗng các đỉnh kết thúc Fq t 2 I i c V. Trên mỗi cung t được ghi một tập các từ hữu hạn hoặc một tập các siêu từ là một siêu ngôn ngữ chính quy Mg ì nào đó trên s. Cung t mà trên đó tập 1 Mg ì gọi là cung rỗng. 2 Mg ì a với a G s gọi là cung cốt yếu. Đỉnh mà có cung cốt yếu đi tới gọi là đỉnh cốt yếu. 3 Mg ì tập các tù hữu hạn gọi là cung hữu hạn. 4 Mg ì tập các tù vô hạn gọi là cung cuối hay cung vô hạn . Từ đỉnh cuối của cung cuối không có cung nào đi ra. ĐỘ PHỨC TẠP ĐOÁN .