1 ページ
Trường Đại học Bách khoa Khoa Công Nghệ Thông Tin BÀI GIẢNG MÔN HỌC LÝ THUYẾT ÔTÔMÁT & NNHT Giảng Viên: Hồ Văn Quân E-mail: hcquan@dit.hcmut.edu.vn Web site: http://www.dit.hcmut.edu.vn/~hcquan/student.htm ThiNganHang.com
資料の内容
2 ページ
NỘI DUNG MÔN HỌC Chương 1 Giới thiệu về lý thuyết tính toán Chương 2 Ôtômát hữu hạn Chương 3 Ngôn ngữ chính qui và văn phạm chính qui Chương 4 Các tính chất của ngôn ngữ chính qui Chương 5 Ngôn ngữ phi ngữ cảnh Chương 6 Đơn giản hóa văn phạm phi ngữ cảnh và các dạng chuẩn Chương 7 Ôtômát đẩy xuống Chương 8 Các tính chất của ngôn ngữ phi ngữ cảnh Chương 9 Máy Turing Trang 2 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
3 ページ
TÀI LIỆU THAM KHẢO 1. Bài giảng lý thuyết Ngôn ngữ Hình thức và Automat - Hồ Văn Quân [2002]. 2. An Introduction to Formal Languages and Automata - Peter Linz [1990]. Trang 3 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
4 ページ
HÌNH THỨC ĐÁNH GIÁ Sẽ có thông báo cụ thể cho từng khóa học. Tuy nhiên, thường là như được cho bên dưới. Thi trắc nghiệm Thời gian: 120 phút Số lượng: 50 câu Được phép xem tài liệu trong 4 tờ giấy A4 Làm bài tập lớn cộng điểm (không bắt buộc) Nộp bài tập lớn và báo cáo vào cuối học kỳ Cộng tối đa 2 điểm Trang 4 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
5 ページ
CÁC MÔN LIÊN QUAN Ngôn ngữ lập trình Trình biên dịch (*) Toán tin học Trang 5 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
6 ページ
Chương 1 Giới thiệu về lý thuyết tính toán 1.1 Giới thiệu 1.2 Yêu cầu về kiến thức nền 1.3 Ba khái niệm cơ bản Ngôn ngữ (languages) Văn phạm (grammar) Ôtômát (máy tự động) 1.4 Một vài ứng dụng Trang 6 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
7 ページ
Giới thiệu Ôtômát Các mô hình tính toán tự động Ngôn ngữ hình thức (formal languages): Định nghĩa Phân loại ngôn ngữ Quan hệ với ôtômát Ứng dụng vào việc xây dựng các ngôn ngữ lập trình ... Trang 7 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
8 ページ
Yêu cầu về kiến thức nền Lý thuyết Tập hợp Đồ thị Kỹ thuật chứng minh Qui nạp Phản chứng Kỹ thuật mô phỏng Trang 8 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
9 ページ
Ba khái niệm cơ bản Ngôn ngữ (languages) Văn phạm (grammar) Ôtômát (automata) Trang 9 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
10 ページ
Ngôn ngữ Ngôn ngữ là gì? Các từ điển định nghĩa ngôn ngữ một cách không chính xác là một hệ thống thích hợp cho việc 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 qui tắc để vận dụng chúng. Định nghĩa trên chưa đủ chính xác để nghiên cứu về NNHT Chúng ta cần xây dựng một định nghĩa toán học cho khái niệm ngôn ngữ Trang 10 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
11 ページ
Các khái niệm Bảng chữ cái (alphabet), Σ Là tập hợp Σ hữu hạn không trống các kí hiệu (symbol). Ví dụ {A, B, C, ... , Z}: Bảng chữ cái La tinh. {α, β, γ, ... , ϕ}: Bảng chữ cái Hi Lạp. {0, 1, 2, ... , 9}: Bảng chữ số thập phân. {I, V, X, L, C, D, M}: Bảng chữ số La Mã. Trang 11 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
12 ページ
Các khái niệm (tt) Chuỗi (string), w Là một dãy hữu hạn các kí hiệu từ bảng chữ cái. Ví dụ Với Σ = {a, b}, thì abab và aaabbba là các chuỗi trên Σ. Qui ước Với một vài ngoại lệ, chúng ta sẽ sử dụng các chữ cái thường a, b, c, . . . cho các phần tử của Σ còn các chữ cái u, v, w, . . . cho các tên chuỗi. Trang 12 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
13 ページ
Các phép toán trên chuỗi Kết nối (concatenation), wv w = a1a2 ...an và v = b1b2...bm là chuỗi: wv = a1a2 ...anb1b2...bm Ðảo (reverse), wR Ðảo của chuỗi w = a1a2 ...an là chuỗi: wR = an...a2a1 Trang 13 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
14 ページ
Các khái niệm (tt) Cho chuỗi w = uv Tiếp đầu ngữ (prefix) u được gọi là tiếp đầu ngữ của w Tiếp vĩ ngữ (suffix) v được gọi lá tiếp vĩ ngữ của w Chiều dài của chuỗi w Là số kí hiệu trong chuỗi, và được kí hiệu là |w| Chuỗi trống (empty string) Là chuỗi không có kí hiệu nào, thường được kí hiệu là λ Trang 14 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
15 ページ
Các khái niệm (tt) Nhận xét 1 . Các quan hệ sau đây đúng với mọi w: |λ| = 0; λw = wλ = w 2 . Nếu u, v là các chuỗi thì : |uv| = |u| + |v| Lũy thừa (power), wn w là một chuỗi thì wn là một chuỗi nhận được bằng cách kết nối chuỗi w với chính nó n lần. wn = wLw w0 = λ 123 nlaàn Trang 15 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
16 ページ
Các khái niệm (tt) Σ*, Σ+ (bao đóng sao và bao đóng dương) Σ* là tập tất cả các chuỗi trên Σ kể cả chuỗi trống. Σ+ là tập tất cả các chuỗi trên Σ ngoại trừ chuỗi trống. Σ* = Σ+ ∪{λ} ; Σ+ = Σ* - {λ} Σ thì hữu hạn còn Σ+ và Σ* là vô hạn đếm được Trang 16 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
17 ページ
Định nghĩa ngôn ngữ Ngôn ngữ Là một tập con của Σ*, hay nói cách khác là một tập bất kỳ các câu trên bộ chữ cái. Ví dụ Cho Σ = {a, b} Σ* = {λ, a, b, aa, ab, ba, bb, aaa, aab, ...} Tập {a, aa, aab} là một ngôn ngữ trên Σ. Nó là một ngôn ngữ hữu hạn. Tập L = {anbn : n ≥ 0} cũng là một ngôn ngữ trên Σ. Nó là một ngôn ngữ vô hạn. Trang 17 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
18 ページ
Các phép toán trên ngôn ngữ Bù (complement), L Bù của ngôn ngữ L trên bảng chữ cái Σ, được kí hiệu là: L = Σ* - L Kết nối, L1L2 Cho 2 ngôn ngữ L1, L2. Kết nối của 2 ngôn ngữ L1, L2 là: L1L2 = { xy : x ∈ L1 , y ∈ L2 } Lũy thừa, Ln Lũy thừa bậc n của L, kí hiệu là Ln, là việc kết nối L với chính nó n lần L0 = {λ} Ln = LLL 123 nlaàn Trang 18 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
19 ページ
Các phép toán trên ngôn ngữ (tt) Ví dụ Cho L = {anbn : n ≥ 0}, thì L2 = {anbnambm : n ≥ 0 , m ≥ 0} Bao đóng-sao (star-closure) của L Kí hiệu là L* và được định nghĩa là L* = L0 ∪ L1 ∪ L2 ∪ ... Bao đóng dương (positive closure) của L Kí hiệu là L+ L+ = L1 ∪ L2 ∪ L3 ∪ ... Trang 19 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
20 ページ
Văn phạm Văn phạm là gì? Các từ điển định nghĩa văn phạm một cách không chính xác là một tập các qui tắc về cấu tạo từ và các qui tắc về cách liên kết các từ lại thành câu. Ví dụ Cho đoạn văn phạm tiếng Anh sau <sentence> → <noun phrase><predicate>, <noun phrase>→ <article><noun>, <predicate> → <verb>, <article> → a | the, <noun> → boy | dog, <verb> → runs | walks, Trang 20 Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin ThiNganHang.com
最初の20ページを表示しています。全文を見るには資料をダウンロードしてください。
コメント (0)
まだコメントはありません。最初のコメントを書きましょう！