Bài giảng Lý thuyết tính toán - Chương 1: Mở đầu - Cơ sở của môn học

 , {  } và { a } bởi các phép hội, ghép và bao đóng
35/56
Ví dụ xây dựng tập NNCQ 
 Cho ={}, những phần tử-ngôn ngữ có ngay (tự có) :
   , {}, {} 
 Những ngôn ngữ L được xây dựng kiểu quy nạp (đệ quy) :
 Luật : Nếu A, B  , thì AB, A.B và A*  
 A={},
B= {},
AB={, },
A.B={}={}, 
B* = {, , , , ... n, ... }, n bất kỳ n>0
 Vậy sau bước này ta có :
, {}, {}, {}, ..., {, , , , ... n, ... }
 Và cứ thế tiếp tục xây dựng 
36/56
(1)
Biểu thức chính quy (BTCQ)
 Người ta sử dụng các biểu thức chính quy (Regular 
Expressions) để biểu diễn các ngôn ngữ chính qui trên 
 Qui tắc xây dựng BTCQ trên  là các biểu thức được tạo 
thành theo các bước quy nạp như sau :
1. ,  và a, với mọi phần tử a của 
đều là những BTCQ 
2. Nếu  và  là hai BTCQ ,
thì (), (), ()* cũng là những BTCQ 
Chú ý 1 : Khi viết một BTCQ, có thể bỏ các dấu ngoặc đơn
theo mức ưu tiên giảm dần : chẳng hạn viết a* thay vì (a)*
Chú ý 2 : Có thể viết a+b thay vì viết ab
Ví dụ, biểu thức ((0 (1*)) + 0) có thể viết 01*+ 0
 i i , 
 i i i ì
 i ì i 
í , i i 
737/56
(2)
Biểu diễn ngôn ngữ bởi biểu thức chính qui
 Ngôn ngữ L() được biểu diễn (hay được chỉ định)
bởi BTCQ  theo các bước quy nạp như sau :
1. L() = , L() = {  }, L(a) = { a } cho a 
2. L((  )) = L()  L()
3. L(()) = L()L()
4. L(()*) = L()*
 Từ (1) và (2) ta có tính chất sau :
Một ngôn ngữ là chính qui nếu và chỉ nếu (nễu, khĩ )
ngôn ngữ đó được chỉ định bởi một biểu thức chính qui 
 Nhận xét :
 Các BTCQ cũng tạo thành một ngôn ngữ
vì chúng là những xâu ký tự trên bảng chữ 
Đọc pxi
38/56
Bao đóng của bảng chữ 
 Cho bảng chữ , khi đó, L = { a | a   } là một NNCQ
 Bao đóng của L là L* = * là một NNCQ có vô hạn câu
 Có thể liệt kê hết (đếm được) tất cả các câu của *
 Ví dụ * = (a + b)*

a b
aa ab ba bb
aaa aab aba abb baa bab bba bbb
...... ......
1
2 3
4 5 6 7
8 ......
 Cho  = {a, b} thì ta 
đã có một thứ tự tiền 
định a đứng trước b
 Cho hai câu w1, w2
khi đó w1 đứng trước 
w2 khĩ |w1|| w2|
 , ì 
 i 
ị 
 i , 
i 
 ĩ 
39/56
Nghịch đảo câu xong thì
cũng chính nó !
Đọc xuôi, đọc ngược như 
nhau
Đứng bên tê, ngó bên ni, 
cũng rứa
Đứng bên ni, ngó bên tê, 
cũng rứa
Đi qua, đi lai, y chang !
Hai ký tự cách đều đầu và
cuối câu y chang !
ị t ì
 í !
 i, 
 t , i, 
 r
 i, t , 
 r
i , i l i, !
i t 
i !
Một số ví dụ _ 1
 Cho bảng chữ  = { a, b },
có thể xây dựng được một số NNCQ trên  như sau :
L1 = {, a, aa, aab } L1 có 4 câu
L2 = { w  * | |w|  8 } L2 gồm các câu có độ dài  8
L3 = { w  * | |w| là một số lẻ } L3 gồm các câu có độ dài lẻ
L4 = { w  * | na(w) = nb(w) }
= {, ab, ba, aabb, abab, baab, ... }
L4 gồm các câu có số chữ a
đúng bằng số chữ b
L5 = { w  * | w = wR }
= {, aa, bb, aba, bab, abba, baab, ... }
L5 gồm các câu đối xứng (palindrome)
Có thể có thêm các nhận xét gì về
các câu đối xúng ?
t t t ì
 i 40/56
