LÝ THUYẾT TÍNH TOÁN

INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA)

Bài 00. Giới thiệu

TIN331

GV: Nguyễn Ngọc Tú Tu.NguyenNgoc@hoasen.edu.vn

Mục tiêu môn học

 Cung cấp những kiến thức cơ bản về ngôn ngữ, văn

phạm và ôtômát.

 Cung cấp các phương pháp phân tích từ vựng, phân

tích cú pháp.

 Cơ sở cho việc tìm hiểu các ngôn ngữ lập trình.  Rèn luyện kỹ năng lập trình cho sinh viên

Cấu trúc môn học

 Thời gian

60 tiết

 30 tiết Lý thuyết + Bài tập  30 tiết Thực hành

Nội dung học

1. Giới thiệu về lý thuyết tính toán 2. Ôtômát hữu hạn 3. Ngôn ngữ chính qui và văn phạm chính qui 4. Các tính chất của ngôn ngữ chính qui 5. Ngôn ngữ phi ngữ cảnh 6. Đơn giản hóa văn phạm phi ngữ cảnh và các dạng

chuẩn

7. Ôtômát đẩy xuống 8. Các tính chất của ngôn ngữ phi ngữ cảnh 9. Máy Turing

Các nội dung liên quan

 Qui nạp  Phản chứng

 Ngôn ngữ lập trình  Trình biên dịch (*)  Toán tin học  Kỹ thuật chứng minh

 Kỹ thuật mô phỏng

Đánh giá

 3 phần đánh giá

40%

 Cuối kỳ (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

 Project (Hiện thực công cụ)  Bài tập định kỳ  Cộng điểm

30% + 10% 20% 10%

Tài liệu Tham khảo

2.

1. Giáo trình lý thuyết Ngôn ngữ Hình thức và

3.

Hồ Văn Quân [2012]. Automat - Introduction to Languages and The Theory of Computation, Fourth Edition. John C. Martin [2011] Introduction to Theory of Computation. Anil Maheshwari , Michiel Smid, [2012].