Xử lý ảnh số - Nhận dạng và nội suy part 6

Chia sẻ: Adfgajdshd Asjdaksdak | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

84
lượt xem 19
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Khi bạn không chắc chắn về Cân bằng trắng Bạn có thể gặp rất nhiều kiểu thời tiết và điều kiện ánh sáng phức tạp khi chụp ảnh. Những lúc này bạn rất nên chụp với tùy chỉnh ảnh raw. Ví dụ, bạn có thể chụp trong bóng râm, khi mây tạm thời che mặt trời, hay thậm chí là các điều kiện ánh sáng hỗn hợp (ví dụ như ánh sáng mặt trời chiếu vào một phòng đang mở đèn dây tóc).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Xử lý ảnh số - Nhận dạng và nội suy part 6

u.ng cua tˆng ra s˜ d at m´.c cao; v` mˆu d .o.c xu. l´ thuˆc l´.p tu.o.ng u.ng n´t n`y. ˜ ˙` ’a ˙y ’ ´ e ¯. u a a ¯u . oo ´ ua . H` 9.13 tˆ’ng kˆt c´c thao luˆn d a d .o.c tr` b`y. Ch´ y trong h`ng th´. ba, ˙ ´ ˙ ’ ınh o ea a ¯˜ ¯u . ınh a u´ a u . .c tap vˆ ranh gi´.i gi˜.a c´c v`ng l` tu` y. Dˇc biˆt, kh´ khˇn ch´ thu.`.ng xay a y´ -a d ˆ ph´ . ` ˙ ’ ¯o u e ouau e oa ınh o . . . . hai khi cho d ap u.ng ch´ x´c d ˆi v´.i c´c tˆ’ ho.p kh´c ˙ ´ u˙` ´ ’a ra trong cˆ u tr´c cua tˆng th´ a u ¯´ ´ ınh a ¯o o a o . a .p cho tru.´.c. L´ do l` c´c d u.`.ng thˇng khˆng kˆt th´c tai c´c giao ˙ ’ ´ ˙ao ’ nhau cua c´c l´ o y a a ¯o a o e u.a .i c´c d u.`.ng thˇng kh´c; v` bo.i vˆy c´c mˆu cua c`ng mˆt l´.p c´ thˆ’ ˙ ˙ ’ ˜ ˙ ’ a˙aa ’. ˙u ’ cua ch´ng v´ a ¯ o u o a a a oo oe . xuˆ t hiˆn trˆn hai ph´ cua d .`.ng thˇng trong khˆng gian mˆu. Diˆu n`y dˆn d e n a -` ˙ ’ ˜ ˜ ´ ´ ıa ˙ ¯u o ’ a e e a o e a a ¯ˆ . .`.ng thˇng d u.o.c tao ra trong thao t´c AND d ˆi kh´ c´ thˆ’ (hoˇc khˆng thˆ’) v˜ c´c d o ˙ ˙ ˙ ’ ´ oo e a o e e a ¯u a ¯. . a ¯o . v´.i mˆt mˆu d a cho. Ph´p to´n XOR trong cˆt th´. ba cua H`nh 9.13 d u.o.c su. dung ˜ ˙ ’ ¯. ˙ . ’ o o a ¯˜ e a o u ı . . dˆ’ nghiˆn c´.u tru.`.ng ho.p c´ hai l´.p mˆu v` mˆi l´.p c´ hai mˆu. Nˆu c´c mˆu d .o.c ˙ ˜ ˜ ˜ ˜ ´ ¯e eu o .o o a aoo o a ea a ¯u . sˇp xˆp sao cho ω1 = {(0, 1), (1, 0)} v` ω2 = {(0, 0), (1, 1)} th` c´ thˆ’ phˆn loai d`ng ˙ ´ ´ ae a ıo e a .u h`m XOR: mˆt mˆu thuˆc l´.p ω1 nˆu kˆt qua XOR bˇ ng 1 v` thuˆc l´.p ω2 nˆu XOR ˜ ` ´´ ´ ˙ ’ a o a oo ee a a oo e . . . c´ gi´ tri 0. oa. Kˆt qua trˆn c´ thˆ’ mo. rˆng cho tru.`.ng ho.p n chiˆu: thay cho c´c d .`.ng thˇng ˙ ’. ˙ ’ ´ ` ˙ e o e ˙o ’ e o e a ¯u o a . ta d`ng c´c siˆu phˇng. Ap dung mang neuron mˆt tˆng, hai tˆng v` ba tˆng tu.o.ng ´ ˙ ’ o` ` ` u ae a .a a a a . . u.ng cho c´c nu.a khˆng gian (x´c d inh bo.i mˆt siˆu phˇng), c´c tˆp lˆi d diˆn (giao ˙ ’ a a ` ¯a e a˙ ’ ˙ ’ ´ o a ¯. oe a .o . . .a khˆng gian), v` v´.i c´c v`ng c´ biˆn v´.i d o ph´.c tap tu` y. Trong hai ˙a˙ ’ ’ cua c´c nu o ao a u o e o ¯ˆ u . y´ . tru.`.ng ho.p sau, sˆ c´c n´t trong mˆi tˆng x´c d .nh d o ph´.c tap cua biˆn. Sˆ c´c l´.p ˜a ´ o` ´ ˙ ’ o oa u a ¯i ¯ˆ u . e oa o . . trong tru.`.ng ho.p d` u tiˆn gi´.i han l` hai. Trong hai tru.`.ng ho.p c`n lai, sˆ c´c l´.p ´ o . ¯ˆa e o.a o . o . oao l` tu` y do sˆ c´c n´t trong tˆng ra c´ thˆ’ chon d e’ ph` ho.p v´.i yˆu cˆu. ˙ ˙ ´ ` oe` a y´ oa u a o e . ¯ˆ u . a Mˆt cˆu hoi tu. nhiˆn l`: tai sao khˆng nghiˆn c´.u c´c mang neuron nhiˆu ho.n ` ˙. ’ oa ea. o eua e . . ba tˆng? X´t cho c`ng th` mˆt mang neuron ba tˆng c´ thˆ’ phˆn l´.p c´c v`ng v´.i ˙ ` ` a e u ıo a oeaoau o . . .`.ng biˆn c´ d o ph´.c tap tu` y. Cˆu tra l`.i l` o. chˆ phu.o.ng ph´p d .o.c su. dung dˆ’ ˙ ’˜ ˙ o a˙ o ’ a ¯u . ˙ . ’ du o ¯ e o ¯ˆ u . y´ a ¯e . huˆ n luyˆn mˆt mang neuron chı d ˆi v´.i ba tˆng. Nguyˆn tˇc huˆ n luyˆn mang trong ´ ´ ’´ ` ´ ˙ ¯o o a e o a ea a e . . . . . .c tiˆ’u lˆi m` khˆng d` cˆp d e n phai liˆn kˆt nh´m c´c siˆu phˇng v´.i ˙˜ ˙ ’ ´ ´ ˙. ’ ˙ee ’ H` 9.10 chı cu e o a o ¯ˆ a ¯ˆ ınh e. o ae a o nh˜.ng n´t d ˇc ta trong tˆng th´. hai cua mˆt mang ba tˆng c´ dang d u.o.c d` cˆp trˆn ` ` u ¯a ˙ .’ ˙ ’ u a u o a o. ¯ . ¯ˆ a e. e . . .a sˆ c´c tˆng v` sˆ c´c n´t trong mˆi tˆng ˆ’n vˆn l` ˙˜ ˜a d ˆy. Thˆt ra b`i to´n cˆn d ˆi gi˜ o a ` a a a ¯o u ´ ´ ´ o` a a a ¯a a a aoa u . mˆt b`i to´n mo.. Trong thu.c tˆ, ngu.`.i ta thu.`.ng chon du.a trˆn ph´p thu. dung-sai ´ ˙ ’ ˙ ¯´ ’ oa a .e o o e e . . . .a v`o tri th´.c biˆt tru.´.c vˆ b`i to´n cˆn giai quyˆt. ´ o`a a` ´ ˙ ’ hoˇc du a a. u e e a e . 320
......................................................................................................................................................................................................................................................................................................................................................... . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . ... . . . . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . .... . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C´c l´.p L`.i giai . . . . . . . . . . . . . ˙ ’ . . . . . C´c loai a ao H` dang biˆn ınh . e . o ´ . . . . . . Cˆ u tr´c a u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v´.i v`ng lu.´.i . su. dung XOR . . . . . . mang neuron . . . . . . tˆ’ng qu´t ˙ . . . . . . ˙. ’ v`ng u ou o . . . . . . . o a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . .. .. . . . .... . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . . .. . . . ......................................................................................................................................................................................................................................................................................................................................................... . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . .. . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . ... .... ... ... ... .... ... ... .... ... .... . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . ... . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... .... ... ... ... .... ... ... .... ..... .. . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . o` . . ... .... ... ... ... .... ... ... .... .... . . . .. . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . Mˆt tˆng .a . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . . . . . . . . ... .... ... ... ... .... ... ... ...... . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... .... ... ... ... .... ... ... .... . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... .... ... ... ... .... ... ... .... . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... .... ... ... ... .... ... ...... . . . .. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... .... ... ......... .... ... .... ...... . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . ... .... ...... . ........ ... ... .... ... . . . . .... ... . . . .. . . . . .. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . ω ω ω . . . . . . ..... . .. ... .... .. .... ... .... .. .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... ... .... ...... .1. . . .. .. 2.. . . . . . . . . .. . . . . . . . . . . ... . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . .. . . . .. . . . ........ . . . ... ... .... ... ................ .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . .. . .. . .. . . . .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .. . ... .... ... ... ... ..... .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mˆt o . . . . . . .. .. . ... .... ... ... ... .... . . . . . . . . . . . . . . ....... . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . ....... . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .. . ...... . . . . . . . . . . . . . . . . . . . . . ... .... ... ... ...... .. . .. ... . . . . . . ....... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. ...... . . . . . . . ... .... ... ... .... . . . . . . . . . . . .. . . . . . . . . . ...... . ... ... .... ... ... .... .. . . . . .... . . . . . . . . . . . . . .. ω . . . . . . . . .. . . . . . . . . . .. . .... . . . . . . . . . . . ... .... ... ... ... . . . . . ....... . . . . . . . . . . . ...... . . . . .. . . . . . . . . .. . . . 2 . . ... .... ... .. ... . . . . ..... . . . . . . . . . . . . . . . . . . . .. . . . . .. . . . . . . . . . . ...... . . . . . . . . . . . . . . . .... . . . . . . . . . ... .... ... ... . . . . . . . . . . .. . . . .. . .. . . . . . . . . . . . ....... . . . . . .. . . . . . . . . . . . . . .. ...... .. . . . ... .... ..... . . . . . . . . . . .. ...... . . . . . . . . . . . . . ˙ ’ . . . . . . . . . . . .. . ..... . .... siˆu phˇng e a . . . . . . . . . . . . . . . .. ... .... ... . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . ... .... ... ..... . . . . . . . .. . . . . . . . . .. .. . . . . . . . .. . . . . . . . . . . . . . . . . ... ...... .... ..... ..... . . . .. . .. . .. . ... .... .. . . . . . . . . .. . . . . .. . . . . . . . . . . . . . . . . .. . . ω ω . .. . . . . . . . . . . . . .. . . ... .... . . . . . . . . . .. . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . .. . 2. .. 1. .. ... .. . . . . . . . . . . . . . . .. . . . . . . . . .. . . . . .. .. . . . . . ... .. . .. . ... . . . ....... . . . . ..... ........ . . . . . . . . . .. . . .. . . . . . . . . .. . . . . . . . . . . . . .. . . . . . ... . . . .. . . . . . . . .. . ... . . . . . . . . . . . . .. . . . . . . .. • • . . . . . . .. . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . ... ... ... .... .... . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . .. . . . . . . .. . . . .. . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . .. . . . . . . . . . ........................................................................................................................................... .. ................................................................................................. ..................................................................................................... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . ... . . . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . .... . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . .... . . ... . . . . . . . . . . .. .. . ..... .. . . ...... . . . . . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . . .. . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . ... . . . . . . . ... .... .... .. . ... .. .... .. . .. . . . . ...... . . . . . . . ... .... ... ... .... .... . . . . . . . . . . ... .... ..... ... .. . ... .. .... .. . .. . . . . . . . . . .. . . ... .... ... ... .... .... . . . . . . . . . . ... .... ... ... .. .. .. . ... .. .... .. . . . . . . . . .. ` . . . . . ... .... ... ... .... .... .. Hai tˆng a . . . . . . . . . . ... .... ... .... .. . ... .. . ... .. .... .. . .. . . . . . . . .. . . .. . ... .... ... ... .... .... . . . . . . . . . ... .... ... ... ... ... . . ... .. . ... .. .... .. . .. . . . .. . . . . . . . . . . ... .... ... ... .... .... . . . . . . . . . . . ... .... ... ... .... .. . . ... .... ... ... .... .... ..... . . ... .. . ... .. .... .. . .. . . . . . . . . . . . . . . . . . . . ... .... ... ... ..... . . . . ... .... ... ... .... .... .. .... . . ... .. . ... .. .... .. . . . . . . . . .. . .. . . . . . . . ........ ... ... ... .... . ... . . ... .... ... ... .... .... . . . . . .... . . ... .. . ... .. .... .. . . . . .. . . . . . . . .... . . . . . . . . . . . . . . . . . . . . . ... .. .................. ... ... . .. . . ... .... ... ... .... .... . . .. . . . . ........ .. ... . . .. . . . . ....... ...... . . .. . . . .. .. . . . . ..... ....... .... ..... .... . . ... .... ... ... .... .... . . . . ω ω ω . .. . . . . . . .. . . .... . . ... .. . ... .. .... .. . ... .. . . . . . . . .. . . . . .... . . . ... .... .. .1..... ... . . ... . . ... .... ... ... .1 . .... . . . . .. . . . . . . . .. . . .. 2. ... . . . . .. . . .... . . ... .. . ... .. .... .. . . . . . .............. . . . .. ......... . . . . . . . ... . . ..... . . . .. ..... . . ... .... ... ... .... .... ....... .. . .... .. . . .. . . . . . . . . . . . . . . .. . . ....... ...... . . . . . . . . . . .. . . . .. . . . . . . . .. . . .... . . ... .... ... ... .... .... . . .. . ... .... . . . . . . . . . .... . . ... .. . ... .. .... .. . . . . . . ... .. . .. .. ...... ... .... ... ... . . .... . . . .. .... . . ... .... ... ... .... .... . .. . . . . . . . . . . . . . ... ` . . . . . . . ....... ...... . C´c miˆn a e . . . . .... .. .. .. . . . .... . . . . . ... . ... .... ... ....... .. .... . . . . . . . . ... . .. ... . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . ....... ...... . . .. . . . . . . .. .. . . . . . . . ... . . ... . . . . . . . .. . . . . ... .... . . . . . . . . . . . . . . . .. .. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . ....... ...... . . .. . . . . . . . . . . . . .. .. .... ... ... .... . . . . . .. .. .. . . . . . . .. . . . . . . . . . . . . ω .. .... . . ... .... ... ... .... .... . . .... . . ... .. . ... .. .... .. . . ... ... .. . . . . . . .. . . . . . . . . . . . . . . .. . . .... .... ... ... ......... . . . .... . ... .. . . . . . . . . . . . . . . . ... 2 . . . . . . . . . . . . . . .. . ... . .. . . . . . . . . . . . . . ....... ...... . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . ..... ... . . .... . . ... .. . ... .. .... .. . . .. . . . . . . . .. . . . .... . .. .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . . . . . . . . . . . ...... ... . . . . ....... ...... . .. . . . .... ... ... .... ...... . . . . .. . . . . . . . . . . . . . . .. . . ... . . . . . . . . . ... ... . . . . . . . . . . . . . . . .. .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . ... ` .... ... ... .... ... .... ....... ....... . . . . . . lˆi o ... . ... . . . ... . . . . ... . . . . . . ... . . . ... . . . . . . . . . . . .. . . . . . . . . .. .... . . ... .... ... ... .... .... .... . . . . . . . . . . . . . . . . . .... . .... .... . . . . ... . .... ... ................ . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .. . ... . . .. . .. . . . . . . . . . . . . . ...... ...... . . . . . . . .. .. .. ....... .. . . . . . . .. . .... . .. . . . ......... . . . .. . . . .. . . . . . . . . ... . . .. . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . . . . . . . . . . . . . . . . . . . . .. . . ...... .... ... .. . ... . ω ω . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . .. . . . . ... ... . ... . 2.. .. . . . . . . .. . . . . . . . . . . . . .. . . . . .. . .. . 1. . . . . ... . . . .. . . . . . . . . . . . . . . . . ... . . . . . .. .. . . . .. . .. ........... .. ...... . ... . . .. . . . . ...... .. . . . . . . . . . . . . . . . . .. ... . .. . . . . . . . . .. . . .. . . . . . . . . . . . . . . . . . . . . . ... . . . . . . .... .. ...... ... . . . . . . .. . ...... ... . .. . . ...... . . . . . . . . . . . . . . . . . . . . . .. . . . . . . ... . .. . . . . . . . . . . . . . . . . .... .. .. ... ... ... ... ... . . ... . . . . .. . .... .... . . . . . . . . . . . . . .. . . . . • • .... . . .. . . . . . . . .. . . .. ... .. ........................ . .. .... . . ... .... ... ... .... .... . . . ... . . . . . .. .. . . . . . . . . . . . . . ... . .... . . . . . . . . . . . .. . . . . . . . . . . . .. ... ... ... ... . . .... . . . . . . . . . . . . . . . . .... . . . . . . . . . .... . . . . . . . . . . . .... . . . . . . . . . .. . .. .. ... ... ... . . . . . .. . . . . .... . . . . . . . . .. . . .... . . . .. . . . . . . ... . . . . . . . . . . . ..... . . . . . . . . ..... . . . . . .. . . . . .. . . . . . . . . . .. . . . . . . . .... . . . . . . . . . . .... . . . . .. . . . . . . ... .. . . . . . . . .. . . . . . . . . .... . . . . . . .... . .. . . . .. . . . . . .... . . . . . . .. . . . . .... . . . . . . .. . ...................................................................................................................................................................................................................................................................................................................................................... . . . . . . . . . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . .... .... .. .. . . .... . . ... . . . . . . . . . . ... . .. ... ... . . ... . . . . . . . . . . ... . . . . . . . . . ... . . ......... . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . . . . .. . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . .. . . .. . . ...... . . . . . ... . . . . .. . ... .... ... ... ... .... ... . . . . .. . .. . . . . . . . .. . ...... .... . . . . . . ... .... ... ... ... .... ... . . . . .. . .. . . . . . . .... . ... .... . .... . . . . . . . ... .... ... ... ... .... ... . . . . . ` .. . . . .... . . . . . ...... ... ... .... Ba tˆng a . . . . . . . ... .... ... ... ... .... ... . . . . . . .. .. .. . . . . . . . . ........ ... ... ... .... . . . . . . . ... .... ... ... ... .... ... . . . . .. .. . . . . . .... ... .... ... ... ... .... . . . .... . . . . . . ... .... ... ... ... .... ... . . . . .. . . .. . . . . . . .. . . ...... . . ... .... ... ... ... .... . . . . . . ... .... ... ... ... .... ... Tu` y y´ . . . . .. .. . . . . . . . . . . . . .. . . ............ .. . .. .. . . . . . .. . .... .. . . . . . .. . . . . . . . . . . . . . . . . ... .... ... ... ... .... ... . . .. . . . . . . . . . . . .... ... . .. . . . . . . . ... .... ... .............. ... . .. .... . . ... .... ... ... ... .... .. . .... .. .. . . . ... .... . . .. ...... . . . .. . . . . . . . . . . . . . .. . . ... ... . . ... .... .... . . .... ... ... . . . . . ... . . .. . . . . . . .. . . .... .. .. . .. . . . . . . . . . . . . . . . . ω ω ω . . . .. . .. .. .. . .. .... ..... .. . . . . . . .... ........ . . . . . . . . . . . . . . . . .. . . . . . . .. . . . . . . . . . . . . . . ... .... ....... ... .... ... . . ... . . .... .. . .. . . . . . .. . ... .... ........ .1..... ... .. 2. . . . . . . . . . . . 1 . .. . .. . . . . .. . . . .. . .... . .... .... .. . .... . . . .. ... ..... . . . .. . . . . . . . . . ... . . .... . . .... .. . . .. . . . . .. ........ . .... . .... . .... . . . .. . . . .... . . ... .... ... .... .. .... ... .. . .. . . . . .... . . . . . . . . . .. .... . . ... .... ... ... ... .... .. ... . . .... .. . .. .. . (d o ph´.c tap .... . ... . . .. .. . . . . . . . . . . . . . .. . . . . ... . . . . . . . . . .. . . . . . . . . ... . . . . . . . . . .. . . ..... . ....... .. . .. .. . . . . . . . . .. . . . . . ..... .... ........ ... ... ... .... .... . ¯ˆ u . .... . . . . . ...................... .. . . . . . . . .. . . . .. . ..... . .. .... . . ... .... ... .... ... .... . . ..... . . . . . . . . . . .... . . . . . . . . . . ...... . . .. . . . .. .. .. ..... . . . .. . . . . . . .. .... .. . . . . . ..... . ....... ... ... ..... .... ... . . . .. .... .... . . .. . . . . . . .... . . . . . . ...... . . . .... .. . ......... .. . . . . .. . .. . .. . . . ......... . . . . . . ......... . . . . .... . . ... ... . . . . . . . . . . .... . . . .. . .. . . ............ . ......... ... . . ................ ......... . . .. . . . . . .. . . . . . .. . . . . . . . . .... . .. . . .... .. . . . . . .. .. . .... ....... .... . .. . . ... . . . ω . . ... ... .. . .... .. ... .... .. .. . . ...... ... .... ... . . . . . . .... . ................... .. . .... . . . .. . . . . . . . . . .. .. .... . . ... ..... . .. .... .. . . . .. . 2 .. .... . . ......... ... ... .... ...................... . .. . . . . . . . . . . .... . ..... .. .. .. . . . . . . . . . . . . ... ... .... ... . . . . .. .... .. . . . . . . . . . . . . ... ... . .. .... .... .. ... .. . . . . ........... ........ .................... . . . . . ... ... ... .... ... . . . . . .. .... . . .... . . . . . . ... .... . .. .. .... .. . . . . . . . . . . . . . .. .. .. . . . . . . . . . . .. .... ... ... .... ... . . .. . . .. . . . . . . . . . ... ... .... . ... .. ..... .. . . . . phu thuˆc o ... ... .. ... .. ... .. . . . . . .. . .. . . .. . ............ . .. . .. . . . . . ... ... ........ .. . . ..... ..... ... ... .... ... . ... . . . . . .. . .. . . . . . . . .. . ... ... .... ... . . . . . . . . . . . . . ..... ...... ....... ........ . . ... ... ..... .. . . . .... ... ... . . . . . . .. . .. .. . . . ............ .... ... . .. . .. ... .... . .. .. . . . . .. . . .... ... .... ..... ... .. . . .. . . . ......... ..... ..... ... .... . . . . .. .......... . .... ... . . . . . . . . .. .... ..... . . . . . . . . . . .... ..... .. . . . . .... . . . . . . ω ω . ........ .. ... .. .. .... ... .... .. . . . . . . . . . .. ................. ... . .... . .... ..... .. . . ... . . . . . . . . . . .. . . .. . . . . ... ... ... ... .... ... . . . . . . . . . . . . . .1. . . . . . . ... ..... ......... ..... . . . .. . . . .. . . .. .... ..... ... . . . 2. . . . .. ... . . ... . . ... . . . . . . . . . .. . .. . . . .. . . . . .. . . . ... ... .... . . .. . .. ..... .. . .. . . . . . . . . . ............... ........ . .. . .... ... .. . . . . ....... . . . . . . .. .. ... . . . . . . . . . ....... . ..... .. .. . . . . ...... .. . . . . . . . . ... .. ... ... .... . . . ..... .. . . . . . . .. . . . ... . . . . . . ........ . ......... . . ........ .... .. . . . . . ..... .. .. . . . . . ..... . . .. . . . . . . . . .. ... ... .... ..... .. . . . . . . . . . . . .. ..... . . ´ . • • . ... . sˆ n´t) ou .. . . . . . . . . .. . . . . . . .. . . . . . . . . . . . . ... .. ........... .... .. . . . .. .. . . . . . . . ... ... .... . . . . . . . . . . .. . . . . . . ....... .. . . . . . . . . . . . . . . . . .. . . ... ... ... .... . . .. ... .. . ... ... .... .. . . . . . . . . . .. . . . . . .. ....... . . . . . . . . . . . . .. . . . ... ... ... .... . ... ... .. . ... ... .... .. . . . . . . . . . . . . .. . . . . . . . . . . .. ... ... .... . . . . . . . . . . .. . . . ... ... .. . ... ... .... .. . . . . . . .. . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . .... ... ... .... . . .. ... ... .. . ... ... .... .. . . . . . . . . . . . . . ..... ... ... .. . ... ... .... .. . . . ....... . . . . . . . . . . .. . . . . .... ... ... .... . . . . ....... . .. . . . . . . . . . ........................................................................................................................................................................................................................................................................................................................................................ . . . ... ... ... .... . . .... ... ... .. . ... ... .... .. . . . . . . . . . .. . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . ... . . . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . .. . . . . ... . . . . .... . . ... . . . . . . . . . . ... . . . . ... . . . ... . . . . . . . . . ... . . . . . ..... . ... . . . . . . . . . . ... . . . . . . . . . . . . H` 9.13: C´c kiˆ’u ranh gi´.i gi˜.a hai l´.p c´ thˆ’ x´c d .nh bo.i mang neuron mˆt hoˇc ˙ ˙ ˙ ’ ınh a e ou o o e a ¯i o a . . . ` ng ˆ’n v` hai t´ hiˆu v`o. ˙a hai tˆ a a ın e a . 321
C´c phu.o.ng ph´p cˆu tr´c ´ 9.4 a a a u C´c k˜ thuˆt tr` b`y trong Phˆn 9.3 du.a trˆn nh˜.ng d ac tru.ng d d .o.c cua mˆu ˜ ` ˙ ’ ay a ınh a a e u ¯ˇ ¯o ¯u . a . . . v` khˆng x´t d e n mˆi quan hˆ cˆ u tr´c gˇn liˆn v´.i h`nh dang cua mˆu. Mˇt kh´c, ´eoı ˜ ´ ´ .´ ua` ˙ ’ ao e ¯ˆ o ea a a a . . .o.ng ph´p cˆ u tr´c trong phˆn n`y du.a v`o mˆi quan hˆ nˆi tai cua mˆu d e’ ˙ ˜ ´ ` ´ eo. ˙ ’ c´c phu a aa u aa a o a ¯ˆ . .. nhˆn dang. a . . -o a ´˜ ´ 9.4.1 Dˆi s´nh sˆ mˆ u oa Tu.o.ng tu. v´.i kh´i niˆm nhˆn dang theo khoang c´ch nho nhˆ t trong Phˆn 9.3.1, o. d ˆy ’´ ` ˙ ’ ˙a ˙ ¯a ’ .o ae a. a a . . ch´ng ta s˜ so s´nh c´c d u.`.ng biˆn cua v`ng qua c´c d ac tru.ng sˆ mˆu. V´.i c´c kh´i ´˜ e˙u ’ u e a a ¯o a ¯ˇ oa oa a . .o.ng tu., k´ hiˆu k, gi˜.a hai ` niˆm d a tr` b`y trong Phˆn 8.2.2, ta d inh ngh˜a d ˆ tu e ¯˜ ınh a a ¯. ı ¯o .ye u . . . d u.`.ng biˆn cua v`ng (c´c h` dang) A v` B l` bˆc l´.n nhˆ t d e’ c´c sˆ mˆu vˆn tr`ng ´˙ ´˜ ˜ e˙u ’ ¯o a ınh . a aao a ¯ˆ a o a a u . .`.ng ho.p c´c sˆ mˆu cua c´c d .`.ng biˆn d ong d .o.c biˆ’u ˙ ˙ ’ ´˜ ˙ a ¯u o ’ nhau. Chˇng han, trong tru o a .aoa e ¯´ ¯u . e . diˆn bo.i m˜ x´ch 4-hu.´.ng, A v` B c´ m´.c d ˆ tu.o.ng tu. k nˆu s4 (A) = s4 (B ), s6(A) = ˜ ´ ˙ ’ e aı o a o u ¯o e . . s6 (B ), s8(A) = s8(B ), . . . , sk (A) = sk (B ), sk+2 (A) = sk+2 (B ), sk+4 (A) = sk+4 (B ), · · · , trong d ´ sk l` sˆ mˆu bˆc k. Khoang c´ch gi˜.a hai mˆu A v` B l` nghich d ao cua ´˜ ˜ ˙’ . ¯˙ ’ ˙ ’ ¯o ao a a a u a a a . .c d o tu.o.ng tu. m´ ¯ˆ u . . 1 d(A, B ) = . k ˜a ˙ ’ Dˆ d`ng chı ra e ´ ˙ ’ ˙ ’ T´ chˆt 9.4.1 H`m khoa ng c´ch thoa quan hˆ ınh a a a e . 1. d(A, B ) ≥ 0 v´.i moi A, B ; dˆ u bˇ ng xa y ra nˆu v` chı’ nˆu A = B. a` ´a ´ ´ ˙ ’ e a ˙e o . 2. d(A, B ) = d(B, A). 3. d(A, C ) ≤ max[d(A, B ), d(B, C )]. Ch´ng ta c´ thˆ’ su. dung d ˆ tu.o.ng tu. k hoˇc khoang c´ch d dˆ’ x´c d .nh m´.c d o tu.o.ng ˙’ ˙ o e˙ . ˙ ’ u ¯o a a ¯e a ¯i u ¯ˆ . . . . . cua hai d .`.ng biˆn. Nˆu su. dung m´.c d ˆ tu.o.ng tu. k th` hai h` dang nhu. nhau ´˙. ˙ ’ ’ tu ¯u o e e u ¯o ı ınh . . . . .n (ch´ y, k = ∞ d ˆi v´.i hai dang tr`ng nhau). Ngu.o.c lai c˜ng dung khi su. ´ ´ ˙ ’ nˆu k l´ e o u´ ¯o o u ..u ¯´ . ˙ ’ dung d ˆ d o khoang c´ch d. ¯o ¯ a . . 322
-o a ˜ ´ 9.4.2 Dˆi s´nh chuˆ i o Gia su. hai d u.`.ng biˆn A, B d u.o.c m˜ ho´ th`nh c´c chuˆi (xem Phˆn 8.5) a1 a2 . . . an ˜ ` ˙˙ ’’ ¯o e ¯. aaa a o a .o.ng u.ng. Dˇt -a v` b1 b2 . . . bm tu a ´ . M = #{k ∈ N | ak = bk } l` sˆ c´c vi tr´ d u.o.c d oi s´nh gi˜.a hai chuˆi. Sˆ c´c k´ hiˆu khˆng d .o.c d ˆi s´nh l` ˜ ´ ´ ´ ´ a o a . ı ¯ . ¯ˆ a u o oa y e o ¯u . ¯o a a . Q = max(|A|, |B |) − M trong d ´ |X | l` d o d`i (sˆ c´c k´ hiˆu) chuˆi biˆ’u diˆn X. Dˆ thˆ y rˇ ng, Q = 0 nˆu ˙ ˜ ˜ ˜a` ´ e´a ´ ¯o a ¯ˆ a o a y e oe e e . . ’´ a ˙e v` chı nˆu A v` B tr`ng nhau. a u Khi d ´ ta c´ thˆ’ d inh ngh˜a m´.c d ˆ tu.o.ng tu. gi˜.a A v` B l` sˆ ˙ ´ ¯o o e ¯. ı u ¯o .u a ao . M M R= = . Q max(|A|, |B |) − M a a` ´ ´ ´ Do d ´ R = ∞ nˆu d oi s´nh ho`n to`n v` bˇ ng 0 nˆu khˆng c´ k´ hiˆu n`o trong A ¯o e ¯ˆ a a a e o oy e a. .o.c d ˆi s´nh (M = 0 trong tru.`.ng ho.p n`y). Do d oi s´nh d .o.c thu.c hiˆn trˆn ´a ´ a ¯u . v` B d u . ¯o a¯ o a ¯ˆ e e . . . .ng k´ hiˆu, nˆn d e’m xuˆ t ph´t trˆn biˆn l` quan trong (theo ngh˜ giam sˆ lu.o.ng ˙ ´ ´ ıa ˙ ’ t` u ye e ¯iˆ a ae ea o. . . t´nh to´n). V` vˆy d e’ tˇng tˆc d ˆ thu.c hiˆn, ta thu.`.ng chuˆ’n ho´ chuˆi hoˇc xuˆ t ˙ ˙ ˜ ´. ´ ı a ı a ¯ˆ a o ¯o . e o a a o a a . . . ph´t t`. c`ng mˆt d iˆ’m. Ch´ng ta xuˆ t ph´t t`. mˆt d iˆ’m tu` y trˆn chuˆi A sau d ´ ˙ ˙ ˜ ´ auu o ¯e u a a u o ¯e y´ e o ¯o . . cho B dich chuyˆ’n. Mˆi lˆn dich chuyˆ’n, ta d` ng th`.i t´ m´.c d ˆ tu.o.ng tu. R. Gi´ ˙ ˙ ˜a . o` e e ¯ˆ o o ınh u ¯o a . . . .n nhˆ t cho d oi s´nh tˆt nhˆ t gi˜.a hai chuˆi. ˜ ´ ´ ´ ´ tri R l´o a ¯ˆ a o au o . 9.4.3 Phˆn t´ c´ ph´p a ıch u a Phu.o.ng ph´p c´ ph´p l` mˆt trong nh˜.ng c´ch tiˆp cˆn phˆ’ biˆn d .o.c su. dung d e’ ˙´ ˙ ´. o e ¯u . ˙ . ’ auaao u a ea ¯ˆ . nhˆn dang cˆ u tr´c. Vˆ co. ban, y tu.o.ng cua nhˆn dang mˆu c´ ph´p l` d ˇc ta mˆt ˜ ´ ` ˙´˙ ’ ’ ˙ ’ a u a a ¯a ˙ o .’. a a u e a . . . . tˆp c´c nguyˆn so. (xem Phˆn 8.5), mˆt tˆp c´c quy tˇc (o. dang vˇn pham) chi phˆi ´’ ` ´ a˙. aa e a oaa a o . .. . .a c´c nguyˆn so., v` mˆt bˆ nhˆn dang (c`n goi l` automat) m` o. d ´ ´ a ˙ ¯o ’ mˆi quan hˆ gi˜ a o eu e aooa o .a . .. . . c´c cˆ u tr´c d u.o.c x´c d .nh bˇ ng tˆp c´c quy tˇc trong vˇn pham. Tru.´.c hˆt ch´ng ` ´ ´ ´ aa u ¯ . a ¯i a aa a a oe u . . . rˆng cho vˇn pham ˜ ˙aaa ’ ¯´ e ˙ . ’ ta khao s´t c´c vˇn pham v` automat dang chuˆi, sau d o s˜ mo o a o a . . . .o.ng u.ng. Nhˇc lai rˇ ng c´c chuˆi v` cˆy l` nh˜.ng miˆu ta mˆu cˆ u a.` ´ ˜ ’˜´ e˙aa cˆy v` automat tu aa ´ a a o aa a u .o.c su. dung trong gi´o tr`nh n`y. tr´c ch´ d . ˙ . ’ u ınh ¯u a ı a 323
˜ Nhˆn dang c´ ph´p chuˆ i a u a o . . Ch´ng ta gia thiˆt rˇ ng c´c v`ng anh hay c´c d oi tu.o.ng quan tˆm d a d .o.c biˆ’u diˆn ˙ e` ˜ ´a ´ ˙ ’ au˙ ’ u a ¯ˆ a ¯˜ ¯u . e e . o. dang chuˆi su. dung nh˜.ng nguyˆn so. th´ch ho.p nhu. d a tr`nh b`y trong Phˆn 8.5. ˜’ ` ˙. ’ o˙. u e ı ¯˜ ı a a . Vˇn pham chuˆ i. Gia su. c´ hai l´.p ω1 , ω2 , trong d ´ c´c mˆu l` c´c chuˆi nguyˆn ˜ ˜ ˜ ˙˙o ’’ a o o ¯o a a aa o e . so.. Ch´ng ta c´ thˆ’ hiˆ’u mˆi nguyˆn so. l` mˆt k´ hiˆu chˆ p nhˆn trong bang ch˜. ˙˙ ˜ ´ ˙ ’ u oee o e aoye a a u . . . . vu.ng) theo vˇn pham n`o d ´, trong d o vˇn pham l` tˆp c´c quy tˇc c´ ´ ˙ ’ (hay bang t` . u a a ¯o ¯´ a aa a au . . . ph´p anh hu.o.ng d e n viˆc tao ra c´c cˆu d u.o.c xˆy du.ng t`. c´c k´ hiˆu trong bang ´ a˙ ’ ˙ ’ ˙’ ¯ˆ e. a a ¯. a ua ye . . . .. Tˆp c´c cˆu d .o.c sinh bo.i vˇn pham G goi l` ngˆn ng˜. v` k´ hiˆu l` L(G). Do ˙a ’ ch˜u a a a ¯u . .a o uay e a . . . d ´ c´c cˆu l` c´c chuˆi k´ hiˆu (biˆ’u diˆn mˆu hiˆn h`nh) v` c´c ngˆn ng˜. tu.o.ng u.ng ˙ ˜ ˜ ˜ ¯o a a a a oye e e a ea aa o u ´ . . .i c´c l´.p mˆu. ˜ v´ a o o a ´ ˙a ’ ˙ ’ ˙ ’ Khao s´t hai vˇn pham G1 , G2 sao cho c´c quy tˇc c´ ph´p cua G1 chı sinh ra a a aua . .o.ng u.ng c´c mˆu thuˆc l´.p ω v` c´c quy tˇc c´ ph´p cua G chı sinh ra ˜ ´ ˙ ’ ˙ ’ c´c cˆu tu aa ´ a a oo 1aa aua . 2 c´c cˆu tu.o.ng u.ng c´c mˆu thuˆc l´.p ω2 . Khi c´c vˇn pham n`y d ˜ d u.o.c thiˆt lˆp th` ˜ ´. aa ´ a a oo aa a ¯a ¯ . ea ı . . qu´ tr` nhˆn dang mˆu theo c´ ph´p ho`n to`n d .n gian: V´.i mˆt cˆu s biˆ’u diˆn ˙ ˜ ˜ ˙ ’ a ınh a a ua a a ¯o ooa e e . . . .a x´c d nh, ch´ng ta kiˆ’m tra xem ngˆn ng˜. n`o ch´.a s. Nˆu s ∈ L(G ) ta ˙ ˜ ´ mˆu p chu a ¯i a u e o ua u e . 1 ˜u p thuˆc l´.p ω1 ; nˆu s ∈ L(G2 ) ta n´i mˆu p thuˆc l´.p ω2 . Nˆu cˆu thuˆc ca ˜ ´ ´a o˙ ’ n´i mˆ oa oo e oa oo e . . . hai ngˆn ng˜. th` ch´ng ta khˆng thˆ’ phˆn loai mˆu p v` do d o s (cˆu khˆng ho.p lˆ) ˙ ˜ o uıu o ea a a ¯´ a o .e . . .o.c loai bo khoi hai ngˆn ng˜.. ˙ ’ ˙ ’ du . ¯ o u . Ho`n to`n tu.o.ng tu., khi c´ nhiˆu l´.p mˆu, ch´ng ta s˜ su. dung thˆm c´c vˇn ˜ `o e˙ . ’ a a o e a u e aa . pham d e’ sinh ra c´c ngˆn ng˜. tu.o.ng u.ng c´c l´.p mˆu. Trong tru.`.ng ho.p n`y, ta n´i ˙ ˜ . ¯ˆ a o u ´ ao a o a o . .p ω nˆu n´ biˆ’u diˆn cˆu ho.p lˆ thuˆc ngˆn ng˜. L(G ). Cˆu thuˆc nhiˆu ˙ ˜ ˜a ´oe ` mˆu thuˆc l´ a oo ie e .e o o u a o e . . . . i ho.n mˆt ngˆn ng˜. s˜ d .o.c goi l` khˆng ho.p lˆ v` bi loai bo. . ea. . ˙ ’ o o u e ¯u . . a o . . -. .´ Dinh ngh˜ 9.4.2 Vˇn pham l` bˆ bˆn ıa a aoo . G = (N, Σ, P, S ), trong d ´ ¯o 1. N l` tˆp h˜.u han c´c biˆn goi l` c´c phˆn tu. khˆng kˆt th´c, ´ ` ´ a˙ ’ aa u .a e . aa o e u . 2. Σ l` tˆp h˜.u han c´c hˇ ng goi l` c´c phˆn tu. kˆt th´c, .a` ` ’´ a ˙e aa u a . aa u . ´ 3. P l` tˆp c´c quy tˇc sinh, aa a a . ´a 4. S ∈ N l` k´ hiˆu bˇt d` u. a y e a ¯ˆ . 324
Ngo`i ra N ∩ Σ = ∅. Ch´ng ta s˜ k´ hiˆu c´c ch˜. c´i viˆt hoa A, B, . . . , S, . . . , l` c´c ´ a u ey e a ua e aa . . c´c viˆt thu.`.ng d` u tiˆn cua bang ch˜. a, b, c, . . . , ´ ´ ˙’ ˙ ’ k´ hiˆu khˆng kˆt th´c. C´c ch˜ a ye o e u a u e o ¯ˆ a e u . l` c´c k´ hiˆu kˆt th´c. C´c ch˜. c´i viˆt thu.`.ng o. cuˆi bang ch˜. v, w, x, y, z l` c´c ´ ´ ´’ ˙ ’o˙ aa y e e u a ua e o u aa . . Hy Lap α, β, θ, . . . , l` c´c chuˆi gˆm c´c ˜o ˜o o` ´ o` chuˆi gˆm c´c k´ hiˆu kˆt th´c. C´c k´ tu ayee u a y. aa a . . .a k´ hiˆu n`o) k´ hiˆu ˜ ´ ´ k´ hiˆu kˆt th´c v` khˆng kˆt th´c. Cˆu rˆng (cˆu khˆng ch´ y e a yee uao e u ao a o u ye . . . .i bang ch˜. V, k´ hiˆu V ∗ l` tˆp tˆ t ca c´c cˆu d .o.c tao t`. nh˜.ng ´i c`ng, v´ ˙ ´ ˙ a a ¯u . . u u ’ ’ l` λ. Cuˆ u a o o u ye aa a . . . cua V. ` phˆn tu ˙ a˙’ ’ Vˇn pham (chuˆi) d u.o.c tao ra t`. c´c luˆt sinh cua ch´ng. Vˇn pham ch´ quy ˜ ˙ ’ a o ¯. . ua a u a ınh . . . . canh l` hai vˇn pham d .o.c ch´ y nhiˆu nhˆ t trong nhˆn dang ` ´ v` vˇn pham phi ng˜ ˙ u’ aa a a . ¯u . u´ e a a . . . ˜u bˇ ng c´ch phˆn t´ c´ ph´p. Vˇn pham ch´ quy chı sinh ra c´c dang A → aB ` ˙’ mˆ a a a a ıch u a a ınh a. . .i A, B ∈ N v` a ∈ Σ. Vˇn pham phi ng˜. canh chı sinh ra c´c dang u˙ ’ ˙ ’ hoˇc A → a, v´ a o a a a. . . A → α, v´.i A ∈ N v` α ∈ (N ∪ Σ)∗ \ {λ}; t´.c l` α l` chuˆi kh´c chuˆi rˆng v` d u.o.c ˜ ˜˜ o a ua a o a oo a¯ . . c´c k´ hiˆu kˆt th´c v` khˆng kˆt th´c. ´ ´ tao tu` y t` a y e e y´ u uao e u . . V´ du 9.4.3 Gia su. d ˆi tu.o.ng trong H` 9.14(a) d u.o.c biˆ’u diˆn bo.i bˆ khung cua ˙ ˜ ’’´ ˙ ˙ ¯o ˙o ’. ˙ ’ ı. ınh ¯. e e . . trong H`nh 9.14(b) d e’ miˆu ta cˆ u tr´c ˙ e ˙a ’´ n´ v` ch´ng ta d .nh ngh˜ hai nguyˆn so oa u ¯i ıa e ı ¯ˆ u cua bˆ khung. X´t vˇn pham G = (N, Σ, P, S ) v´.i N = {A, B, S }, Σ = {a, b, c} v` ˙’o ea o a . . .o.ng ´ P = {S → aA, A → bA, A → bB, B → c}, trong d ´ c´c k´ hiˆu kˆt th´c a, b, c tu ¯o a y e e u . u.ng c´c nguyˆn so. trong H` 9.14(b). Nhu. trˆn, S l` k´ hiˆu kho.i d` u cua c´c chuˆi˜ ˙ ¯ˆ ˙ a ’a ’ ´ a e ınh e ay e o . trong ngˆn ng˜. L(G). Chˇng han, ´p dung mˆt lˆn quy tˇc th´. nhˆ t v` sau d o hai ˙ ’ ´ o` ´ o u a .a .a a u aa ¯´ . lˆn quy tˇc th´. hai ta d u.o.c ´ ` a a u ¯. S ⇒ aA ⇒ abA ⇒ abbA, trong d ´ (⇒) c´ ngh˜a chuˆi xuˆ t ph´t t`. S v` su. dung c´c quy tˇc trong P. Quy tˇc ˜ ´ ´ ´ a˙ .’ ¯o o ı o a au a a a th´. nhˆ t cho ph´p viˆt lai S bo.i aA, v` quy tˇc th´. hai cho ph´p viˆt lai A l` bA. ´ ´ ´ ´ ˙ ’ u a e e. a a u e e. a Do c´ mˆt k´ hiˆu khˆng kˆt th´c trong chuˆi abbA nˆn ta lai c´ thˆ’ tiˆp tuc ´p dung ˙´ ˜ ´ ooye o e u o e . o ee .a . . . . hai, mˆt lˆn quy ´ ˙ ’ ´ ` o` c´c quy tˇc trˆn d ´. Chˇng han, ´p dung thˆm hai lˆn quy tˇc th´ a a e ¯o a .a e a a u .a . tˇc th´. ba v` mˆt lˆn theo quy tˇc th´. tu. ta d .o.c chuˆi abbbbbc (tu.o.ng u.ng v´.i cˆ u ´ ´ ˜ a o` ´ a u .a a u ¯u . o ´ oa . trong chuˆi n`y l` k´ hiˆu kˆt th´c ˜ ´’ ` ´ ıa ˙a a˙ ’ tr´c trong H` 9.14(c)). V` tˆ t ca c´c phˆn tu u ınh o a ay e e u . nˆn khˆng thˆ’ ´p dung thˆm quy tˇc n`o trong P. Ngˆn ng˜. sinh bo.i c´c quy tˇc cua ˙ ´ ´’ ˙a ’ a˙ e o ea e aa o u . .o.c lˇp lai n n vˇn pham n`y l` L(G) = {ab c | n ≥ 1}, trong d ´ b c´ ngh˜ k´ hiˆu b d u . a . a aa ¯o o ıa y e ¯ . . . ˙ sinh ra c´c bˆ khung c´ dang trong H` 9.14(c) ’ ` ˙o e ’ n lˆn. N´i c´ch kh´c, G chı c´ thˆ a oa a ao o. ınh . .ng v´.i d o d`i tu` y. nhu o ¯ˆ a y´ . Su. dung ng˜. ngh˜ Trong v´ du tru.´.c ch´ng ta d a gia thiˆt mˆi liˆn kˆt gi˜.a c´c ˙. ’ ´oeeua ´ ´ ¯˜ ˙’ u ıa. ı. o u e . chı c´ thˆ’ d u.o.c nˆi tai c´c chˆ m d am trong H` 9.14(b). Trong nhiˆu t`nh ˙ ´ ´ `ı nguyˆn so ˙ o e ¯ . o . a ’ e a ¯ˆ ınh e . 325
..................... . . .. . . . . . . .. . .................. .. . . . .. . . . ... . ... . . .. .. . . .. . .. . .. .. . . . . .. .. .. .... .... . ... ... . .. . . . . .. .. . .. . . . .. . .. .. . . . . . .... . .... . . . ...... .... . . . ... . . ... ... .. . . ................................................. . .. . .. . . ... . . . . . . . . . . . . . . . . . . . . . . . . . .. .. . .. . . . .. . . . . . ...... .... ..... .... ..... .... ..... .... ..... . . . . . ... . . .. . . . .. . . . .. . . . . . . . . . . . . . . . . .. . .. .. . . . .................................................. . . . ... . . . . . . . . . . . . . . . . . . . . . . . . .. ... . . .. . . ....... . . . . ...... .. ..... . .. .. .. . . . .. . . . . .. . . .. . .. . .. . . . . .. . .... . . . .. . .... ... ... .. .. . .. . . ... . . .. . . .. .. . . . ... . . . .. . . . . . .. . ... . ..................... ... . . .. . . .. .................. . (a) .. ... .. .. .. .. .. ... ... .. ... b ... ... .. .. ... ... .. ... ... .. ... a• •c •......................• . .. . . . ... ... .. .. ... ... .. .. ... .. ... .. ... . .. .. .. .. . . .. .. .. .. (b) ... . .. .. ... ... .. .. .. .. ... .. .. ... ... .. .. . ... .. .. ............................................................................................. • • • • • • .. . .... . . . . . . . . . . . . . . . . . . ... . . . . . . . . . . . . . . . . . . . . . . .... . .. .. ... .. .. .. .. ... ... .. .. ... .. .. ... ... .. .. ... .. (c) H` 9.14: (a) Dˆi tu.o.ng d .o.c biˆ’u diˆn qua bˆ khung; (b) c´c nguyˆn so.; (c) cˆ u -o ˙ ˜ ´ ´ ınh ¯u . e e o a e a . . tr´c tao ra su. dung vˇn pham ch´ quy. ˙. ’ u. a ınh . huˆng ph´.c tap ho.n, ch´ng ta cˆn phai miˆu ta khˆng nh˜.ng mˆi liˆn kˆt gi˜.a c´c ´ ` ´ ´ua ˙’ e˙ ’o o u. u a u oee .i c´c nhˆn tˆ kh´c (chˇng han d o d`i v` hu.´.ng cua nguyˆn ´ ˙ ’ ´ ´ ˙ ’ nguyˆn tˇc, m` c`n d oi v´ a ea a o ¯ˆ o aoa a . ¯ˆ a a o e . so.) v` sˆ lˆn ´p dung mˆt quy tˇc. Diˆu n`y c´ thˆ’ thu.c hiˆn bˇ ng c´ch su. dung c´c a -` ˙ ´ .` a o` a ´a ˙. ’ o eaoe. ea a a . . . ngh˜ d u.o.c lu.u tr˜. trong co. so. tri th´.c cua Bang 9.1. Vˆ co. ban, ´ ` ˙ ’ ˙ ’ ˙ ’ ˙ ’ nguyˆn tˇc ng˜ ea u ıa ¯ . u u e c´ ph´p gˇn liˆn cˆ u tr´c cua mˆt d ˆi tu.o.ng v` sinh bo.i c´c quy tˇc, trong khi ng˜. ´e´ ´ uaa`a ´ u˙ ’ ˙a ’ o ¯o a a u . . ´ ˙ ’ ngh˜ d` cˆp d e n t´nh dung d ˇn cua cˆ u tr´c. Chˇng han, cˆu lˆnh trong FORTRAN: ´ ’´ ıa ¯ˆ a ¯ˆ ı ¯´ ¯a ˙ a e. u a ae . . .ng chı dung vˆ mˇt ng˜. ngh˜ khi C = 0. Hoˇc `aua `a ˙ ¯´ ’ A = B/C dung vˆ mˇt c´ ph´p, nhu ¯´ e. e. u ıa a. . ph´p, ca vˆ mˇt ng˜. ´´ ˙` a ˙` a ’e . ’e . cˆu: “nh` to´n hoc v˜ d ai n`y viˆt rˆ t d ep” dung ca vˆ mˇt ng˜ a a a a . ı ¯. a e a ¯. ¯´ u u ngh˜ nhu.ng cˆu “nh` to´n hoc v˜ d ai n`y ˇn co ngon miˆng” dung vˆ mˇt ng˜. ph´p `a . ı ¯. a a ˙ ’ ıa; a aa e ¯´ e. ua . .ng sai vˆ mˇt ng˜. ngh˜ `a nhu e. u ıa. Gia su. ch´ng ta muˆn gˇn thˆng tin v`o vˇn pham trong v´ du tru.´.c. Thˆng ´´ ˙˙ ’’ u oa o aa ı. o o . .o.c d´nh k`m theo c´c quy tˇc sinh trong Bang 9.1. Su. dung thˆng tin tin c´ thˆ’ d u . ¯ı ˙ ´ ˙ ’ ˙. ’ o e¯ e a a o ng˜. ngh˜ ch´ng ta c´ thˆ’ ´p dung mˆt v`i nguyˆn tˇc dˆ’ miˆu ta mˆt l´.p v´.i rˆ t ˙ ˙ e ˙oo ´ ´ ’. u ıa, u o ea oa e a ¯e oa . . .ng h˜.u han). Chˇng han, bˇ ng c´ch thay d o’i hu.´.ng θ trong Bang 9.1 ˙ ˜ ˙ ’ ` ` ˙ ’ nhiˆu mˆu (nhu e a u a a a ¯ˆ o . . ch´ng ta c´ thˆ’ d inh ngh˜ c´c nguyˆn so. v´.i hu.´.ng bˆ t k`. Tu.o.ng tu., d ` u kiˆn c´c ˙ ´ u o e ¯. ıa a e o o ay . ¯iˆ e ea . . c`ng hu.´.ng cho ph´p loai bo c´c cˆ u tr´c kh´c biˆt v´.i mˆu co. ban trong ˜ ´ ˙a a ’ ˙ ’ nguyˆn so u e o e u a eo a . . H` 9.14(a). ınh ˜ ˜ Automat nhˆn dang chuˆ i. Ch´ng ta d a minh hoa vˇn pham sinh ra c´c mˆu. a o u ¯˜ a a a . . . . 326