Ví dụ về một thuật toán kiểm tra câu đối xứng
Func PalinCheck(w: string): bool
OK = true; i=1, l=len(w)
if l>0 then
while OK and i<=l and w(i)=w(l) do i++; l--
Return OK
w1 w2 wl-1 wl...
i++ l--
41/56
Một số ví dụ _ 2
 Cho bảng chữ , a  , w  * và L  * 
 Khi đó :
 ak = aa ... a k chữ a liên tiếp
 wk = ww ... w ghép liên tiếp k câu w
 k =  ...  = { w  * | |w| = k }
 Lk = LL ... L ngôn ngữ gồm các câu là ghép k câu tuỳ ý của L
 Trường hợp đặc biệt k = 0 :
 a0 = w0 = 
 0 = L0 = {  }
 Chú ý {  }   :
 {  } có một câu là 
 còn  không có câu nào !
42/56
Một số tính chất
 Với quy ước L() là NNCQ đbdb BTCQ 
 Khi đó :
 L() = L() khi và chỉ khi  = 
Nghĩa là :
Hai BTCQ bằng nhau cùng biểu diễn một NNCQ
 Để chứng minh rằng hai tập hợp A và B đã cho là bằng nhau
A = B
cần chỉ ra AB và BA
Nghĩa là cần CM hai chiều “” và “”
843/56
Một số ví dụ _ 3
 Chứng minh rằng :
 Các BTCQ : (a*b)*  (b*a)* và *
cùng chỉ định một ngôn ngữ chính qui ?
 Bằng cách “cùng L hai BTCQ” :
L1 = L((a*b)*  (b*a)*) và L2 = L((a  b)*) = L(*) với  = { a, b }
Cần CM rằng L1 = L2?
 Từ nay về sau để đơn giản, ta viết w thay vì wL()
 Lời giải là CM hai chiều “” và “” :
“” : Rõ ràng L1 = (a*b)*(b*a)*  L2 = *, vì * là bao đóng
“” : Để chứng minh điều ngược lại, ta xét một câu :
w = w1w2...wn  *
Cần chứng minh w  (a*b)*(b*a)* 
44/56
a*b (a*b)* a*b (a*b)*
Chứng minh w  (a*b)*(b*a)*
 Giả sử w = w1w2...wn  *
Xảy ra bốn trường hợp như sau :
1. w = an, do đó w  ( a )*  ( b*a )*  (a*b)*(b*a)*
2. w = bn, do đó w  ( b )*  ( a*b )*  (a*b)*(b*a)*
3. w chứa a và b, kết thúc bởi b. Ta có :
 w = a . . . ab b . . . b a . . . ab b . . . b
Do đó, w  (a*b)*(b*a)*
4. w chứa a và b và kết thúc bởi a.
Tương tự trường hợp 3, ta cũng có :
w  L((a*b)*(b*a)*)
45/56
Các ngôn ngữ phi chính qui
 Nhận xét :
 Các BTCQ là vô hạn đếm được
 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
và không có đủ các BTCQ để biểu diển mọi ngôn ngữ
 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 
tập hợp đếm được (tập hợp các câu) là không đếm được
 Tập hợp các NNCQ là đếm được vì mỗi NNCQ được biểu diển 
bởi một BTCQ và tập hợp các BTCQ là đếm được
 Sẽ có nhiều ngôn ngữ khác với NNCQ
46/56
Có vô hạn không đếm được ngôn ngữ
 = { a, b }
* = { a, b }*
Tập các NNCQ 
Các ngôn ngữ phi CQ
 Có 2n tập hợp con của một tập hợp A có n 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ử
t t t t
 t t ì t
47/56
Ví dụ tập con
 Cho A = { cục, cọ, cẫng)
Hỏi có bao nhiêu tập hợp con của A ?
 Trả lời : có 2|A|=23 = 8 tập hợp con của A
 Đó là các tập hợp con :
{ rỗng, {cục} , {cọ} , {cẫng}, 
{cục , cọ}, {cục , cẫng } , {cọ,cẫng}, {cục, cọ, cẫng} }
 Lý thuyết số
 , ,  vô hạn đếm được
 vô hạn không đếm được (lấp đầy trục số)
 Dựng bằng compa-êke số
- 0 1 2 ... +
2
2
48/56
Vấn đề 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 +
 Cho L+, làm sao để biểu diễn hết mọi câu wL ?
Khi L có hữu hạn câu, chỉ việc liệt kê các câu 
Khi L có vô hạn câu, không thể liệt kê hết các câu của L,
mà phải tìm cách biểu diễn hữu hạn :
 Nếu L gồm các câu có một số tính chất nhất quán P nào đó,
dùng tân từ để biểu diễn tính chất P đó
L = { w* | P(w) }
 Nếu L là NNCQ, sử dụng BTCQ  chỉ định L :
L = L()
 L tuỳ ý, không phải là NNCQ : sử dụng ôtômat và văn phạm
- Ôtômat đoán nhận câu của một ngôn ngữ
- Văn phạm sản sinh ra câu cho một ngôn ngữ
Chi rứa ?
949/56
Ví dụ biểu diễn ngôn ngữ
 Ngôn ngữ có vô hạn câu :
 L1 = { ai  i là một số nguyên tố }, hay
