ĐỀ CƯƠNG CHI TIẾT
Tên học phần: AUTOMAT VÀ NGÔN NGỮ HÌNH THỨC
(FORMAL LANGUAGES AND AUTOMATA)
2. Mã học phần: 2101012018
3. Số tín chỉ: 3(3,0,6)
4. Trình độ: dành cho sinh viên năm thứ 2
5. Phân bố thời gian:
- Lên lớp : 45 tiết
- Thực tập phòng thí nghiệm: 0 tiết
- Thực hành: 0
- Tự học: 90 tiết
6. Điều kiện tiên quyết: 2101011003 (a)
7. Mục tiêu của học phần:
Sau khi hoàn tất học phần này, sinh viên được cung cấp các kiến thức
căn bản về lý thuyết tính toán được áp dụng vào khoa học máy tính, hiểu
đuợc nguyên tắc điều hành tài nguyên máy tính, dịch chương trình, thiết kế
cơ sở dữ liệu, tạo máy tính và các chương trình nhanh hơn, rẻ hơn, dễ sử
dụng và bảo mật hơn.
8. Mô tả vắn tắt nội dung học phần:
Automat hữu hạn và ngôn ngữ chính qui. Automat đẩy xuống và ngôn
ngữ phi ngữ cảnh. Automat bị chặn tuyến tính và ngôn ngữ cảm ngữ cảnh.
Máy Turing. Các ứng dụng.
9. Nhiệm vụ của sinh viên:
Tham dự học, thảo luận, kiểm tra, thi theo qui chế 04/1999/QĐ-
BGD&ĐT, qui định 25/2006/QĐ-BGD&ĐT và qui chế học vụ hiện hành
của nhà trường
- Dự lớp: trên 75%
- Bài tập: trên lớp và ở nhà
- Khác: theo yêu cầu của giảng viên
10. Tài liệu học tập:
− Sách, giáo trình chính:

Thực
hành
Tự
học
1 Dẫn nhập 3 3 0 4
2 Automat hữu hạn 6 6 0 10
3 Ngôn ngữ và văn phạm chính qui 3 3 0 8
4
Các tính chất của ngôn ngữ chính
qui
3 3
0 8
5 Ngôn ngữ phi ngữ cảnh 6 6 0 12
6
Đơn giản hoá văn phạm phi ngữ
cảnh
6 6
0 12
7 Automat đẩy xuống 6 6 0 15
8
Các tính chất của ngôn ngữ phi ngữ
cảnh
4 4
0 8
9 Máy Turing 4 4 0 8
10
Sự phân cấp của các automat và
ngôn ngữ hình thức
4 4
0 5

7.4 Văn phạm phi ngữ cảnh đơn định
Chương 8. CÁC TÍNH CHẤT CỦA NGÔN NGỮ PHI NGỮ CẢNH
8.1 Các bổ đề bơm
8.2 Tính đóng
Chương 9. MÁY TURING
9.1 Máy Turing chuẩn
9.2 Kết hợp các máy Turing
9.3 Luận đề Turing
Chương 10. SỰ PHÂN CẤP CỦA CÁC AUTOMAT VÀ NGÔN NGỮ
HÌNH THỨC
10.1 Các ngôn ngữ đệ qui và khả liệt kê đệ qui
10.2 Văn phạm không hạn chế
10.3 Ngôn ngữ phi ngữ cảnh và automat bị chặn tuyến tính
14. Phê duyệt
Trưởng đơn vị đào tạo
Nguyễn Chí Hiếu
Tp. HCM, Ngày 16 tháng 7 năm 2007
Đại diện Tổ trưởng bộ môn
Nguyễn Quang Châu