Ch¬ng 1
Bµi tËp
1.Cho OH M = (, Q, q0, , F) với = {0,1} , Q = {q0, q1, q2, q3} , F = {q0}
Hµm chuyÓn cho bëi :
0
1
- H·y biÓu diÔn hµm chuyÓn bëi
q0
q1
q2
®å thÞ .
q1
q3
q0
- X¸c ®Þnh ng«n ng÷ ®o¸n nhËn
q2
q0
q3
bëi M
q3
q3
q3
2. Dùng c¸c ¤H§ ®o¸n nhËn c¸c ng«n ng÷ trªn tõ ®iÓn {0, 1} sau :
- TËp c¸c x©u kÕt thóc bëi 00
- TËp c¸c x©u chøa 3 ký hiÖu 1 liªn tiÕp
- TËp c¸c x©u b¾t ®Çu lµ 101
3.
Dùng c¸c ®å thÞ chuyÓn t¬ng ®¬ng víi c¸c ¤HK trªn ={0, 1} vµ Q={p, q, r, s}
sau:
a) (, Q, 1,p,{s})
b) (, Q, 2,p,{q, s})
víi 1, 2 cho bëi c¸c b¶ng sau
0
1
0
1
p
{p, q}
p
p
{q, s}
q
q
r
r
q
r
{q, r}
r
s
r
s
p
s
p
s
s
s
XÐt xem c¸c tõ x = 101010; y = 011100 cã thuéc c¸c ng«n ng÷ trªn kh«ng?
4.
ViÕt l¹i theo ®Þnh nghÜa ¤HK cho bëi
c,b
c
p
a
a
b
q
c
a
r
b
t
a,b,c
s
0
b
5. T×m c¸c BTCQ t¬ng øng víi biÓu ®å chuyÓn :
0
A
1
1
0
1 bµi 4 vµ 5.
C
6. Cho vÝ dô vÒ c¸ch ®o¸n nhËn x©u víi c¸c «tmat B
nh trong c¸c
7. Dùng c¸c v¨n ph¹m chÝnh quy t¬ng ®¬ng (sai kh¸c x©u rçng) víi c¸c «tmat cho
bëi c¸c bµi 4 vµ 5.
8. Cho VPCQ G bëi tËp quy t¾c P = {S aA | bB ; A bA | a; B aB | b}
a) C¸c tõ sau cã thuéc L(G) kh«ng: ababab ; ab5a ; baaaab ; babba
b) Dùng c¸c OHK vµ OH§ t¬ng ®¬ng víi G.
c) ViÕt biÓu thøc chÝnh quy cña L(G)
9. Dùng c¸c VPCQ (vµ c¸c «tmat h÷u h¹n t¬ng øng) sinh ra c¸c ng«n ng÷ sau:
L1 = { (01)n | n>=0 } ; L2 = { (01)n | n>0 } ; L3 = {0n1m | n,m > 0}
Ch¬ng 2
1. Cho VPPNC G = <, , P, S> trong ®ã = {a, b}, = {S, A, B}
P = {S aB | bA ;
A aS | bAA | a ;
B bS | aBB | b}
a) C¸c tõ sau cã thuéc L(G) kh«ng? NÕu cã h·y dùng c©y dÉn xuÊt cña chóng : x =
aabbbababa ; y = babaaabbabab ; z = aabbbabba
b) Dùng VPPNC G’ t¬ng ®¬ng víi G vµ ë d¹ng chuÈn Chomsky.
c) L(G) lµ ng«n ng÷ v« h¹n hay h÷u h¹n?
2. Cho VPPNC G = <, , P, S> trong ®ã = {0, 1}, = {S, A, B, C, D}
P = {S 1A | 0SA ; A 0BA | 1A0 | 10 ;
B 0B1 | 01A}
a) Dùng c©y ph©n tÝch cho c¸c tõ sau (nÕu ®îc)
x = 1100110100
;
y = 0110000110110
b) Dùng VPPNC t¬ng ®¬ng ë d¹ng chuÈn Ch«msky vµ xÐt xem NNPNC t¬ng øng lµ
v« h¹n hay h÷u h¹n.
3. Cho VPPNC G = <, , P, S> trong ®ã = {0, 1}, = {S, A, B, C, D}
P = {S 0B | 1A | 0SA | 1SB ;
A 0CA | 1A0 | 10 ;
B BS1 | 0BD | 1B0 | 0B1 ; C 0C1 | 01A | 0BD ; D 1DB | 0D | 1}
a) Dùng c¸c VPPNC b»ng c¸ch lo¹i c¸c ký hiÖu kh«ng ®Õn ®îc sau ®ã lo¹i c¸c ký hiÖu
v« sinh.
b) Dùng c¸c VPPNC b»ng c¸ch lo¹i c¸c ký hiÖu v« sinh sau ®ã lo¹i c¸c ký hiÖu kh«ng
®Õn ®îc.
c) Víi v¨n ph¹m G’ thu ®îc tõ b) h·y ®a nã vÒ d¹ng chuÈn Ch«msky.
4. Dùng VPPNC G’ kh«ng chøa c¸c ký hiÖu v« Ých, kh«ng chøa c¸c -quy t¾c vµ c¸c quy
t¾c ®¬n t¬ng ®¬ng víi v¨n ph¹m G sau
G = <, , P, S> trong ®ã = {a, b, c}, = {S, A, B, C, D, E}
P = {S A | B | CD ; A C | D ; B D | E ; C aS | a | ;
D bS | b ; E cS | c | }
Víi v¨n ph¹m t×m ®îc, h·y dùng «t«mat ®Èy xuèng t¬ng ®¬ng.
Ch¬ng 3
1. Cho hệ mã Vigine với khoá là ‘tunhien’
a) Giải mã bản mã: eicjisohwxoweit
b) Tự cho một bản rõ không ít hơn 15 ký tự rồi mã hoá theo khoá trên.
2. Cho hệ mã Affine với khoá là (11, 14)
a) Giải mã bản mã: ‘gvakopymb’
b) Tự cho một bản rõ không ít hơn 15 ký tự rồi mã hoá theo khoá trên.
3. Cho hệ mã Hoán vị với khoá là
1
2
3
4
5
4
1
5
3
2
a) Giải mã bản mã: inehguntuckoinaenzth
b) Tự cho một bản rõ không ít hơn 15 ký tự rồi mã hoá theo khoá trên.
4. Hỏi tương tự với các hệ mã khác
5. Cơ sở toán học của mã Balô? mô tả hệ mã và cho ví dụ.
6. Xét hệ mã Ba lô (Knapsac) với dãy siêu tăng cho trước là 2, 5, 11, 23, 47, 95; cho
các số M = 211 và
u = 83; hãy chỉ rõ phần khoá công khai, khoá bí mật, mô tả
cụ thể cách mã hoá và giải mã xâu nhị phân ‘101101’.
7. Xét bảng chữ cái gồm 26 chữ cái tiếng Anh (chữ in hoa) A .. Z
a) Cho hệ mã Affine với khóa (7, 18), hãy giải mã bản mã ‘GNUXIODAM’
b) Với hệ mã Hoán vị, tự cho một khóa với độ dài 5 rồi mã hóa bản rõ
‘NUOCCONGHOAXAHOICHUNGHIAVIETNAM’ với khóa đó.
c) Cho hệ mã tự sinh với khóa là 15, hãy mã hóa bản rõ ‘TRUNGDIEM’.
8. Cơ sở toán học của mã RSA? mô tả hệ mã RSA và chữ ký RSA?
9. Phân biệt mã đối xứng và mã công khai. Khái quát về chữ ký số.
- Xem thêm -
.DOC 
3 
274 
102 
