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

Chia sẻ: Đinh Y | Ngày: | Loại File: PDF | Số trang:41

Thêm vào BST

Báo xấu

28
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 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.

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 ngôn ngữ hình thức và ôtômát: Chương 2 - Nguyễn Thị Minh Huyền

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 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 quy Biể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 quy Ngô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 quy Tươ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 quy Bà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 định Một số khái niệm, tính chất Đơn định: hàm chuyển đơn trị Đầy đủ: hàm chuyển xác định khắp nơi Đơn định và đầy đủ: Trong bảng hàm chuyển mọi ô đều có 1 trạng thái 2 ôtômat/nguồn tương đương: đoán nhận/sinh cùng một ngôn ngữ Ôtômat đơn định tương đương với ôtômat không đơn định? Ch2. NN chính quy& ôtômát hữu hạn 10 / 37
Ôtômát hữu hạn Đơn định hoá ôtômát Đơn định hoá nguồn Cho nguồn không đơn định A. Xây dựng nguồn đơn định, đầy đủ A0 tương đương với A Kí hiệu: S(A) – tập tất cả các đỉnh, F (A) - tập đỉnh ra, D(A) – tập đỉnh cốt yếu N(p, q) : tập các từ đi từ đỉnh p đến đỉnh q Cho a ∈ Σ, δ(p, a) = {q ∈ D(A)|a ∈ N(p, q)} δ(M, a) = {∪δ(p, a), p ∈ M}, M ⊂ D(A) s00 = {s0 } Tập đỉnh của A0 : ∀M ∈ S(A0 ) đã xác định, a ∈ Σ, bổ sung cung ghi chữ cái a tới đỉnh δ(M, a) Tập đỉnh kết: F (A0 ) = {M ∈ S(A0 )|M ∩ F (A) 6= ∅} Ch2. NN chính quy& ôtômát hữu hạn 11 / 37
Ôtômát hữu hạn Đơn định hoá ôtômát Đơn định hóa ôtômat Cho ôtômat không đơn định A. Xây dựng ôtômat đơn định, đầy đủ A0 tương đương với A A = (S, Σ, s0 , δ, F ). Giả sử ∀s ∈ S, δ(s, ) = ∅ Xây dựng T : 2S × Σ → 2S ∀s ∈ S, ∀a ∈ Σ, T (s, a) = {s0 ∈ S|s0 ∈ δ(s, a)} ∀B ⊆ S, ∀a ∈ Σ, T (B, a) = {∪T (s, a)|s ∈ B} A0 = (S 0 , Σ, {s0 }, δ 0 , F 0 ) S 0 ⊆ 2S , xây dựng trong quá trình xây dựng hàm T ∀p ∈ S 0 : δ 0 (p, a) = T (p, a) F 0 = {p ∈ S 0 |p ∩ F 6= ∅} Ch2. NN chính quy& ôtômát hữu hạn 12 / 37
Ôtômát hữu hạn Đơn định hoá ôtômát Tóm tắt lại Ngôn ngữ chính quy có thể sinh/đoán nhận bởi: văn phạm chính quy ôtômat hữu hạn (luôn đưa về được dạng đơn định, đầy đủ) nguồn/đồ thị chuyển (luôn đưa về được dạng đơn định, đầy đủ) Ch2. NN chính quy& ôtômát hữu hạn 13 / 37
Ôtômát hữu hạn Bài tập Bài tập Xây dựng ôtômat đoán nhận một ngôn ngữ đã cho 1. Xây dựng 3 ôtômat đoán nhận các tập các số tự nhiên chia hết cho 2, cho 3 và cho 5. 2. Xây dựng ôtômat mô phỏng máy bán nước tự động dùng tiền xu (1000, 2000, 5000). Giá 1 lon nước ngọt là 5000, 1 chai nước suối là 3000. Ch2. NN chính quy& ôtômát hữu hạn 14 / 37
Tính đóng của lớp ngôn ngữ chính quy 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 15 / 37
Tính đóng của lớp ngôn ngữ chính quy Các phép toán trên nguồn Trang 53 -> 66 (giáo trình) Phép lấy phần bù Phép hợp Phép giao Phép lấy tích ghép Phép soi gương Phép lặp, lặp cắt Phép chia trái, chia phải Ch2. NN chính quy& ôtômát hữu hạn 16 / 37
Tính đóng của lớp ngôn ngữ chính quy Tính đóng của lớp ngôn ngữ chính quy Lớp ngôn ngữ chính quy đóng với các tất cả phép toán trên ngôn ngữ: hợp, giao, lấy phần bù, tích ghép, lặp, lặp cắt, soi gương, chia trái, chia phải. Ch2. NN chính quy& ôtômát hữu hạn 17 / 37
Biểu thức chính quy 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 18 / 37
Biểu thức chính quy Biểu thức chính quy (Regular expression) Định nghĩa (quy nạp) Cho Σ = {a1 , a2 , . . . , an } Cơ sở quy nạp: B = ai , B = , B = ∅ là các biểu thức chính quy, biểu diễn các ngôn ngữ {ai }, {}, ∅ Quy nạp: Cho B1 , B2 là các biểu thức chính quy Khi đó B1 .B2 , B1 ∪ B2 , B1∗ , (B1 ) cũng là các biểu thức chính quy Chỉ có các biểu thức được xác định như trên mới là các biểu thức chính quy trên bảng chữ cái Σ Ch2. NN chính quy& ôtômát hữu hạn 19 / 37