Bài giảng Lý thuyết tính toán: Bài 12 - Phạm Xuân Cường

Chia sẻ: Bạch Khinh Dạ Lưu | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

20
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết tính toán: Bài 12 - Phạm Xuân Cường cung cấp cho học viên các bài tập để các bạn ôn tập, nắm vững kiến thức về ngôn ngữ tương đương, biểu thức chính quy, đưa ra được biểu đồ trạng thái của DFA tương đương với NFA, đưa ra PDA đoán nhận ngôn ngữ,... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết tính toán: Bài 12 - Phạm Xuân Cường

LÝ THUYẾT TÍNH TOÁN BÀI 12: Ôn tập Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@tlu.edu.vn
Bài tập ôn tập Bài 1: Cho bộ chữ Σ= {a,b} a. Hãy đưa ra biểu đồ trạng thái của NFA đoán nhận ngôn ngữ tương đương với biểu thức chính quy b*ab*ab* b. Mô tả định nghĩa hình thức của NFA trên c. Hãy đưa ra biểu đồ trạng thái của DFA tương đương với NFA trên và mô tả định nghĩa hình thức d. Hãy mô tả ngôn ngữ mà NFA trên đoán nhận 1
Bài tập ôn tập Bài 2: a. Đưa ra 2 chuỗi mà NFA trên đoán nhận b. Đưa ra 2 chuỗi mà NFA trên không đoán nhận c. Mô tả ngôn ngữ mà NFA trên đoán nhận d. Chuyển đổi NFA trên thành DFA tương đương 2
Bài tập ôn tập Bài 3: Cho CFG sau: S = SaS | b Hãy đưa ra cây dẫn xuất cho chuỗi bababab Bài 4: Hãy đưa ra PDA đoán nhận ngôn ngữ an b m+n c m 3
Questions? 3