TRƯNG ĐẠI HỌC TÔN ĐC THNG
KHOA : CNTT-TƯD
BỘ MÔN : TOÁN


 

ĐỀ CƯƠNG MÔN HỌC
AUTOMAT VÀ NGÔN NGỮ HÌNH THC
Mã số môn học:
• Số tín chỉ : 3(30,15,0,90)
• Số tiết tổng : 45 LT: 30 BT: 15 TN(TH): 30 BTL(TL):
• Ngành đào tạo : Công nghệ thông tin, Toán tin ứng dụng, Điện - Điện tử
• Đánh giá :
Điểm thứ 1: 10% Kiểm tra trên lớp
Điểm thứ 2: 20% Kiểm tra trắc nghiệm giữa kỳ
Điểm thứ 1: 10% Kiểm tra viết cuối kỳ
• Môn tiên quyết : Cơ sở lập trình MS:
• Môn học trước : Toán rời rạc MS:
• Môn song hành : MS:
• Ghi chú khác :
Nội dung tóm tắt môn học:
- Mô hình toán học của ngôn ngữ. Phân loại ngôn ngữ.
- Khảo sát 2 lớp ngôn ngữ quan trọng: Ngôn ngữ chính qui và ngôn ngữ phi ngữ cảnh.
- Giới thiệu về máy Turing và khái niệm giải thuật. Luận đề Church.
Tài liệu tham khảo:
[1] C. Đ. Khánh, !"#$%&'%(%)*+*!%,%'$%)* -/0%12 ĐH Tôn Đức Thắng,
2009
[2] P. Linz, %3,%!%43'$5$-,$-67$,%'$%$, Lexington,1990
Cán bộ tham gia giảng dạy:
• TS Chu Đức Khánh, ĐH Tôn Đức Thắng

3.7. Tính chất của lớp các CFL.
3.8. Bổ đề bơm cho CFL.
[1] 18
89->;Sơ lược về máy Turing
4.1. Định nghĩa TM chuẩn.
4.2. TM và ngôn ngữ.
4.3. Các dạng tương đương của TM chuẩn.
4.4. LBA và ngôn ngữ cảm ngữ cảnh.
4.5. Luận đề Turing- Church.
4.6. Giới thiệu về Lý thuyết tính toán: Khái niệm bài toán
giải được.
[1], [2] 3 SV tự
đọc
Ngày phê duyệt:
Chủ nhiệm bộ môn (ngành) duyệt
?#@)*-!3AB%CD