BỘ GD&ĐT CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
Trường đại học SPKT Độc lập – Tự do – Hạnh phúc
Khoa: CNTT *******
Chương trình Giáo dục đại học
Ngành đào tạo: Tin học cơ sở trính độ đào tạo: ĐH
Chương trình đào tạo: Công nghệ thông tin
Đề cương chi tiết học phần
1. Tên học phần: Automat và ngôn ngữ hình thức Mã học phần: AUFL330685
2. Tên Tiếng Anh: Automata and Formal Languages
3. Số tín chỉ: 3
4. Phân bố thời gian: (học kỳ 15 tuần) 3(3:0:6) (4)
5. Các giảng viên phụ trách học phần (5)
1/ GV phụ trách chính: Nguyễn Quang Ngọc
2/ Danh sách giảng viên cùng GD:
2.1/ Trần Công Tú
6. Điều kiện tham gia học tập học phần
Môn học trước: Kỹ thuật lập trình, toán cao cấp.
Môn học tiên quyết:
Khác: ……
7. Mô tả tóm tắt học phần
Học phần này cung cấp cho người học những kiến thức cơ bản về các lớp chuỗi, cung cấp
cho người học các thuật toán kiểm tra một chuỗi có thuộc một lớp cho trước hay không. Về mặt ứng
dụng học phần này là bộ phận cơ bản của trình biên dịch. Về mặt lý thuyết nó là cũng là bộ phận cơ
bản của tin học lý thuyết.
8. Chuẩn đầu ra của học phần (8)
Kiến thức:
8.1/ Trình bày được các khái niệm cơ bản của môn học như ngôn ngữ, Automat(dfa/nfa) ngôn ngữ
chính qui, biểu thức chính qui, ngữ pháp chính qui. Hiểu và ứng dụng được trong việc xác định một
ngôn ngữ không là chính qui.
8.2/ Thành thạo phương pháp chuyển một dfa sang dạng đồ thị , phương pháp rút gọn số trạng thái
trong dfa, phương pháp chuyển từ nfa sang dfa, phương pháp chuyển một dfa sang ngữ pháp chính

- Báo cáo : trình bày một cài đặt bằng ngôn ngữ C của một thuật toán xử lý chuỗi cho một bài
tóan cụ thể.
10. Tài liệu học tập (10)
- Sách, giáo trình chính:
- Sách (TLTK) tham khảo:
11. Tỷ lệ Phần trăm các thành phần điểm và các hình thức đánh giá sinh viên : (11)
- Đánh giá quá trình: 30% trong đó:
+ Dự lớp: 10%
+ Làm bài tập: 10%
+ Báo cáo : 10%
2
- Thi cuối học kỳ: 10% (thi tự luận, đề mở (tối thiểu 90 phút) (cộng là 100% = 10 điểm))
12. Thang điểm: 10
13. Kế hoạch thực hiện (Nội dung chi tiết) học phần theo tuần (13)
Tuần thứ 1-2: Chương 1: Automat hữu hạn (6/0/12) Dự kiến các CĐR được
thực hiện sau khi kết thúc
ND
A/ Tóm tắt các ND và PPGD trên lớp: (6) 8.1/ Trình bày được các khái
niệm cơ bản của môn học
như ngôn ngữ, ngôn ngữ
chính qui, Automat( dfa/nfa),
ngữ pháp.
8.2/ Thành thạo phương pháp
chuyển một dfa sang dạng đồ
thị , phương pháp rút gọn số
trạng thái trong dfa, phương
pháp chuyển từ nfa sang dfa.
Nội Dung (ND) GD trên lớp
+ Ngôn ngữ, ngữ pháp, Automat
+ Máy chấp nhận hữu hạn đơn định.

