CÂU HỎI ÔN TẬP MÔN: OTOMAT VÀ NGÔN NGỮ HÌNH THỨC
- PHẦN LÝ THUYẾT
[Ôn giữa kỳ từ câu 1
-4]
1.
Nêu các định nghĩa về hệ viết lại, suy dẫn trực tiếp, suy dẫn và biểu diễn [định nghĩa] ngôn ngữ bởi hệ viết lại
. 2.
M
ô tả phi hình thức, sự hoạt động và định nghĩa otomat hữu hạn đơn định
. 3.
M
ô tả phi hình thức, sự hoạt động và định nghĩa otomat hữu hạn không đơn định
. [
phải viết tương tự như câu 2 [ÔHĐ]
,
chỉ khác là
:
khi trình bày về hàm chuyển đa định và cách đoán nhận xâu
] 4.
Nêu định nghĩa và tính chất của biểu thức chính quy, cho hai ví dụ về biểu thức chính quy
[
ví dụ không quá đơn giản và phải
nói rõ chỉ định ngôn ngữ
nào
]
. Nêu nội d
u
ng hệ quả và định lý dẫn đến định nghĩa biểu thức chính quy.
5.
Nêu định nghĩa văn phạm ngữ cấu
,
văn phạm cảm ngữ cảnh,
văn phạm
phi
ngữ
cảnh và văn phạm
chính quy.
Tóm tắt các kết quả của lớp các ngôn ngữ
chính quy. 6.
Mô tả phi hình thứ
c và
sự hoạt động của otomat đẩy xuống
. 7.
Hãy mô tả phi hình thức, sự hoạt động và định nghĩa máy Turing.
8.
Mô tả phi hình thức, định
nghĩa otomat tuyến tính giới nội
và ngôn ngữ được đoán nhận bởi otomat tuyến tính giới nội.
II. PHẦN BÀI TẬP
,
Gồm các dạng sau
[Ôn giữa kỳ các dạng từ
câu 1-12]:
1.
Cách chia xâu, chia ngôn ngữ, ghép tiếp ngôn ngữ.
2.
Thành lập otomat hữu hạn đơn định đoán nhận
ngôn ngữ nào đó
[ví dụ, ngôn ngữ kết thúc bởi 00
trên bảng chữ {0, 1}
]. 3.
Thành lập otomat hữu hạn đơn định tương đương với otomat hữu hạn không đơn định cho trước.
4.
Dùng công thức
để tính BTCQ tương ứng với
các
biểu đồ chuyển
của các
ÔH
[hạ xuống k=1 thì tính nhẩm]
. 5.
Thành lập otomat hữu hạn tương đương với biểu thức chính quy nào đó.
6.
Tìm ngôn ngữ được sản sinh bởi văn phạm phi ngữ cảnh cho trước
. 7.
Thành lập văn phạm phi ngữ cảnh sản sinh ngôn ngữ
nào đó.
8.
Cho trước một văn phạm phi ngữ cảnh, tìm suy dẫn bên phải nhất, hoặc
suy
dẫn bên trái nhất của xâu nào đó và lập cây suy dẫn của suy dẫn đó.
Dưới đây là bài tập + lời giải môn Ngôn ngữ hình thức gồm 7 chương:
Chương 1: Văn phạm Chương 2: DFA và NFA Chương 3: Biểu thức chính quy Chương 4: Cực tiểu hoá Otomat Chương 5: Khử sự nhập nhằng của văn phạm Chương 6: Otomat đẩy xuống PDA Chương 7: Máy Turing
Link