Lí thuyết ngôn ngữ hình thức và ôtômát
Chương 2. Ngôn ngữ chính quy và ôtômát hữu hạn
Nguyễn Thị Minh Huyền
Khoa Toán - Cơ - Tin học
Trường Đại học Khoa học Tự nhiên Hà Nội
Ngôn ngữ chính quy
Văn phạm chính quy
Ôtômat hữu hạn
Nguồn (đồ thị chuyển)
Ch2. NN chính quy& ôtômát hữu hạn 1 / 37
Ôtômát hữu hạn
Nội dung
1. Ôtômát hữu hạn
Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy
Ôtômát hữu hạn, không đơn định
Đơn định hoá ôtômát
Bài tập
2. Tính đóng của lớp ngôn ngữ chính quy
3. Biểu thức chính quy
4. Điều kiện cần của ngôn ngữ chính quy
5. Điều kiện cần và đủ của ngôn ngữ chính quy
Ch2. NN chính quy& ôtômát hữu hạn 2 / 37
Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy
Ví dụ
Dàn máy phát thanh:
P(nút Power): 2 chế độ ON/OFF
S(nút chọn nguồn phát): chuyển đổi giữa 3 chế độ
CD/Tape/Radio. Chỉ thay đổi được trạng thái của Skhi
máy bật (P=ON). Khi tắt máy (P=OFF), Skhông thay
đổi giá trị
Ban đầu, máy tắt và ở chế độ CD.
Bài toán: Cho 1 dãy thao tác bấm nút Phoặc S. Dãy thao
tác này có cho phép đưa máy về trạng thái bật và ở chế độ
Radio không?
Ch2. NN chính quy& ôtômát hữu hạn 3 / 37
Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quy
Định nghĩa hình thức
Ôtômat hữu hạn, đơn định
Bộ năm A= (S,Σ,s0, δ, F)
S: tập hữu hạn các trạng thái, S6=∅
Σ6=∅: bảng chữ cái vào
s0∈Strạng thái khởi đầu
F⊆S: tập trạng thái kết
δ:S×Σ→S: hàm chuyển trạng thái
δ(p,a) = q: máy đang ở trạng thái p, nếu đọc được chữ cái
vào athì chuyển sang trạng thái q
biểu diễn dạng bảng
Ch2. NN chính quy& ôtômát hữu hạn 4 / 37