tailieunhanh - Bài giảng Tin học lý thuyết - Chương 2: Ngôn ngữ và sự phân cấp Chomsky

Chương 2 trang bị cho người học những kiến thức về ngôn ngữ và sự phân cấp Chomsky. Các nội dung chính trong chương này gồm có: Khái niệm ngôn ngữ, Cách biểu diễn ngôn ngữ, Văn phạm, Sự phân lớp văn phạm. . | Ngôn ngữ và sự phân cấp Chomsky Nội dung: Khái niệm ngôn ngữ Cách biểu diễn ngôn ngữ Văn phạm Sự phân lớp văn phạm Chương 2: Ký hiệu, bộ chữ cái, chuỗi Ký hiệu (symbol): là một thực thể trừu tượng mà ta không định nghĩa được một cách hình thức Các chữ cái a, b, c hoặc các số 1, 2, 3 Bộ chữ cái (alphabet): Σ Là một tập (không rỗng) các ký hiệu nào đó Bộ chữ cái Latin {A, B, C, , a, b, c, , z} Chuỗi (string): một chuỗi (hay một từ - word) trên bộ chữ cái Σ Là một dãy hữu hạn các ký hiệu của Σ Một ký hiệu có thể xuất hiện nhiều lần Chuỗi Độ dài chuỗi: là số các ký hiệu tạo thành chuỗi |abca| = 4 Chuỗi rỗng: ký hiệu ε, là chuỗi không có ký hiệu nào |ε| = 0 Chuỗi con: chuỗi v là chuỗi con của w nếu v được tạo bởi các ký hiệu liền kề nhau trong chuỗi w. Chuỗi 10 là chuỗi con của chuỗi 010001 Chuỗi tiền tố: là chuỗi con bất kỳ nằm ở đầu chuỗi Chuỗi hậu tố: là chuỗi con bất kỳ nằm ở cuối chuỗi Chuỗi abc có các tiền tố a, ab, abc Chuỗi 0246 có các hậu tố 6, 46, 246, 0246 Chuỗi Chuỗi nối kết (ghép): là chuỗi được tạo thành bằng cách viết chuỗi thứ nhất, sau đó viết chuỗi thứ hai, . Nối ghép của chuỗi Long và Int là LongInt Nối kết của chuỗi rỗng: εw = wε = w (với mọi w) → ε là đơn vị của phép nối kết Chuỗi đảo ngược: của chuỗi w, ký hiệu wR, là chuỗi w được viết theo thứ tự ngược lại. w = abcd → wR = dcba εR = ε Ngôn ngữ (Languages) Tổng quan về ngôn ngữ: Ngôn ngữ tự nhiên: tiếng Việt, tiếng Anh, Ngôn ngữ lập trình: Pascal, C/C++, Là tập hợp các câu theo cấu trúc quy định nào đó Biểu thị các ý nghĩ, các sự kiện hay các khái niệm Bao gồm một tập các ký hiệu và các quy tắc để vận dụng chúng Ngôn ngữ (Languages) Một ngôn ngữ (hình thức) L là một tập hợp các chuỗi của các ký hiệu từ một bộ chữ cái nào đó. * và +: * : tập hợp tất cả các chuỗi con, kể cả chuỗi rỗng ε, sinh ra từ bộ chữ cái . + : tập hợp tất cả các chuỗi con, ngoại trừ chuỗi rỗng ε, sinh ra từ bộ chữ cái . * = + + {ε} + = * - {ε} = {0,1} thì: * = {ε, 0, 1, 00, 01, 10, 11, 000, } + = {0, | Ngôn ngữ và sự phân cấp Chomsky Nội dung: Khái niệm ngôn ngữ Cách biểu diễn ngôn ngữ Văn phạm Sự phân lớp văn phạm Chương 2: Ký hiệu, bộ chữ cái, chuỗi Ký hiệu (symbol): là một thực thể trừu tượng mà ta không định nghĩa được một cách hình thức Các chữ cái a, b, c hoặc các số 1, 2, 3 Bộ chữ cái (alphabet): Σ Là một tập (không rỗng) các ký hiệu nào đó Bộ chữ cái Latin {A, B, C, , a, b, c, , z} Chuỗi (string): một chuỗi (hay một từ - word) trên bộ chữ cái Σ Là một dãy hữu hạn các ký hiệu của Σ Một ký hiệu có thể xuất hiện nhiều lần Chuỗi Độ dài chuỗi: là số các ký hiệu tạo thành chuỗi |abca| = 4 Chuỗi rỗng: ký hiệu ε, là chuỗi không có ký hiệu nào |ε| = 0 Chuỗi con: chuỗi v là chuỗi con của w nếu v được tạo bởi các ký hiệu liền kề nhau trong chuỗi w. Chuỗi 10 là chuỗi con của chuỗi 010001 Chuỗi tiền tố: là chuỗi con bất kỳ nằm ở đầu chuỗi Chuỗi hậu tố: là chuỗi con bất kỳ nằm ở cuối chuỗi Chuỗi abc có các tiền tố a, ab, abc Chuỗi 0246 có các hậu tố 6, 46, 246, 0246 Chuỗi Chuỗi nối