Giáo trình Tin học lý thuyết - ThS. Võ Huỳnh Trâm

Giáo trình Tin học lý thuyết do ThS. Võ Huỳnh Trâm biên soạn trình bày các nội dung chính sau: Bổ túc toán, Ôtômát tuyến tính giới nội và văn phạm cảm ngữ cảnh, Ôtômat hữu hạn và biểu thức chính quy, Văn phạm phi ngữ cảnh, Ôtômát đẩy xuống, Văn phạm chính quy và các tính chất, Máy Turing, Attributions.
Nội dung trích xuất từ tài liệu:
Giáo trình Tin học lý thuyết - ThS. Võ Huỳnh TrâmGiáo trình Tin học lý thuyết By: ThS. Võ Huỳnh TrâmGiáo trình Tin học lý thuyết By: ThS. Võ Huỳnh Trâm Online: < http://cnx.org/content/col10826/1.1/ > CONNEXIONS Rice University, Houston, TexasThis selection and arrangement of content as a collection is copyrighted by ThS. Võ Huỳnh Trâm. It is licensed underthe Creative Commons Attribution 3.0 license (http://creativecommons.org/licenses/by/3.0/).Collection structure revised: July 30, 2009PDF generated: February 5, 2011For copyright and attribution information for the modules contained in this collection, see p. 107. Table of Contents1 Bổ túc toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Ôtômát tuyến tính giới nội và văn phạm cảm ngữ cảnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Ôtômat hữu hạn và biểu thức chính quy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 Văn phạm phi ngữ cảnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415 Ôtômát đẩy xuống . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676 Văn phạm chính quy và các tính chất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 797 Máy Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89Attributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .107ivChương 1Bổ túc toán 11.1 TẬP HỢP (Sets)Một tập hợp là tập các đối tượng không có sự lặp lại. Mỗi đối tượng trong tập hợp được gọi là phần tử(element) của tập hợp đó.1.1.1 Ký hiệu tập hợpNếu số phần tử trong một tập hợp không quá lớn, hay nói cách khác – tập hợp là hữu hạn, tập hợp có thểđược đặc tả bằng cách liệt kê các phần tử của nó. Thí dụ 1.1 : D xác định tập hợp các ngày trong tuần : D = { Mon, Tues, Wed, Thurs, Fri, Sat, Sun } Các phần tử trong tập hợp viết cách nhau bởi dấu “, “ và đặt trong cặp dấu { và }. Không có sự bắtbuộc về thứ tự liệt kê các phần tử trong tập hợp. Chẳng hạn, tập hợp D cũng tương đương với tập hợp sau : D = { Mon, Wed, Fri, Thurs, Sun, Tues, Sat } Nếu phần tử x là thành phần của tập hợp A, ta viết x [U+F0CE] A (đọc là x thuộc A), và nếu x khônglà phần tử của A, ta viết x [U+F0CF] A (đọc là x không thuộc A). Chẳng hạn : Mon [U+F0CE] D nhưngKippers [U+F0CF] D. Nếu một tập hợp chứa một số khá lớn các phần tử hay thậm chí là một số vô hạn, người ta có thể khôngliệt kê tất cả các phần tử mà đặc tả tập hợp theo một số tính chất đặc trưng của nó. Thí dụ 1.2 : D = { x [U+F07C] x là một ngày trong tuần } P = { y [U+F07C] y là số nguyên tố } X = { x [U+F0BD] x > 2 } Mọi tập hợp đều chứa các phần tử thuộc vào một không gian xác định nào đó, ký hiệu là U. Không giantương ứng có thể được định nghĩa là một tập số nguyên, số thực, . . . Một trường hợp đặc biệt của tập hợp là tập hợp rỗng (empty set). Tập hợp này không có chứa bất kỳphần tử nào, ký hiệu bởi [U+F0C6] hoặc { }. Ta nói tập hợp A là tập hợp con (subset) của tập hợp B khi mọi phần tử của A là thành phần của B (ký hiệu A [U+F0CD] B). Ngược lại, A không là tập con của B (A [U+F0CB] B ). Thí dụ 1.3 : { 1, 2, 4 } [U+F0CD] { 1, 2, 3, 4, 5 } nhưng { 2, 4, 6 } [U+F0CB] { 1, 2, 3, 4, 5 } Có thể suy ra rằng tập hợp A [U+F0CD] U và [U+F0C6] [U+F0CD] A, [U+F022]A Hai tập hợp A và B được gọi là bằng nhau (A = B), khi A [U+F0CD] B và B [U+F0CD] A Thí dụ 1.4 : { 1, 2, 3, 4 } = { 2, 1, 4, 3 } nhưng { 1, 2, 3, 4 } [U+F0B9] { 2, 1, 3, 5 } Tập hợp tất cả các tập hợp con của tập A được gọi là tập lũy thừa (power set) của A và xác định bởi2A. Thí dụ 1.5 : Giả sử A = { 1, 2, 3 } 1 This content is available online at . 12 CHƯƠNG 1. BỔ TÚC TOÁN Thì 2A = { [U+F0C6], {1 }, {2 }, {3}, {1, 2}, {2, 3}, {3, 1}, {1, 2, 3} }1.1.2 Các phép toán trên tập hợpCác toán tử cơ bản trên tập hợp bao gồm các toán tử một ngôi (una ...