Trang 1
BÀI TẬP LẬP TRÌNH
MÔN LÝ THUYẾT AUTOMATA VÀ NGÔN NGỮ HÌNH THỨC
Giáo Viên: Hồ Văn Quân
Email: hcquan@dit.hcmut.edu.vn
Mục đích: Đây là một hình thức để khuyến khích các bạn sinh viên tham gia tìm hiểu môn học và
rèn luyện thêm kỹ năng lập trình.
Các qui định:
1. Các nhóm sẽ viết bằng một trong các ngôn ngữ sau: Delphi, Visual Basic, Visual C++, Java,
C#, Visual Basic.NET.
2. Các nhóm khác nhau nếu thực hiện cùng một đề thì nên viết bằng các ngôn ngữ khác nhau. Nếu
giáo viên phát hiện có việc copy mã nguồn thì các thành viên trong nhóm sẽ bị trừ 2 điểm vào
điểm thi học kỳ.
3. Các nhóm có liên quan với nhau phải phối hợp với nhau để thực hiện.
4. Mỗi nhóm không được quá 2n người cho đề n điểm.
5. Số điểm mỗi người trong nhóm thực hiện một đề sẽ bằng số điểm của đề chia cho số thành viên
của nhóm. Điểm cộng chỉ tính theo thang 0.5, 1.0, 1.5, … không tính tới 2 số lẽ chẳng hạn 0.75.
6. Mỗi người có thể tham gia nhiều nhóm, mỗi nhóm có thể thực hiện nhiều đề.
7. Tổng điểm cộng cuối học kỳ tối đa của mỗi người là 2 điểm. Nếu điểm cộng vượt quá 2 thì
phần vượt quá không được tính.
8. Các nhóm phải nộp sản phẩm vào ĐÚNG tuần 15 (tuần dự trữ), nếu nộp trước hay sau thời
gian trên thì không được xem xét. Sau khi nộp các sinh viên sẽ được thông báo ngày mang máy
lên trình bày với giáo viên. Các sinh viên không lên báo cáo sẽ không được cộng điểm. Mỗi đề
được trình bày trong vòng 5 đến 10 phút. Chú ý KHI MANG MÁY VÀO TRƯỜNG CÁC
SINH VIÊN PHẢI XIN “GIẤY MANG MÁY VÀO TRƯỜNG” Ở CHỖ CÁC CHÚ BẢO
VỆ TRƯỜNG.
9. Mỗi nhóm sẽ đặt chương trình trong một thư mục có tên là mã số sinh viên của các thành viên
trong nhóm, chẳng hạn 50012345_50054321_50056789. Trong thư mục này phải có file
tacgia.txt ghi rõ thông tin của các thành viên trong nhóm bao gồm họ tên, mã số, nhóm lớp,
làm bài tập nào, viết bằng ngôn ngữ gì. Ví dụ
Nguyễn Văn A 50012345 Nhóm 3A
Trần Văn B 50054321 Nhóm 2B
Làm các bài tập 1, 3, 6
Ngôn ngữ Visual C++
Hình thức nộp:
Cách 1, các nhóm sẽ ftp lên máy của giảng viên vào thời gian được qui định.
Cách 2, các nhóm sẽ gởi mail cho giáo viên theo địa chỉ hcquan@dit.hcmut.edu.vn với subject
chính xác như sau kể cả chữ hoa lẫn chữ thường “Bai tap lon Automata” vào thời gian được
qui định.
10. Sản phẩm nộp phải bao gồm source code và chương trình đã dịch sang mã máy. Source code
phải có chú thích rõ ràng ở từng phần chẳng hạn mục đích của từng phần và ý nghĩa của các
câu lệnh quan trọng. Ngoài ra nếu để chạy được chương trình cần có điều kiện gì về môi trường
hệ điều hành cũng như cần phải thực hiện các thao tác gì thì phải nêu rõ trong một file help.txt
đi kèm.
11. Các bài nộp không đúng qui định sẽ không được tính điểm.
12. Nếu các bạn sinh viên có ý kiến đóng góp gì trong vấn đề này thì có thể gởi mail về cho giáo
viên theo địa chỉ ở trên.
Trang 2
DANH SÁCH CÁC ĐỀ
Ñeà 1. (2đ)
Xây dựng bộ công cụ cho phép vẽ các đồ thị chuyển trạng thái (các đối tượng trong đồ thị có
thể thay đổi vị trí được), nhập các bảng truyền của các dfa, nfa. Lưu trữ và hiển thị lại chúng.
Các câu sau nếu có dùng đến nfa và dfa thì có thể kế thừa từ Đề 1. Ngoài ra chỉ chấp nhận hai
dạng biểu diễn của nfa và dfa là dạng đồ thị chuyển trạng thái và dạng bảng truyền.
Ñeà 2. (1đ)
Viết chương trình mô phỏng sự xử lý chuỗi của một nfa, dfa dưới dạng đồ thị chuyển trạng
thái.
Ñeà 3. (2đ)
Viết chương trình biến đổi một nfa thành dfa tương đương
Ñeà 4. (2đ)
Viết chương trình rút gọn một dfa thành dfa tối giản
Ñeà 5. (3đ)
Viết chương trình nhận dạng các token từ khoá (begin, end, var, if, then, for, to), số nguyên, số
thực, tên biến, phép gán, phép so sánh, các phép toán số học (+, -, *, /) của một chương trình
viết bằng Pascal. Chương trình phải được thực hiện theo mô hình lý thuyết automata.
Ñeà 6. (3đ)
Viết chương trình phân tích cú pháp, tạo và hiển thị cây cú pháp (dưới dạng đồ hoạ) của một
biểu thức chính qui.
Ñeà 7. (2đ)
Viết chương trình biến đổi một biểu thức chính qui thành nfa theo phương pháp cải tiến. (Có
thể kế thừa từ Đề 6.)
Ñeà 8. (3đ)
Viết chương trình biến đổi một biểu thức chính qui thành dfa trực tiếp không thông qua nfa.
(Có thể kế thừa từ Đề 6.)
Ñeà 9. (2đ)
Viết chương trình biến đổi một nfa thành văn phạm tuyến tính phải, văn phạm tuyến tính trái và
ngược lại.
Ñeà 10. (2đ)
Viết chương trình thực hiện giao của hai dfa, hiệu của hai dfa.
Ñeà 11. (2đ)
Viết chương trình thực hiện thương đúng của hai dfa.
Ñeà 12. (3đ)
Viết chương trình kiểm tra hai dfa có tương đương nhau không.
Ñeà 13. (3đ)
Ứng dụng automata hữu hạn, viết chương trình chuyển mã của các file text giữa ít nhất 3 bảng
mã thông dụng hiện nay VNI, Unicode, ...
Ñeà 14. (3đ)
Ứng dụng automata hữu hạn viết chương trình đổi nhiều tên file cùng lúc từ mẫu này sang mẫu
khác. (Tạo ra các phép toán thuận tiện hơn cho người sử dụng dựa vào 3 phép toán cơ bản của
biểu thức chính qui. Tham khảo thêm ngôn ngữ Perl để biết thêm chi tiết)
Ñeà 15. (5đ)
Ứng dụng automata hữu hạn viết chương trình driver cho bộ gõ tiếng Việt hỗ trợ hai cách gõ
VNI, Telex và hỗ trợ ít nhất 3 bảng mã thông dụng hiện nay VNI, Unicode, ...
Ñeà 16. (2đ)
Viết các chương trình loại bỏ lần lượt và loại bỏ đồng thời ba loại luật sinh vô dụng, trống và
đơn vị.
Ñeà 17. (3đ)
Trang 3
Viết các chương trình biến đổi một văn phạm bất kỳ thành văn phạm có dạng Chomsky và
Greibach
Ñeà 18. (1đ)
Cho biết dẫn xuất, viết chương trình hiển thị dẫn xuất dưới dạng cây.
Ñeà 19. (2đ)
Viết chương trình phân tích cú pháp theo phương pháp vét cạn. Có trình bày tuần tự các bước
phân tích và dẫn xuất nếu có.
Ñeà 20. (3đ)
Viết chương trình phân tích cú pháp theo phương pháp CYK. Có trình bày các bước tính toán
và dẫn xuất nếu có.
Ñeà 21. (4đ)
Viết chương trình phân tích cú pháp theo phương pháp Earley. Có trình bày các bước tính toán
và dẫn xuất nếu có.
Ñeà 22. (2đ)
Xây dựng bộ công cụ cho phép nhập, vẽ các npda, dpda (các đối tượng trong đồ thị có thể thay
đổi vị trí được). Lưu trữ và hiển thị lại chúng.
Ñeà 23. (3đ)
Viết chương trình mô phỏng hoạt động của một npda, dpda bằng hình ảnh và bằng đồ thị
chuyển trạng thái.
Ñeà 24. (2đ)
Viết chương trình biến đổi một văn phạm phi ngữ cảnh thành một npda.
Ñeà 25. (3đ)
Viết chương trình biến đổi một npda thành một văn phạm phi ngữ cảnh.
Ñeà 26. (4đ)
Viết chương trình phân tích cú pháp cho ngôn ngữ Pascal đơn giản (bao gồm các khai báo hàm,
thủ tục, khai báo biến, begin, end, lệnh if, lệnh lặp for, repeat … until, while … do, các phép so
sánh, các phép toán số học).
Ñeà 27. (3đ)
Tìm hiểu các hàm xử lý chuỗi của ngôn ngữ Perl. Xây dựng lại một số hàm này (khoảng 10
hàm) cho các ngôn ngữ khác.