tailieunhanh - Lý thuyết ngôn ngữ hình thức và ôtômát - Chương mở đầu

Tham khảo tài liệu 'lý thuyết ngôn ngữ hình thức và ôtômát - chương mở đầu', khoa học xã hội, ngôn ngữ học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | BỘ GIÁQ DỤC VÀ ĐÀQ TẠQ ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUyỄN GIA ĐỊNH Lý THUYẾT NGÔN NGỮ HÌNH THỨC VÀ ÔTÔMAT HUẾ - 2004 LỜI NÓI ĐẦU Mấy chục năm gần đây chúng ta đã chứng kiến sự phát triển mãnh liệt trong các lĩnh vực nghiên cứu toán học liên quan đến máy tính và tin học. Sự phát triển phi thường của các máy tính và những thay đổi sâu sắc trong phương pháp luận khoa học đã mở ra những chân trời mới cho toán học với một tốc độ không thể sánh được trong suốt lịch sử lâu dài của toán học. Những phát triển đa dạng của toán học đã trực tiếp tạo ra thuở ban đầu của máy tính và tin học và các tiến bộ trong tin học đã dẫn đến sự phát triển rất mạnh mẽ một số ngành toán học. Vì vậy toán học đóng vai trò trung tâm trong các cơ sở của tin học. Có thể kể ra một số lĩnh vực nghiên cứu đáng chú ý trong mối quan hệ này. Thật là thú vị khi nhận thấy rằng các lĩnh vực này cũng phản ánh sự phát triển lịch sử của tin học. 1. Lý thuyết kinh điển về tính toán bắt đầu bằng công trình của Godel Tarski Church Post Turing và Kleene chiếm vị trí trung tâm. 2. Trong lý thuyết ôtômat và ngôn ngữ hình thức kinh điển các khái niệm cơ bản là ôtômat văn phạm và ngôn ngữ với các công trình sáng giá của Axel Thue Chomsky Post. Ngoài hai lĩnh vực trên nhiều lĩnh vực quan trọng khác thuộc về các cơ sở toán học của tin học chẳng hạn lý thuyết độ phức tạp ngữ nghĩa và lý thuyết về tính đúng đắn của các ngôn ngữ lập trình lý thuyết mật mã lý thuyết các cấu trúc dữ liệu và lý thuyết các cơ sở dữ liệu. Lý thuyết ngôn ngữ hình thức và ôtômat đóng một vai trò rất quan trọng trong các cơ sở toán học của tin học. Ngôn ngữ hình thức được sử dụng trong việc xây dựng các ngôn ngữ lập trình lý thuyết về các chương trình dịch. Các ngôn ngữ hình thức tạo thành một công cụ mô tả đối với các mô hình tính toán cả cho dạng thông tin vào-ra lẫn kiểu thao tác. Lý thuyết ngôn ngữ hình thức chính vì thực chất của nó là một lĩnh vực khoa học liên ngành nhu cầu mô tả hình thức văn phạm được phát sinh trong nhiều ngành