Bài giảng "Tin học lí thuyết - Chương 2: Ngôn ngữ và sự phân cấp Chomsky" cung cấp cho người học các kiến thức: Khái niệm ngôn ngữ, cách biểu diễn ngôn ngữ, văn phạm, sự phân lớp văn phạm. Mời các bạn cùng tham khảo nội dung chi tiết.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Tin học lí thuyết: Chương 2 - Võ Huỳnh Trâm
- là số các ký hiệu tạo thành chuỗi
• abca = 4
ký hiệu , là chuỗi không có ký hiệu nào
• Khái niệm ngôn ngữ
• |ε| = 0
• Cách biểu diễn ngôn ngữ chuỗi v là chuỗi con của w nếu v ñược tạo
• Văn phạm bởi các ký hiệu liền kề nhau trong chuỗi w.
• Chuỗi 10 là chuỗi con của chuỗi 0 001
• Sự phân lớp văn phạm
là chuỗi con bất kỳ nằm ở ñầu chuỗi
là chuỗi con bất kỳ nằm ở cuối chuỗi
• Chuỗi abc có các tiền tố a, ab, abc
1 • Chuỗi 0246 có các hậu tố 6, 46, 246, 0246 3
là một thực thể trừu tượng mà ta là chuỗi ñược tạo thành bằng
không ñịnh nghĩa ñược một cách hình thức cách viết chuỗi thứ nhất, sau ñó viết chuỗi thứ hai, ...
• Các chữ cái a, b, c … hoặc các số 1, 2, 3 … •Nối ghép của chuỗi Long và Int là LongInt
•Nối kết của chuỗi rỗng: εw = wε = w (với mọi w)
• Là một tập (không rỗng) các ký hiệu nào ñó → ε là ñơn vị của phép nối kết
• Bộ chữ cái Latin {A, B, C, …, a, b, c, …, z} của chuỗi w, ký hiệu wR, là chuỗi
một chuỗi (hay một từ - word) trên bộ w ñược viết theo thứ tự ngược lại.
chữ cái Σ •w = abcd → wR = dcba εR = ε
• Là một dãy hữu hạn các ký hiệu của Σ
• Một ký hiệu có thể xuất hiện nhiều lần 2 4
Printed with FinePrint - purchase at www.fineprint.com
- • Ngôn ngữ tự nhiên: tiếng Việt, tiếng Anh, … L = Σ* - L
• Ngôn ngữ lập trình: Pascal, C/C++, …
• Là tập hợp các câu theo cấu trúc quy ñịnh nào ñó L1L2 = {w1w2 | w1 ∈ L1 và w2 ∈ L2} trên bộ chữ cái Σ1 ∪ Σ2
• Biểu thị các ý nghĩ, các sự kiện hay các khái niệm • LLL…LL = L (kết nối i lần trên cùng ngôn ngữ L)
i
• Bao gồm một tập các ký hiệu và các quy tắc ñể • L = {ε}
0
vận dụng chúng
5 7
Một ngôn ngữ (hình thức) L là một thành lập một ngôn ngữ
của các ký hiệu từ một bộ chữ cái Σ nào ñó. bằng cách kết nối các chuỗi (với số lượng bất kỳ) các
Ø và {ε} cũng ñược coi là ngôn ngữ chuỗi của một ngôn ngữ L cho trước
Ø ≠ {ε} và {Ø} ≠ {ε} Bao ñóng Kleene: L* = ∪ Li
∞
i
0
Σ Σ
+
=
∞ i
Bao ñóng dương (positive): L* = ∪ L
●
Σ* : tập hợp tất cả các chuỗi con, kể cả chuỗi rỗng
i
1
=
ε, sinh ra từ bộ chữ cái Σ.
L = L*L = LL* L* = L ∪ {ε}
+
+
●
Σ+ : tập hợp tất cả các chuỗi con, ngoại trừ chuỗi
rỗng ε, sinh ra từ bộ chữ cái Σ. cho L = {a, ba}
• L = {aa, aba, baa, baba}
2
Σ* = Σ+ + {ε} Σ+ = Σ* - {ε}
• L = {aaa, aaba, abaa, ababa, baaa,baaba, babaa, bababa}
3
●
Σ = {0,1} thì Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, …} và • L* = {ε, a, ba, aa, aba, baa, baba, aaa, aaba, …} 8
6
Σ+ = {0, 1, 00, 01, 10, 11, 000, …}
Printed with FinePrint - purchase at www.fineprint.com
- L = {aa, aba, baa, baba} nếu α→β là một luật sinh thì
L = {ai | i là số nguyên tố} γ α δ ⇒ γ βδ
nếu các chuỗi α1, α2, ...., αm ∈ Σ* và
α1 ⇒ α2, α2 ⇒ α3, ..., αm-1 ⇒ αm thì αm có thể ñược dẫn
• Cho phép biểu diễn ngôn ngữ một cách tổng quát
xuất từ α1
• Văn phạm: cơ chế sản sinh ra mọi chuỗi của ngôn
ngữ α1 ⇒* αm
• Automata: cơ chế cho phép ñoán nhận một chuỗi
bất kỳ có thuộc một ngôn ngữ L hay không
L (G) = {w | w ∈ T * và S ⇒* w}
là 2 văn phạm sinh ra cùng
9 một ngôn ngữ (G1 tương ñương G2 ⇔ L(G1)=L(G2) ) 11
Theo từ ñiển, văn phạm là một tập các quy tắc về cấu Bằng cách áp ñặt một số quy tắc hạn chế trên các luật
tạo từ và các quy tắc về cách thức liên kết từ lại thành sinh, Noam Chomsky ñề nghị một hệ thống phân loại
câu các văn phạm dựa vào tính chất của các luật sinh.
văn phạm cấu trúc G là một hệ thống gồm 4
thành phần G(V, T, P, S) không cần thỏa ñiều kiện ràng buộc nào
trên tập các luật sinh
• V (variables): tập các biến (VD: A, B, C, …)
• T (terminal): tập các ký hiệu kết thúc (V ∩ T = Ø)
nếu văn phạm G có các luật
(VD: a, b, c, …, w, x, y, ...)
sinh dạng α→β và |β| ≥ |α|
• P (production): tập luật sinh, dạng α→β với α, β ∈
(V ∪ T)*
có luật sinh dạng A→α với A là một
• S (start): ký hiệu bắt ñầu (S ⊂ V) 10 biến ñơn và α là chuỗi các ký hiệu thuộc (V ∪ T)* 12
Printed with FinePrint - purchase at www.fineprint.com
- văn phạm G( {S}, {a, b}, P, S )
có mọi luật sinh dạng tuyến tính phải hoặc
S → aSb
tuyến tính trái. P=
S → ab
• Tuyến tính phải: A → wB hoặc A → w
ðây là văn phạm loại 2 (dạng A→α )
• Tuyến tính trái: A → Bw hoặc A → w
Một dẫn xuất từ S có dạng:
Với A, B là các biến ñơn, w là chuỗi ký hiệu kết
thúc (có thể là rỗng) S → aSb → aaSbb → aaaSbbb → aaaabbbb = a4b4
Nếu ký hiệu L , L , L , L là các ngôn ngữ ñược sinh ra ⇒ L(G) = {anbn | n ≥ 1}
0
1
2
3
bởi văn phạm loại 0, 1, 2, 3, ta có:
L ⊂L ⊂L ⊂L
3
2
1
0
13 15
văn phạm G( {S, A}, {a, b}, P, S ) văn phạm G( {S, B, C}, {a, b, c}, P, S )
S → aS S → aSBC
S → aA S → aBC
P=
A → bA CB → BC
A→b P= aB → ab
bB → bb
ðây là văn phạm loại 3 (dạng tuyến tính phải) bC → bc
cC → cc
Một dẫn xuất từ S có dạng:
S → aS → aaS → aaaA → aaabA → aaabbA → ðây là văn phạm loại 1
aaabbbA → aaabbbb = a3 b4 Một dẫn xuất từ S: S → aSBC → aaBCBC → aabCBC →
⇒ L(G) = a b = {anbm | n,m ≥ 1} aabBCC → aabbCC → aabbcC → aabbcc=a2b2c2
+
+
⇒ L(G) = {anbncn | n ≥ 1}
14 16
Printed with FinePrint - purchase at www.fineprint.com
- là máy trừu tượng có cơ cấu và hoạt ñộng
ñơn giản nhưng có khả năng ñoán nhận ngôn ngữ
• Con người phải lập trình sẵn cho máy một ‘lộ trình’
ñể thực hiện
I
N
P
U
T
B
ñ
i
k
h
i
u
n
O
U
T
P
U
T
B
N
H
17
• Mỗi bước di chuyển chỉ ñược xác ñịnh duy nhất
bởi cấu hình hiện tại (hàm chuyển của automata là
ñơn trị)
• Tại mỗi bước di chuyển, nó có vài khả năng ñể lựa
chọn (hàm chuyển của automata là ña trị)
18
Printed with FinePrint - purchase at www.fineprint.com
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
