Xem mẫu
- Chào mọi người !
Chà ườ
Chào
Ngôn ngữ hình thức và Ôtômat
Hello Everyone!
(Formal Language & Automata)
Bonjour Tout le Monde !
PGS.TS. Phan Huy Khánh
Khá
他好!
khanhph@vnn.vn, phk@ud.edu.vn
khanhph@vnn.vn,
Chương 1 M ở đầ u Привет Kаждый !
2/38
2/38
Ta sẽ học những buổi mô ?
Trường ĐHSP : 05CTT12
Trườ
(Hai lớp trưởng quyết định) :
ưở
Chiều thứ Hai hàng tuần, tại A5-104, 13H30
hà A5-
Chi
Những buổi đầu :
Nh
Chiều thứ Hai 14/01
Chi
To Start…
Sáng thứ Bảy, 26/01/2008, 7H00
Sau Tết, t.29, 13H30, 25/02/08
Sau
“One picture is worth more than ten thousand words”
Chinese Proverb
4/38
4/38
Ghi chép như thế nào ?
ché
Một vài “chuyện nhỏ” bắt đầu môn học
và
Có nên ghi bài giảng trên lớp vào sổ, vở học trò ?
bà và
Thủ tục “chào hỏi” :
chà
Th
Học bằng slide cần có TLTK+ cách ghi hợp lý
có cá
Vào lớp muộn, hoặc ra khỏi lớp, không cần xin phépphé
Nếu không sẽ xảy ra hiện tượng “THỪA TAY”, “để tay ở
ượ TAY”
Khi Giảng viên (GV) hỏi, cần :
Khi
nhà”
nhà”
Nói rõ và to giọng để cả lớp cùng nghe được
và cù ượ
Ghi bài giảng trên lớp vào giấy rời A4
Ghi bà và
Khi trả lời, cần thực hiện ngay :
Khi
Từ chối, không biết, hoặc trả lời trực tiếp vào câu hỏi
và Mỗi môn học một tập giấy A4, có màu đánh dấu phân biệt
có
Chuẩn bị học :
Chu Nguyên tắc thao tác tiếp thụ tri thức và ứng dụng :
tá và
Nguyên
Lớp sạch sẽ (mọi nghĩa), sẵn sàng cho buổi dạy
sà Thu nhặt, liệt kê, vun xới
Thu
Ngồi tập trung gần tôi, không ngồi kiểu “gió đưa ao bèo...”
gió bè ...”
Ng Phân loại, sắp xếp
Phân
Giúp GV chuẩn bị màn hình, đèn chiếu, ổ cắm điện...
Giú hì Khoanh vùng, giới hạn
Khoanh vù
Kết thúc môn học :
thú Chỉ định, lựa chọn, tìm kiếm
tì
Ch
Giúp GV dọn dẹp màn hình, đèn chiếu, ổ cắm điện...
Giú mà hì Vận dụng, hoàn thiện, làm giàu tri thức
hoà là già
Tìm kiếm phương pháp học tập hiệu quả
phá
Phát huy các giác quan : mắtn, tain, miệngn, mũin, tayn ...
Phá cá giá ...
5/38
5/38 6/38
6/38
1
- Để có thể “tốc ký”
ký” Mục đích môn học
Dùng Sử dụng bảng viết tắt (BVT) : Học phần cung cấp cơ sở toán học của các phương pháp
toá cá phá
tự định nghĩa chữ viết tắt của riêng mình
mì hình thức trong việc xây dựng các ngôn ngữ lập trình
cá trì
Ví dụ : ql = quản lý Giúp sinh viên hiểu được những yếu tố cơ bản của một
Giú ượ
pp = phương pháp
phá ngôn ngữ hình thức như bảng chữ, từ vụng, cú pháp và
cú phá và
ngữ nghĩa
pp+ = phân phối
Học phần trình bày các công cụ chủ yếu để làm việc với
trì bà cá
= người...
ng ườ
các ngôn ngữ hình thức là văn phạm và ôtômat, phân loại
là và
Luôn mang BVT theo mình, mọi lúc mọi nơi
mì lú
Luôn
ngôn ngữ của Chomsky :
Chỉ chọn ghi các ý chính, hay từ khoá
cá chí khoá
Ch
Ngôn ngữ chính quy
chí
Ngôn
Không nhất thiết ghi cả câu
Không
Ngôn ngữ phi ngữ cảnh
Ngôn
Tìm mọi cách đễ vẽ, thay vì chỉ viết !
cá vì Ngôn ngữ cảm ngữ cảnh
Ngôn
Ngôn ngữ loại 0 (gần gũi với ngôn ngữ tự nhiên)
Ngôn
7/38
7/38 8/38
8/38
Kiến thức yêu cầu Đánh giá kết quả học tập
giá
Môn học yêu cầu kiến thức tiên quyết : Toán cho Tin học
Toá
Môn Yêu cầu :
Yêu
Lý thuyết
Lý Hiiểu nội dung trình bày trên lớp
trì bà
H
Tập hợp
Thực hiện các bài tập về nhà
cá nhà
Th
Đồ thị
Khả năng thực hành
hà
Kh
Kỹ thuật chứng minh
Tinh thần thái độ và năng lực học tập
thá
Tinh
Qui nạp
Nghe giảng, ghi chép
ché
Nghe
Phản chứng
Trả lời và đặt câu hỏi
và
Tr
Kỹ thuật mô phỏng
Tham khảo tài liệu, truy cập internet
tà
Georg Cantor (1845–1918) Tham
Các kiến thức cần thiết khác :
khá Founder of Modern Set Theory
Tham gia học nhóm, tập thảo luận và thuyết trình
nhó và trì
Tham
Cơ sở Lập trình
trì
…
Môn học đòi hỏi một số kỹ năng :
Môn
Kiiểm tra giữa kỳ : Bài thi viết 15-30 phút
Bà 15- phú
K
Khả năng đọc hiểu vấn đề
Kh
Kiiểm tra cuối kỳ : Bài thi viết 60-75 phút
Bà 60- phú
K
Trình bày diễn đạt vấn đề (nghệ thuật !)
Trì bà
Khả năng thảo luận, làm việc theo nhóm...
là nhó
Kh
9/38
9/38 10/38
10/38
Nội dung môn học Tài liệu tham khảo Gặp cô Hương, văn
thư khoa CNTT
Giáo trình + Bài giảng trên lớp
Giá trì Bà
Chương 1 Mở đầu
(chúng mình ?)
Tài liệu
Nguyễn Văn Ba, Ngôn ngữ hình thức, NXBKH&KT, 2002.
Ba,
Nguy
Chương 2 Ôtômat hữu hạn (ôhh/ôh2/ô2h)
SM. D. Davis, E. J. Weyuker, Computability, Complexity and
Computability,
SM.
languages, Academic Press, 1983
Chương 3 Văn phạm chính qui (VPCQ)
chí J. E. Hopcroft, J. D. Ulman, Introduction to Automata Theory,
Theory,
Introduction
J.
Languages and Computation, Addison - Wesley, 1979
Phan Huy Khánh. Lý thuyết ngôn ngữ hình thức và ôtômát
ôtômá
Chương 4 Ôtômat đẩy xuống (ôđx)
(ô x) Lý
Khá
Phan
Tài liệu lưu hành nội bộ
hà
Hồ Văn Quân. Giáo trình lý thuyết ôtômát và ngôn ngữ hình
Quân. Giá trì ôtômá và
Chương 5 Máy Turing (MT) thức. NXBĐHQG HCM, 2002
HCM,
NXB
A. Salomaa, Nhập môn tin học, lý thuyết tính toán và ôtômat.
tí toá
Nh
A.
NXB Khoa học Kỹ thuật, Hà nội 1992
Hà
Internet: tìm kiếm Google.com.vn, wikipedia
Internet: tì
11/38
11/38 12/38
12/38
2
- Vài dòng lịch sử M ở đ ầu ☺
Chương 1
Cantor (1845-1918) Một số khái niệm
khá
“Nếu tôi có một số thành công nhất địịnh trong
“Nếu tôi có một số thành công nhất đ nh trong
Lý thuyết tập hợp
toán học thì đó là vì tôi luôn thấy nó rất khó” Bảng chữ (Σ)
toán học thì đó là vì tôi luôn thấy nó rất khó”
Hilbert (1862-1943) Hilbert
Hilbert
Câu (xâu)
Câu
Toán học chặt chẽ
Ngôn ngữ
Ngôn
Gödel (1906-1978)
Mô tả ngôn ngữ
Mô
Lý thuyết về tính không đầy đủ
Các phép toán (θ) trên ngôn ngữ (ng2)
phé toá
Church, Kleene, Post, Markov, von Neumann, Turing
Biiểu thức chính qui (BTCQ)
chí
B
CM từ đlý mô (Preuves de quels théorèmes)?
CM với thtoán mô (Avec quels algorithmes)?ta thật ngắn
“Tầm nhìn ta thật ngắn
“Tầm nhìn
Các ngôn ngữ phi chính qui
chí
mà đã thấy bao thứ để làm”
mà đã thấy bao thứ để làm”
Turing (1912-1954) Alan Turing Vấn đề biểu diễn ngôn ngữ
Alan Turing
Máy Turing
McCulloch, Pitts
Mạng nơ-ron nhân tạo
Chomsky 13/38
13/38 14/38
14/38
Mô hình toán học mô tả ngôn ngữ - hình thức hoá ngôn ngữ
Câu trên bảng chữ Σ
Bảng chữ và câu
Bảng chữ (alphabet) : Cho trước một bảng chữ Σ nào đó
Cho ướ
là một tập hữu hạn các ký tự (characters), hay ký tượng/
cá ượ
Một câu (phrase, word), hay xâu (string), trên Σ :
câu xâu
ký hiệu (symbol), ký hiệu bởi chữ cái Hy lạp Σ
là một dãy hữu hạn các phần tử của Σ,
cá
Kích thước của bảng chữ là số phần tử của bảng chữ đó,
ướ
ký hiệu bởi w (hay x, y, u, v...)
ký hiệu |Σ|, hay Card(Σ) (Cardinality)
Ví dụ một số bảng chữ Σ : Độ dài của một câu là số ký tự có mặt trong câu,
là
ký hiệu là |w| hay length(w)
là
{#} |=1
Độ dài câu là hữu hạn,
là
|Σ| = 2
{ 0, 1 }
nhưng không hạn chế là có bao nhiêu ký tự
{ ♣, ♠, ♦, ♥ } |Σ| = 4
Chữ số thập phân, |Σ| = 10
{0, 1, 2, ... , 9} Một câu có thể có từ 0 đến n ký tự tuỳ ý
có
{I, V, X, L, C, D, M} Chữ số La Mã
Câu có độ dài bằng 0 được gọi là câu rỗng (empty word),
Câu có ượ là
{aA, bB, cC, ... , zZ} Chữ cái La tinh
ký hiệu ε, hoặc e, hoặc λ hoặc ω
{αΑ, βΒ, χΧ, ... , ζΖ} chữ cái Hi Lạp
Bảng mã ASCII
15/38
15/38 16/38
16/38
Ví dụ về câu trên bảng chữ Σ Phép ghép tiếp các câu
Phé ghé cá
Cho hai câu u và v trên Σ
và
Ví dụ Cho
Phép ghép tiếp (Concatenation) của u và v là câu w = uv
Bảng chữ Σ Câu trên Σ Phé ghé và là
Nghĩa là câu w gồm hai phần :
Ngh là
ε, 0, 1, 00, 01, 10, 11, 100...
{ 0, 1 }
u đgl là tiền tố (prefix)
là
{ a....z } a, ab, zt, computer
ab
rồi đến v là hậu tố (postfix) của w
là
{ 0, ..., 7, ♠, ♣, ♦, ♥ } 4♣3♦2♠, 1234, ♣♠
♣♠
ASCII Một chương trình C, Pascal, Java, VB...
trì Trường hợp câu w = xuy là ghép tiếp của ba câu x, u, y,
Trườ là ghé u, y,
u đgl trung tố (infix) của w
Cho một câu w có có |w|=n, người ta có thể trích ra từ w
có |w|=n, ườ có trí
Cho
một ký tự nào đó có vị trí xác định trong phạm vi 1..n
trí Người ta còn gọi câu rỗng ε là câu đơn vị
đơ
Ngườ
vì có εw = wε = w
Ví dụ câu w=aaabbaabbba có |w|=11,
có
với w là một câu bất kỳ trên Σ
là
có thể trích ra các ký tự :
trí cá
w(1) = a, ..., w(4) = b, ..., w(11) = a
Returning
17/38
17/38 18/38
18/38
3
- Các phép toán khác trên xâu
phé toá khá Khái niệm ngôn ngữ
Khá
Một ngôn ngữ hình thức (nói gọn ngôn ngữ) :
(nó
Cho các câu w trên Σ
Cho cá
là tập hợp các câu
cá
Phép Đảo ngược (Reversion) một câu w, ký hiệu
Phé ượ wR : được xây dựng trên cùng một bảng chữ đã cho Σ
đượ cù
Là câu w được viết theo thứ tự ngược lại
ượ ượ Ví dụ :
Rõ ràng εR = ε
Rõ rà Σ* là ngôn ngữ gồm tập tất cả các xâu trên bảng chữ Σ
kể cả xâu rỗng
wR = w đgl câu đối xứng : OMO, akitOMOtika...
akitOMOtika...
Σ+ là ngôn ngữ gồm tập tất cả các xâu trên bảng chữ Σ
KHÔNG CÓ xâu rỗng
CÓ
Phép Lũy thừa (power) xâu
Phé Σ+ = Σ* - ε
Chú ý {ε} ≠ ∅
∅ là ngôn ngữ trống (tập trống)
wn = ww…w (n lần)
ww… Quy ước chỉ định một câu
Ví dụ
w0 = ε với mọi w (denotation)
L1 = {a, ab, abb, bba, bbb} là ngôn ngữ hữu hạn trên {a, b}
là
L1
L2 = {(ab)n | n > 0} là ngôn ngữ vô hạn trên {a, b}
là
L2
19/38
19/38 20/38
20/38
Các phép toán trên ngôn ngữ
phé toá Các phép toán trên ngôn ngữ
phé toá
Phép ghép nối :
Phé ghé
Ngôn ngữ là một tập hợp do đó có thể áp dụng các phép toán
Ngôn cá phé toá
trên tập hợp : L1L2 = = {w | w = uv, u ∈ L1 và v ∈ L2}
và
L1L2
∈∉
Đối với các phần tử :
cá Phép nghịch đảo :
Phé
∩∪⊂⊆⊄⊃⊇
Đối với ngôn ngữ :
ngôn LR = {w | wR ∈ L}
Cho L1, L2 và L là các ngôn ngữ, các phép toán:
và là cá phé toá
Cho Phép lũy thừa :
Phé
Ghép nối L1 có m
Phép hợp
Phé Ln = LL…L (n lần)
LL… câu, và L2 có n câu,
L1 ∪ L2 = {w | w ∈ L1 hoặc w ∈ L2}
L1
Li = LLi-1 = Li-1L với i>0 được ngng có m.n câu
???
Phép giao
Phé
L0 = { ε }
L1 ∩ L2 = {w | w ∈ L1 và w ∈ L2}
và L1 L2
L1 Là bản số của tích ĐêCac
Là bản số của tích ĐêCac
Ví dụ :
Phép hiệu
Phé (Cartesian Product)
(Cartesian Product)
Cho L = { tic, tac, toe } khi đó :
tic, tac, toe
Cho
L1 – L2 = {w | w ∈ L1 và w ∉ L2}
và
L1
L2 = LL
L
Phép bù
Phé bù = { tictic, tictac, tictoe, tactic, tactac, tactoe, toetic, toetac, toetoe }
toetac,
L’ = {w | w ∉ L} hoặc L’ = Σ* - L
L’
21/38
21/38 22/38
22/38
Các phép toán trên ngôn ngữ
phé toá Các ngôn ngữ chính quy (NNCQ)
chí
Phép bao đóng (closure) :
Phé ℜ tập hợp các ngôn ngữ chính quy (Regular Languages)
chí
cá ngôn
∞
i
UL
L* = L 0 ∪ L 1 ∪ … ∪ Ln ∪ … = trên Σ :
i= 0
Phép bao đóng dương :
Phé Được định nghĩa dựa trên các ngôn ngữ sơ cấp
Đượ cá
∞
i
UL và các phép toán hội, ghép và đóng lặp *
phé toá ghé và
L + = L1 ∪ L 2 ∪ … ∪ L n ∪ … =
i=1
Là tập hợp nhỏ nhất (chứa ít phần tử nhất) các ngôn ngữ
cá
Nhận xét :
Nh xé
thõa mãn các điều kiện sau :
cá
L+ = LL* = L*L
1. ∅ ∈ ℜ, {ε}∈ℜ
L * = L+ ∪ { ε }
2. { a } ∈ ℜ với ∀a ∈ Σ
Ví dụ :
3. Nếu A, B ∈ ℜ, thì A∪B, A.B và A* ∈ ℜ
thì và
Cho L = { tic, tac, toe } khi đó :
tic, tac, toe
Cho
Rõ ràng ℜ là tập hợp bé nhất do được xây dựng từ các tập
Rõ rà bé ượ
L* = { ε, tic, tac, toe, tictic, tictac, tictoe, tactic, tactac, tactoe,
sơ cấp ∅, { ε } và { a } bởi các phép hội, ghép và bao đóng
và cá phé ghé và bao
toetic, toetac, toetoe, tictictic, tictictac, ... }
23/38
23/38 24/38
24/38
4
- Biểu thức chính quy (BTCQ)
chí Biểu diễn ngôn ngữ bởi biểu thức chính qui
chí
Người ta sử dụng các biiểu thức chính quy (Regular
chí
cá b Ngôn ngữ L(ξ) được biểu diễn (hay được chỉ định)
Ngườ đượ (hay ượ
Ngôn
Expressions) để biểu diễn các ngôn ngữ chính qui trên Σ
cá chí bởi BTCQ ξ theo các bước quy nạp như sau :
cá ướ
Qui tắc xây dựng BTCQ trên Σ là các biểu thức được tạo
ượ
Qui 1. L(∅) = ∅, L(ε) = { ε }, L(a) = { a } cho ∀a ∈Σ
∈Σ
thành theo các bước quy nạp như sau :
thà cá ướ 2. L((α ∪ β)) = L(α) ∪ L(β)
(2)
1. ∅, ε và a, với mọi phần tử a của Σ 3. L((αβ)) = L(α)L(β)
đều là những BTCQ
là 4. L((α)*) = L(α)*
(1)
2. Nếu α và β là hai BTCQ ,
Từ (1) và (2) ta có tính chất sau :
và có
thì (α∪β), (αβ), (α)* cũng là những BTCQ
thì là
Một ngôn ngữ là chính qui nếu và chỉ nếu
chí và
ngôn ngữ đó được chỉ định bởi một biểu thức chính qui
ượ chí
Chú ý 1 : Khi viết một BTCQ, có thể bỏ các dấu ngoặc đơn
BTCQ có
Chú
Chú các
Nhận xét :
Nh xé
theo mức ưu tiên giảm dần : chẳng hạn viết a* thay vì (a)*
vì
Chú ý 2 : Có thể viết a+b thay vì viết a∪b
Chú thay vì
Có vì Các BTCQ cũng tạo thành một ngôn ngữ
thà
Ví dụ, biểu thức ((0 (1*)) + 0) có thể viết 01*+ 0
(1*)) + 0) có th
Ví có vì chúng là những xâu ký tự trên bảng chữ Σ
chú là
25/38
25/38 26/38
26/38
Bao đóng của bảng chữ Σ Một số ví dụ _ 1
Cho bảng chữ Σ = { a, b },
Cho
Cho bảng chữ Σ, khi đó, L = { a | ∀a ∈ Σ } là một NNCQ
khi là
Cho
có thể xây dựng được một số NNCQ trên Σ như sau :
ượ nh
Bao đóng của L là L* = Σ* là một NNCQ có vô hạn câu
là là có
Bao
L1 = {ε, a, aa, aab } L1 có 4 câu
Có thể liệt kê hết (đếm được) tất cả các câu của Σ*
ượ
L2 = { w ∈ Σ* | |w| ≤ 8 } L2 gồm các câu có độ dài ≤ 8
cá có
Ví dụ Σ* = (a+ b)* ε
1 L3 = { w ∈ Σ* | |w| là một số lẻ } L3 gồm các câu có độ dài lẻ
là cá có
L4 = { w ∈ Σ* | na(w) = nb(w) }
2 3 b
a
= {ε, ab, ba, aabb, abab, baab, ... }
ab,
L4 gồm các câu có số chữ a đúng bằng số chữ b
cá có
7
6
5
4 bb
ab ba
aa
L5 = { w ∈ Σ* | w = wR }
...
8
= {ε, aa, bb, aba, bab, abba, baab, ... }
aa,
aaa aab aba abb baa bab bba bbb
L5 gồm các câu đối xứng (palindrome)
cá
... ...
27/38
27/38 28/38
28/38
Một số ví dụ _ 2 Một số tính chất
Cho bảng chữ Σ, a ∈ Σ, w ∈ Σ* và L ⊆ Σ*
và
Cho Với quy ước L(α) là NNCQ đbdb BTCQ α
là
Khi đó :
Khi Khi đó :
Khi
ak = aa ... a k chữ a liên tiếp L(α) = L(β) khi và chỉ khi α = β
và
L(
wk = ww ... w ghép liên tiếp k câu w
ghé Nghĩa là :
là
Σk = ΣΣ ... Σ = { w ∈ Σ* | |w| = k }
ΣΣ Hai BTCQ bằng nhau cùng biểu diễn một NNCQ
cù
Lk = LL ... L ngôn ngữ gồm các câu là ghép k câu tuỳ ý của L
cá là ghé
Trường hợp đặc biệt k = 0 :
Trườ Để chứng minh rằng hai tập hợp A và B đã cho là bằng nhau
và là
a0 = w0 = ε A=B
Σ0 = L0 = { ε } cần chỉ ra A⊂B và B⊂A
và
Chú ý { ε } ≠ ∅ :
Chú
Nghĩa là cần CM hai chiều “⊂” và “⊃”
{ ε } có một câu là ε
có là
còn ∅ không có câu nào !
có nà
còn
29/38
29/38 30/38
30/38
5
- Chứng minh w ∈ (a*b)*∪(b*a)*
Một số ví dụ _ 3
Chứng minh rằng :
Ch Giiả sử w = w1w2...wn ∈ Σ*
G
L((a*b)* ∪ (b*a)*) = L((a ∪ b)*) = Σ* với Σ = { a, b }
L((a*b)* Xảy ra bốn trường hợp như sau :
ườ
Nghĩa là các BTCQ :
Ngh là 1. w = an, do đó w ∈ ( εa )* ⊂ ( b*a )* ⊂ (a*b)*∪(b*a)*
do
(a*b)* ∪ (b*a)* và Σ*
và
2. w = bn, do đó w ∈ ( εb )* ⊂ ( a*b )* ⊂ (a*b)*∪(b*a)*
do
cùng chỉ định một ngôn ngữ chính qui
chí
3. w chứa a và b, kết thúc bởi b. Ta có :
và thú có
w = a . . . ab b . . . b a . . . ab b . . . b
ab
Từ nay về sau để đơn giản, ta viết w ∈ α thay vì w ∈ L(α)
vì
a*b (a*b)* a*b (a*b)*
Lời giải là CM hai chiều “⊂” và “⊃” :
là (a*b)*∪(b*a)*
Do đó, w ∈
“⊂” : Rõ ràng (a*b)*∪(b*a)* ⊂ Σ* vì Σ* là bao đóng
rà vì là bao 4. w chứa a và b và kết thúc bởi a.
và và thú
“⊃” : Để chứng minh điều ngược lại, ta xét một câu :
ượ xé Tương tự trường hợp 3, ta cũng có :
ườ có
w = w1w2...wn ∈ Σ*
w ∈ L((a*b)*∪(b*a)*)
Cần chứng minh w ∈ (a*b)*∪(b*a)*
31/38
31/38 32/38
32/38
Các ngôn ngữ phi chính qui
chí Có vô hạn không đếm được ngôn ngữ
ượ
Nhận xét :
Nh xé Σ = { a, b }
Các BTCQ là vô hạn đếm được
là ượ
Các ngôn ngữ phi CQ
Các BTCQ chỉ biểu diễn tập vô hạn đếm được NNCQ,
ượ
nhưng không biểu diễn hết mọi ngôn ngữ
Tồn tại những ngôn ngữ phi chính qui
chí
Tập các NNCQ ℜ
cá
và không có đủ các BTCQ để biểu diển mọi ngôn ngữ
có
Mọi ngôn ngữ không thể là chinh qui :
Tập hợp các ngôn ngữ và tập hợp các tập hợp con của một
cá cá
Σ* = { a, b }*
tập hợp đếm được (tập hợp các câu) là không đếm được
ượ cá là không ượ
Tập hợp các NNCQ là đếm được vì mỗi NNCQ được biểu diển
cá là ượ vì ượ
bởi một BTCQ và tập hợp các BTCQ là đếm được
và cá là ượ Có 2n tập hợp con của một tập hợp A có n phần tử
Có 2n tập hợp con của một tập hợp A có n phần tử
có
Sẽ có nhiều ngôn ngữ khác với NNCQ
khá Nếu A có vô hạn đếm được phần tử thì 2A có vô hạn không đếm được phần tử
Nếu A có vô hạn đếm đượ c phần tử thì 2A có vô hạn không đếm đượ c phần tử
có ượ thì ượ
33/38
33/38 34/38
34/38
Vấn đề biểu diễn ngôn ngữ Ví dụ biểu diễn ngôn ngữ
Một ngôn ngữ trên bảng chữ Σ là tập hợp con của Σ+ Ngôn ngữ có vô hạn câu :
Ngôn
Cho L⊆Σ+, làm sao để biểu diễn hết mọi câu w∈L ?
là
Cho L1 = { ai ⏐ i là một số nguyên tố }, hay
là
Khi L có hữu hạn câu, chỉ việc liệt kê các câu
Khi có cá = { a2, a3, a5, a7, …, a11, a13, … }
Khi L có vô hạn câu, không thể liệt kê hết các câu của L,
Khi có cá
L2 = { aibj ⏐ i ≥ j ≥ 0 }, hay
mà phải tìm cách biểu diễn hữu hạn :
tì cá
= { ε, a, ab, aab, aabb, … }
Nếu L gồm các câu có một số tính chất nhất quán P nào đó,
cá có quá nà
là ngôn ngữ gồm các câu có một dãy con a rồi đến một dãy con b,
cá có
dùng tân từ để biểu diễn tính chất P đó
trong đó số con a bên trái nhiều hơn hoặc bằng số con b bên phải
trá
L = { w∈Σ* | P(w) }
Nếu L là NNCQ, sử dụng BTCQ α chỉ định L :
là L3 = (ab)*
L = L(α) = { ε, ab, abab, ababab, … }
L tuỳ ý, không phải là NNCQ : sử dụng ôtômat và văn phạm
là và
tu là ngôn ngữ gồm các câu có các cặp ab tuỳ ý (0..n cặp)
cá có
- Ôtômat đoán nhận câu của một ngôn ngữ
oá
- văn phạm sản sinh ra câu cho một ngôn ngữ
35/38
35/38 36/38
36/38
6
- Ví dụ sản sinh ra câu của ngôn ngữ Ví dụ đoán nhận một câu của ngôn ngữ
oá
Giiả sử định nghĩa ngôn ngữ L gồm các câu w∈Σ∗ :
cá
Cho L là ngôn ngữ trên { a, b } được định nghĩa như sau :
Cho là trên a, đượ G
1. ε ∈ L Có thể thu gọn w về câu rỗng ε : w ⇒ ε
2. Nếu w ∈ L thì awb ∈ L Thu gọn bằng cách thay thế dần các xâu con ab của w bởi ε
thì cá cá
Thu
3. L không còn câu nào khác nữa (ngoài 1 và 2)
nà khá (ngoà và Ví dụ :
Qui luật sản sinh các câu của L như sau :
cá
Qui w = ab ∈ L vì : ab ⇒ ε
vì
ab
Từ (1), L = { ε } w = aabbab ∈ L vì : aabbab ⇒ abab ⇒ ab ⇒ ε
vì
aabbab
Coi ε là w, từ (2), ta có câu awb = aεb = ab, L = { ε, ab }
có Coi a, b lần lượt là cặp dấu ngoặc đơn ( và ) :
ượ là và
Coi
Lại do (2), ta có L = { ε, ab, aabb, aaabbb, ... }
có L gồm các cặp dấu ngoặc đơn cân bằng nhau không cài nhau
cá cà
Cứ thế, ta có mọi câu của L có dạng aibi ⏐ ∀i ≥ 0
có có thu được từ một biểu thức toán học nào đó
ượ toá nà
Có thể biểu diễn L dưới dạng :
ướ Ví dụ, từ biểu thức (3*(x − y)) / (x + 1), thực hiện bỏ hết các
1), cá
ký hiệu toán tử và toán hạng, ta nhận được câu ngoặc đơn
toá toá ượ
L = { aibi ⏐ ∀i ≥ 0 }
cân bằng (())(), là câu aabbab
(())(), là
37/38
37/38 38/38
38/38
7
nguon tai.lieu . vn