logo
Chào mừng Khách! Để kích hoạt tất cả tính năng xin vui lòng Đăng nhập Hoặc Đăng ký.

Thông báo

Icon
Error

Tùy chọn
Xem bài viết cuối Đến bài chưa đọc đầu tiên
Offline Winzy_Atan  
#1 Đã gửi : 23/05/2017 lúc 05:26:03(UTC)
Winzy_Atan

Danh hiệu: Newbie

Nhóm: Registered
Gia nhập: 23-05-2017(UTC)
Bài viết: 1
Viet Nam
Đến từ: Hải Phòng

Chào các bạn! Mình có một số bài tập về ngôn ngữ hình thức và otomat cần phải làm, nhưng thực sự mình học môn này không được tốt cho lắm. Đây là những bài được giao, mình sẽ cố gắng tự nghĩ một số, nhưng đồng thời cũng mong các bạn giúp đỡ mình, được bài nào hay bài đó thôi. Mình cảm ơn trước.

1. Otomat hữu hạn trạng thái

a) 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}:
- 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.
- 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.
- 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.
- 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.

b) 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):
- 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 đó.
- 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.

2. Biểu thức chính quy

a) 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.

b) Hãy viết biểu thức chính quy và xây dựng otomat (nguồn) tương đương cho các xâu có dạng sau:
- Tập tên biến/tên hàm trong chương trình.
- Các số thập phân.
- Tập số thực dấu phẩy động.
- Tập các địa chỉ Internet IPv4 (32 bits) biểu diễn bằng chuỗi số trong hệ thập phân.

3. Định lý Myhill - Nerode

Xét tính chính quy của các ngôn ngữ sau:
- {0^n 1^m | 0 ≤ n ≤ m}
- {0^n 1^m | m,n ≥ 0}

4. Ngôn ngữ phi ngữ cảnh

Sử dụng định lí về điều kiện cần của ngôn ngữ phi ngữ cảnh, chứng minh các ngôn ngữ sau không phải là ngôn ngữ phi ngữ cảnh:
- L1 = {w ∈ {a,b,c}∗ : |w|a = |w|b = |w|c}
- L2 = {0^n 1^n 0^n 1^n : n ≥ 0}
- L3 = {0^(2^i), i ≥ 1}



Ai đang xem chủ đề này?
Di chuyển  
Bạn không thể tạo chủ đề mới trong diễn đàn này.
Bạn không thể trả lời chủ đề trong diễn đàn này.
Bạn không thể xóa bài của bạn trong diễn đàn này.
Bạn không thể sửa bài của bạn trong diễn đàn này.
Bạn không thể tạo bình chọn trong diễn đàn này.
Bạn không thể bỏ phiếu bình chọn trong diễn đàn này.

Vận hành bởi YAF.NET 2.2.2 | YAF.NET © 2003-2017, Yet Another Forum.NET
Thời gian xử lý trang này hết 0.079 giây.