Bài giảng Chương trình dịch: Bài 2 do Trương Xuân Nam biên soạn, cùng nắm kiến thức trong bài học này thông qua tìm hiểu các nội dung sau: Ngôn ngữ và biểu diễn ngôn ngữ, các lớp văn phạm (phân loại chomsky), văn phạm chính quy và automat hữu hạn, văn phạm phi ngữ cảnh và automat đẩy xuống, văn phạm có đệ quy trái, văn phạm đơn nghĩa. | CHƯƠNG TRÌNH DỊCH Bài 2: Các khái niệm cơ sở Nội dung 1. 2. 3. 4. 5. 6. 7. Ngôn ngữ và biểu diễn ngôn ngữ Các lớp văn phạm (phân loại chomsky) Văn phạm chính quy và automat hữu hạn Văn phạm phi ngữ cảnh và automat đẩy xuống Văn phạm có đệ quy trái Văn phạm đơn nghĩa Bài tập TRƯƠNG XUÂN NAM 2 Phần 1 Ngôn ngữ và biểu diễn ngôn ngữ TRƯƠNG XUÂN NAM 3 Ngôn ngữ Kí hiệu (symbol): khái niệm cơ sở để xây dựng ngôn ngữ, không thể định nghĩa một cách hình thức Các chữ số, các chữ cái, các dấu kí hiệu, Bộ chữ (alphabet): tập hợp hữu hạn các kí hiệu Bộ chữ cái tiếng Việt (a, ă, â, , x, y, A, Ă, , Y) Chuỗi (string): dãy hữu hạn các ký hiệu thuộc cùng một bộ ký hiệu nào đó “2016” là chuỗi gồm 4 ký hiệu thuộc bộ ký hiệu chữ số “2016” còn gọi là chuỗi sinh bởi bộ ký hiệu chữ số Chuỗi rỗng (không có kí hiệu) được kí hiệu là TRƯƠNG XUÂN NAM 4 Ngôn ngữ Ngôn ngữ (language): tập hợp các chuỗi Ngôn ngữ tiếng Việt là tập một số các chuỗi sinh bởi bộ chữ tiếng Việt Có những chuỗi sinh từ bộ chữ tiếng Việt những không thuộc ngôn ngữ tiếng Việt (chẳng hạn chuỗi “lẫnh”) Chuỗi thuộc ngôn ngữ tiếng Việt đều sinh bởi bộ chữ tiếng Việt Tổng quát: Cho bộ chữ * là tập tất cả các chuỗi sinh ra từ (gồm cả ) Ngôn ngữ L sinh bởi là một tập con của * TRƯƠNG XUÂN .
