TAILIEUCHUNG - Bài tập ôn thi cuối học kỳ môn Lý thuyết ngôn ngữ hình thức và ôtômat

Bài tập ôn thi cuối học kỳ môn Lý thuyết ngôn ngữ hình thức và ôtômat đã tổng hợp lại toàn bộ kiến thức cơ bản đã học và một số bài tập để người học rèn luyện và vận dụng các kiến thức đã học vào thực tế. Mời các bạn cùng tham khảo. | Bài tập ôn tập thi cuối kì Môn Lý thuyết ngôn ngữ hình thức và ôtômat 1 Ngôn ngữ hình thức và văn phạm Phần bắt buộc ôn tập với tất cả các sinh viên. 1. Ôn tập các khái niệm liên quan tới ngôn ngữ và văn phạm hình thức ôtômat. 2. Ôn lại kĩ năng xây dựng văn phạm sinh ngôn ngữ đã cho. 3. Ôn lại kĩ năng tìm ngôn ngữ biết văn phạm sinh ngôn ngữ đó. 2 Ngôn ngữ chính quy Ôtômat hữu hạn trạng thái 1. Xây dựng otomat đơn định hữu hạn trạng thái đoán nhận các ngôn ngữ sau trên bảng chữ cái 0 1 a Tập các xâu trong đó số chữ cái 0 chia hết cho 3 số chữ cái 1 chia hết cho 5. b Tập các xâu bắt đầu bằng 1 khi đổi xâu nhị phân đó sang số nguyên thì được một số chia hết cho 5. c Tập các xâu trong đó số chữ cái 0 chia hết cho 2 số chữ cái 1 chia hết cho 3. d Tập các xâu bắt đầu bằng 1 khi đổi xâu nhị phân đó sang số nguyên thì được một số chia hết cho 4. 2. Cho otomat đơn định hữu hạn A S Σ s0 δ F và một chữ cái a Σ. Giả sử s S đều có δ s a s. a Chứng minh bằng quy nạp theo n rằng n 0 ta luôn có giá trị ˆ an s. hàm chuyển mở rộng δ s 1 b Chứng minh rằng hoặc a L A hoặc a L A . 3. Xây dựng otomat không đơn định hữu hạn trạng thái đoán nhận các ngôn ngữ trên bảng chữ cái 0 1 2 5 sau tận dụng tối đa lợi thế của việc xây dựng otomat không đơn định a Tập các xâu trong đó chữ số cuối cùng đã xuất hiện ít nhất 1 lần trước đó b Tập các xâu trong đó chữ số cuối cùng chưa hề xuất hiện trước đó Thực hiện thuật toán đơn định hóa hai otomat trên. Biểu thức chính quy 1. Cho biểu thức chính quy sau bc cb a bccb. Vẽ đồ thị chuyển viết dưới dạng hình thức ôtômat và viết văn phạm chính quy tương đương với biểu thức chính quy này. 2. Cho cú pháp của biểu thức chính quy trên Unix như sau Mỗi kí tự biểu diễn chính nó trừ các kí tự điều khiển metachar- acter bao gồm các kí tự sau - . ˆ Để biểu diễn các kí tự điều khiển thêm dấu vào trước 03a c 0 3 a b c ˆ 15 tập các kí tự khác 1 và 5 . biểu diễn kí tự bất kì ˆ và đánh dấu đầu và cuối dòng lt và gt đánh dấu đầu và cuối từ b đánh dấu biên từ B .

• Môi trường
• Đề thi học kỳ
• Lý thuyết ngôn ngữ hình thức
• Đề thi Lý thuyết ngôn ngữ hình thức
• Bài tập Lý thuyết ngôn ngữ hình thức
• Lý thuyết ngôn ngữ hình thức và ôtômat
• Đề thi học kỳ 1 môn Lý
• Đề thi học kỳ 1 lớp 8
• Đề thi học kỳ 1
• Đề thi học kỳ Vật lý 8
• Đề thi học kỳ Vật lý
• Đề thi học kỳ lớp 8
• Đề thi học kỳ 2
• Đề kiểm tra học kỳ
• Đề kiểm tra học kỳ 2 lớp 7
• Đề thi học kỳ Mĩ thuật 7
• Đề thi học kỳ môn Mĩ thuật
• Đề thi học kỳ lớp 7
• Đề kiểm tra học kỳ 1 lớp 8
• Đề thi học kỳ Mĩ thuật 8
• Đề kiểm tra học kỳ 2 lớp 9
• Đề thi học kỳ Mĩ thuật 9
• Đề thi học kỳ lớp 9
• Đề kiểm tra học kỳ 1 lớp 7