A/ Tóm tắt các ND và PPGD trên lớp: (6) 8.1/ Trình bày được khái niệm
3
về biểu thức chính qui và ngữ
pháp chính qui.
8.2/ Hiểu và thực hiện được các
phương pháp chuyển một biểu
thức chính qui sang dfa, chuyển
một dfa sang ngữ pháp chính
qui, chuyển một ngữ pháp chính
qui sang dfa
Nội Dung (ND) trên lớp:
+ Biểu thức chính qui
+ Biểu thức chính qui và ngôn ngữ chính qui
+ Ngữ pháp chính qui
+ Ngữ pháp chính qui và ngôn ngữ chính qui
Tóm tắt các PPGD:
+ Thuyết trình
+ Thảo luận nhóm
B/ Các nội dung cần tự học ở nhà: (12) Dự kiến các CĐR được thực
hiện sau khi kết thúc tự học
Các nội dung cần tự học:
+ Làm 05 bài tập được giao
+ Đọc phương pháp chuyển một dfa sang biểu thức chính
qui
-Liệt kê các tài liệu học tập cần thiết (yêu cầu phải
thống nhất với mục 11 nêu trên)
+ An introduction to formal languages and automata,
Peter Linz, University of California at Davis
8.2/ Thành thạo các phương
pháp chuyển một biểu thức

Tuần thứ 6-9: Chương 4:Ngữ pháp phi ngữ cảnh và
ngôn ngữ phi ngữ cảnh (12/0/24)
Dự kiến các CĐR được thực
hiện sau khi kết thúc ND
A/ Tóm tắt các ND và PPGD trên lớp: (12) 8.6/ Trình bày được các khái
niệm ngữ pháp phi ngữ cảnh,
ngôn ngữ phi ngữ cảnh, cây dẫn
xuất
Nội Dung (ND) trên lớp:
+ Ngữ pháp phi ngữ cảnh
+ Ngôn ngữ phi ngữ cảnh
+ Cây dẫn xuất
+ Cây dẫn xuất và dạng câu
+ Các phương pháp rút gọn luật sinh
+ Tính đóng của ngôn ngữ phi ngữ cảnh
+ Xác định một ngôn ngữ không là phi ngữ cảnh
Tóm tắt các PPGD:
+ Thuyết trình
+ Thảo luận nhóm
B/ Các nội dung cần tự học ở nhà: (24) Dự kiến các CĐR được thực
hiện sau khi kết thúc tự học
Các nội dung cần tự học:
+ Làm 08 bài tập được giao
-Liệt kê các tài liệu học tập cần thiết (yêu cầu phải
thống nhất với mục 11 nêu trên)
+ An introduction to formal languages and automata,
Peter Linz, University of California at Davis
8.7/ Xây dựng được một ngữ
pháp phi ngữ cảnh cho một
ngôn ngữ phi ngữ cảnh. Hiểu và

+ Thảo luận nhóm
B/ Các nội dung cần tự học ở nhà: (18) Dự kiến các CĐR được thực
hiện sau khi kết thúc tự học
Các nội dung cần tự học:
+ Làm 08 bài tập được giao
+ Cài đặt thuật toán cho 1 trong 08 bài tập trên
-Liệt kê các tài liệu học tập cần thiết (yêu cầu phải
thống nhất với mục 11 nêu trên)
+ An introduction to formal languages and automata,
Peter Linz, University of California at Davis
8.10/ Thành thạo phương pháp
chuyển một ngữ pháp phi ngữ
cảnh sang automat đẩy xuống
không đơn định.
Tuần thứ 13-15: Chương 6: Máy Turing( 9/0/18) Dự kiến các CĐR được thực
hiện sau khi kết thúc ND
A/ Tóm tắt các ND và PPGD trên lớp: (9) 8.11/ Trình bày được các khái
niệm máy Turing, tiên đề
Turing, ngôn ngữ đệ qui kể
được , ngôn ngữ đệ qui, ngữ
pháp không giới hạn, ngữ pháp
cảm ngữ cảnh.
8.12/ Hiểu được sự liên hệ giữa
ngữ pháp không giới hạn và
ngôn ngữ đệ qui kể được. Hiểu
được sự liên hệ giữa ngữ pháp
cảm ngữ cảnh và các ngôn ngữ
Nội Dung (ND) trên lớp:
+ Máy Turing
+ Tiên đề Turing

và ghi rõ họ tên)
Tổ trưởng Bộ môn:
Lấn 2: Nội Dung Cập nhật ĐCCT lần 2: ngày/tháng/năm <người cập nhật ký
và ghi rõ họ tên)
Tổ trưởng Bộ môn:
7
8