Về Otomat Đẩy Xuống Và Ngôn Ngữ Phi Ngữ Cảnh
--- Bài mới hơn ---
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
Phạm Thị Thu Hà
VỀ OTOMAT ĐẨY XUỐNG
VÀ NGÔN NGHỮ PHI NGỮ CẢNH
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Hà Nội – Năm 2022
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
Phạm Thị Thu Hà
VỀ OTOMAT ĐẨY XUỐNG
VÀ NGÔN NGỮ PHI NGỮ CẢNH
Chuyên ngành: Toán học ứng dụng
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. Kiều Văn Hưng
Hà Nội – Năm 2022
Lời cảm ơn
Em xin được bày tỏ lòng biết ơn chân thành tới TS Kiều Văn Hưng, người
thầy đã truyền thụ kiến thức, tận tình giúp đỡ, hướng dẫn em trong suốt quá
trình học tập, nghiên cứu và hoàn thành khóa luận này.
Em xin được gửi lời cảm ơn tới các thầy cô giáo trường Đại học Sư phạm
Hà Nội 2, các thầy cô giáo khoa Toán đã giúp đỡ em trong quá trình học tập
tại trường và tạo điều kiện cho em hoàn thành đề tài khóa luận tốt nghiệp.
Trong quá trình nghiên cứu, không tránh khỏi những thiếu sót và hạn chế. Em
kính mong nhận được sự đóng góp ý kiến của các thầy giáo, cô giáo và toàn
thể bạn đọc để khóa luận được hoàn thiện hơn.
Hà Nội, ngày tháng 05 năm 2022
Sinh viên
Phạm Thị Thu Hà
Lời cam đoan
Em xin cam đoan dưới sự hướng dẫn của thầy giáo Kiều Văn Hưng khóa luận
của em được hoàn thành không trùng với bất kì đề tài nào khác.
Em cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện khóa luận
này đã được cảm ơn và các thông tin thu trích dẫn trong khóa luận đã được
chỉ rõ nguồn gốc.
Hà Nội, tháng 5 năm 2022
Sinh viên
Phạm Thị Thu Hà
ii
1 Văn phạm phi ngữ cảnh
1
1.2
1.1 Văn phạm phi ngữ cảnh . . . . . . . . . . . . . . . . .
1
1.1.1
Định nghĩa . . . . . . . . . . . . . . . . . . . . .
1
1.1.2
Ngôn ngữ sinh bởi văn phạm phi ngữ cảnh . . . .
2
1.1.3 Cây suy dẫn đầy đủ trong văn phạm phi ngữ cảnh
3
1.1.4
Quan hệ giữa dẫn xuất và cây suy dẫn . . . . . .
3
1.1.5
Văn phạm phi ngữ cảnh đa nghĩa . . . . . . . . .
5
1.1.6
Rút gọn các văn phạm phi ngữ cảnh . . . . . . .
7
Chuẩn hóa văn phạm phi ngữ cảnh . . . . . . . . . . . . 12
1.2.1
Dạng chuẩn Chomsky
……………
1.2.2
Dạng chuẩn Greibach . . . . . . . . . . . . . . . . 16
1.3 Bổ đề Bơm cho ngôn ngữ phi cảnh
1.4
…………
13
20
Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2 Otomat đẩy xuống
2.1 Mô tả otomat đẩy xuống . . . . . . . . . . . . . . . . . .
i
2.2
Otomat đẩy xuống không đơn định . . . . . . . . . . . . 35
2.2.1
Định nghĩa
…………………
2.2.2
Hàm chuyển . . . . . . . . . . . . . . . . . . . . . 36
2.2.3
Hình trạng . . . . . . . . . . . . . . . . . . . . . . 37
2.2.4
Ngôn ngữ đoán nhận bởi otomat đẩy xuống không
35
đơn định . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.5
Otomat đẩy xuống không đơn định và ngôn ngữ
phi ngữ cảnh
2.3
. . . . . . . . . . . . . . . . . . . . 40
Otomat đẩy xuống đơn định và ngôn ngữ phi ngữ cảnh
đơn định . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.4
Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Kết luận
Tài liệu tham khảo
ii
iii
Hà Nội, ngày 04/05/2016
Tác giả khóa luận
Phạm Thị Thu Hà
iv
x thuộc tập M
x ∈= M x không thuộc tập M
∈ x ∈ M với mọi x thuộc tập M
∈x
M∩N
tồn tại x
giao của hai tập hợp M và N
M∪N
hợp của hai tập hợp M và N
Σ
∈
tập mọi từ trên bảng chữ cái Σ
v
Chương 1
Văn phạm phi ngữ cảnh
1.1
Văn phạm phi ngữ cảnh
1.1.1
Định nghĩa
Văn phạm phi ngữ cảnh là một bộ sắp thứ tự gồm 4 thành phần:
G = ,
trong đó:
+ Σ là một bảng chữ cái, gọi là bảng chữ cái cơ bản (hay bảng chữ cái kết
thúc), mỗi phần tử của nó được gọi là một ký hiệu kết thúc hay ký hiệu cơ
bản.
+ ∆ là một bảng chữ cái, ∆ ∩ Σ = ∅, gọi là bảng ký hiệu phụ (hay bảng
chữ cái không kết thúc), mỗi phần tử của nó được gọi là một ký hiệu
không kết thúc hay ký hiệu phụ.
+ S ∈ ∆ được gọi là ký hiệu xuất phát hay tiên đề.
+ P là tập hợp các quy tắc sinh có dạng A → !, trong đó A ∈ ∆,
! ∈(Σ ∪ ∆).
Như vậy, các quy tắc trong văn phạm phi ngữ cảnh có vế trái chỉ chứa một
ký hiệu phụ còn vế phải là tùy ý, và được gọi là quy tắc phi ngữ
1
Khóa luận tốt nghiệp Đại học
Phạm Thị Thu Hà
cảnh.
Ví dụ 1.1. Cho văn phạm G1 = , trong đó:
P1 = {S → AB, A → aA, A → a, B → bB, B → b}.
G1 là văn phạm phi ngữ cảnh.
Ví dụ 1.2. Cho văn phạm G2 = , trong đó:
P2 = {S → SS, S → 0S1, S → 1S0, S → “}.
G2 là văn phạm phi ngữ cảnh.
1.1.2
Ngôn ngữ sinh bởi văn phạm phi ngữ cảnh
Định nghĩa 1.1. Cho văn phạm phi ngữ cảnh G = và
∈
; ! ∈ (Σ ∪ ∆) . Ta nói ! được suy dẫn trực tiếp từ
trong G, ký hiệu
∈
G
⊢ ! hay ngắn gọn là ⊢ !, nếu tồn tại quy tắc → ∈ P và ; ∈ (Σ ∪ ∆)
sao cho = , ! = .
Định nghĩa 1.2. Cho văn phạm phi ngữ cảnh G = và
∈
G
sao cho
!0 = , !k = ! và !i−1 ⊢ !i, với i = 1, 2,…, k.
Định nghĩa 1.3. Cho văn phạm phi ngữ cảnh G = . Từ
!∈Σ
∈
được gọi là sinh bởi văn phạm phi ngữ cảnh G, ký hiệu L(G), là
∈
tập hợp tất cả các từ sinh bởi văn phạm G: L(G) = {! ∈ Σ
G
Hai văn phạm G1 = và G2 = được gọi
là tương đương nếu L(G1) = L(G2).
Ví dụ 1.3. Xét văn phạm G =
--- Bài cũ hơn ---