= { a2, a3, a5, a7, …, a11, a13, … }
 L2 = { aibj  i  j  0 }, hay
= { , a, ab, aab, aabb, … }
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,
trong đó số con a bên trái nhiều hơn hoặc bằng số con b bên phải 
 L3 = (ab)*
= { , ab, abab, ababab, … }
là ngôn ngữ gồm các câu có các cặp ab tuỳ ý (0..n cặp)
50/56
Ví dụ sản sinh ra câu của ngôn ngữ
 Cho L là ngôn ngữ trên { a, b } được định nghĩa như sau :
1.   L
2. Nếu w  L thì awb  L
3. L không còn câu nào khác nữa (ngoài 1 và 2)
 Qui luật sản sinh các câu của L như sau :
 Từ (1), L = {  }
Coi  là w, từ (2), ta có câu awb = ab = ab, L = { , ab }
 Lại do (2), ta có L = { , ab, aabb, aaabbb, ... }
 Cứ thế, ta có mọi câu của L có dạng aibi  i  0
 Có thể biểu diễn L dưới dạng :
 L = { aibi  i  0 }
51/56
Ví dụ đoán nhận một câu của ngôn ngữ
 Giả sử định nghĩa ngôn ngữ L gồm các câu w :
 Có thể thu gọn w về câu rỗng  : w  
 Thu gọn bằng cách thay thế dần các xâu con ab của w bởi 
 Ví dụ :
 w = ab  L vì : ab  
 w = aabbab  L vì : aabbab  abab  ab  
 Coi a, b lần lượt là cặp dấu ngoặc đơn ( và ) :
 L gồm các cặp dấu ngoặc đơn cân bằng nhau không cài nhau 
thu được từ một biểu thức toán học nào đó
 Ví dụ, từ biểu thức (3*(x  y))  (x + 1), thực hiện bỏ hết các 
ký hiệu toán tử và toán hạng, ta nhận được câu ngoặc đơn 
cân bằng (())(), là câu aabbab
52/56
Bài tập 1
1. r + s = s + r
2. r + (s + t) = (r + s) + t
3. r (s + t) = rs + rt
4. r = r = r 
5. r +  = r
6. ( + r)* = r*
7. r = r = 
8. (r*)* = r*
9. r + r = r
10. r(st ) = (rs)t
11. * = 
12. (r*s*)* = (r + s)*
13. r + r* = r*
14. (r + s)t = rt + st
Cho các biểu thức chính qui r, s, t,
trong đó nếu r = s thì có nghĩa L(r) = L(s)
Chứng minh các tinh chất sau (dấu + ~ dấu ):
53/56
Bài tập_2
2. Tìm các BTCQ chỉ định phần bù của các ngôn ngữ sau :
 (ab)*b
 ((ab)(ab))*
3. Cho ngôn ngữ L trên bảng chữ { a, b }
được định nghĩa như sau :
   L
 Nếu w  L thì awb  L
 Nếu w  L thì bwa  L
 Nếu w1, w2  L thì w1w2  L
Chứng minh bằng quy nạp rằng :
ngôn ngữ L theo cách định nghĩa trên khĩ L gồm mọi câu có
số chữ a đúng bằng số chữ b (viết gọn na(w) = nb(w) ?
Phép CM quy nạp (induction) :
•Cần CM P(n), n  ?
•Thử trường hợp P(0), P(1)
•Giả sử P(n) đúng
Cần CM rằng P(n+1) đúng
i i
i
54/56
Phép chứng minh
Mệnh đề
Pitagore: a2+b2=c2i
Tiên đề/Định đề
(công nhận)
i ị
Bổ đềĐịnh lýị lHệ quả
Trời sinh ra thế !i i
10
55/56
CM r + s = s + r
 “L” hai vế, cần CM rằng L(r + s) = L(s + r) :
 Thật vậy, biến đổi vế trái :
 L(r + s) = (theo đn) = L(r)  L(s)
= {w  * | w  L(r)  w  L(s) }
= {w  * | w  L(s)  w  L(r) } (không tin, lập bảng chân lý)
= L(s + r) (đpcm)
(Qed-Quote Erat Demonstandum)

56/56
CM (r*s*)* = (r + s)*
 Sử dụng định nghĩa ngôn ngữ L* để CM :
 Đặt L1= (r*s*)*, L2 = (r + s)*,
CM L1= L2 bằng cách CM L1 L2 và L2  L1
 L1 L2 là hiển nhiên vì L2 là một bao đóng chưá mọi 
câu từ các BTCQ r và s
 L2  L1 ?
Theo đn L1={w|k: wkr*s*, w= w0w1 ... wk} 
Cho w L, CM wL1
w = r* = r* ()  r* s*
w = s* = () s*  r* s*
w = r*s*  r* s** = L1
r, s