Bài giảng Lí thuyết ngôn ngữ hình thức và ôtômát: Chương 2 - Nguyễn Thị Minh Huyền

Bài giảng "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" cung cấp cho người học các kiến thức: Ôtômát hữu hạn, tính đóng của lớp ngôn ngữ chính quy, biểu thức chính quy, điều kiện cần của ngôn ngữ chính quy,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Lí thuyết ngôn ngữ hình thức và ôtômát: Chương 2 - Nguyễn Thị Minh HuyềnLí thuyết ngôn ngữ hình thức và ôtômátChươ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ộiNgô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ạnNộ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 quyVí 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 S khi máy bật (P = ON). Khi tắt máy (P = OFF ), S khô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 P hoặ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, S 6= ∅ Σ 6= ∅ : bảng chữ cái vào s0 ∈ S trạ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 a thì 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 Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quyBiểu diễn ôtômat Biểu diễn bằng đồ thị chuyển (nguồn) Đỉnh vào, đỉnh ra/kết, cung 1 1 0 s1 s2 0 Ch2. NN chính quy& ôtômát hữu hạn 5 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quyNgôn ngữ đoán nhận bởi ôtômat hữu hạn, đơn định Hàm chuyển mở rộng δˆ : S × Σ∗ → S ˆ ) = p δ(p, ˆ ay) = δ(δ(p, ∀p ∈ S, a ∈ Σ, y ∈ Σ∗ : δ(p, ˆ a), y) Ngôn ngữ đoán nhận bởi ôtômat A: ˆ 0 , x) ∈ F } L(A) = {x ∈ Σ∗ |δ(s Ch2. NN chính quy& ôtômát hữu hạn 6 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quyTương đương giữa ôtômat và văn phạm chính quy Ôtômat hữu hạn, đơn định A tương đương văn phạm chính quy G: L(A) = L(G) Chuyển từ ôtômat sang văn phạm chính quy Chuyển từ văn phạm chính quy sang ôtômat G = ({a, b, c}, {S, A, B}, S, P), P gồm các quy tắc: S → aA|bA|cB A → cA|aB B → bB|a|c Ch2. NN chính quy& ôtômát hữu hạn 7 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, đơn định và ngôn ngữ chính quyBài tập Cho bảng chữ cái Σ = {a, b, c}, xây dựng ôtômat đoán nhận các ngôn ngữ sau: 1. L1 = {an |n ≥ 2} 2. L2 = {x ∈ Σ∗ ||x| ≥ 1} 3. L3 = {am b n c k |m ≥ 1, n ≥ 0, k ≥ 2} 4. L4 = {x ∈ Σ∗ ||x| lẻ} Ch2. NN chính quy& ôtômát hữu hạn 8 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, không đơn địnhÔtômát hữu hạn, không đơn định Khác với ôtômat đơn định ở hàm chuyển: δ : S × (Σ ∪ {}) → 2S δ(p, a) ⊆ S Biểu diễn bằng đồ thị (nguồn): Đỉnh vào, đỉnh ra/kết, cung rỗng, cung cốt yếu, đỉnh cốt yếu (có cung cốt yếu đi vào) Ngôn ngữ đoán nhận bởi ôtômat không đơn định: Mở rộng hàm chuyển như ôtômat đơn định L(A) = {x ∈ Σ∗ |δ(s0 , x) ∩ F 6= ∅} Ch2. NN chính quy& ôtômát hữu hạn 9 / 37 Ôtômát hữu hạn Ôtômát hữu hạn, không đơn địnhMột ...