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

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

Thêm vào BST

Báo xấu

97
lượt xem 17
download

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

Với một file ảnh raw, bạn có thể dễ dàng thay đổi cân bằng trắng của bức ảnh sau đó. Mặc dù cơ chế cân bằng trắng tự động (Auto White Balance) trên hầu hết các máy ảnh hiện nay rất tiên tiến, vẫn rất nhiều trường hợp cơ chế này bị đánh lừa. Nếu bạn đã từng cố sửa một bức ảnh JPEG sai độ màu, bạn sẽ biết thực ra chỉnh sửa cân bằng trắng không phải là một vấn đề nhỏ. Với ảnh raw, bạn không cần phải lo về điều này. ...

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 7

Thˆng tin ng˜. ngh˜ ´ Quy tˇc a o u ıa Chı d u.o.c nˆi d e n a tai chˆ m d am (chˆ d ´nh dˆ u). Hu.´.ng cua a, ˜ ´´ ´ ´ ˙ ¯ . o ¯ˆ ’ ˙ ’ S → aA a ¯ˆ o ¯a a o . . .´.ng (so v´.i truc ho`nh) cua d u.`.ng trung tru.c cua ˙ ¯o ’ ˙ ’ k´ hiˆu θ, l` hu o ye a o a . . . d oan thˇng nˆi hai d e’m khˆng d anh dˆ u. Mˆi d . n t`. d iˆ’m d anh ˙ ˙ ˙ ’ ˜ ´ ´ ¯. a o ¯iˆ o ¯´ a o ¯oa u ¯ e ¯´ dˆ u d e n d e’m khˆng d anh dˆ u c´ d ˆ d`i 0.3cm. ˙ ´´ ´ a ¯ˆ ¯iˆ o ¯´ a o ¯o a. Chı d u.o.c nˆi d e n b tai chˆ m d am. Khˆng c´ hai nguyˆn so. c`ng ´´ ´ ˙ ¯ . o ¯ˆ ’ A → bA a ¯ˆ o o e u . . nˆi tai mˆt chˆ m d am. Hu.´.ng cua b tr`ng v´.i hu.´.ng cua a. Dˆ -o ´ ´ ˙ ’ ˙ ’ o. o a ¯ˆ o u o o . . . d`i cua b l` 0.25cm. Quy tˇc n`y khˆng thˆ’ ´p dung trˆn 10 lˆn. ˙ ´ ` a˙ ’ a aa o ea e a . Hu.´.ng cua a tr`ng v´.i hu.´.ng cua b. Chı c´ d o.n liˆn kˆt v` d .o.c ´ ˙ ’ ˙ ’ ˙ o¯ ’ A → bB o u o o e e a ¯u . thu.c hiˆn tai c´c chˆ m d e’m. ˙ ´ e.a a ¯iˆ . . Hu.´.ng cua c tr`ng v´.i hu.´.ng cua a. Chı c´ d o.n liˆn kˆt v` d .o.c ´ ˙ ’ ˙ ’ ˙ o¯ ’ B→c o u o o e e a ¯u . .c hiˆn tai c´c chˆ m d e’m. ˙ ´ thu e.a a ¯iˆ . . Bang 9.1: V´ du vˆ thˆng tin ng˜. ngh˜ d .o.c gˇn v´.i c´c quy tˇc sinh. ´ ´ ı.` o ˙ ’ e u ıa ¯u . a o a a 327
Trong phˆn sau ch´ng ta khao s´t b`i to´n nhˆn dang mˆu c´ thuˆc ngˆn ng˜. L(G) ˜ ` ˙aaa ’ a u a ao o o u . . . .i vˇn pham G hay khˆng. C´c kh´i niˆm co. ban trong nhˆn dang c´ ph´p c´ ˙ ’ ˙ ’ sinh bo a o a ae a uao . . . . thˆ’ minh hoa bˇ ng c´ch su. dung mˆ h`nh to´n hoc cua c´c m´y t´nh goi l` automat. ˙ ` ˙. ’ ˙a ’ e .a a oı a aı .a . .a v`o mˆu dang chuˆi, mˆt automat c´ kha nˇng nhˆn dang mˆu n`y c´ thuˆc - ˜ ˜ ˜ ˙a ’ Du a a o o o a a ao o . . . . . . . d u.o.c gˇn v´.i automat d o khˆng. O d ˆy, ch´ng ta chı tˆp trung v`o c´c ˙ ¯a ’ ´ ˙a ’. ngˆn ng˜ ¯ . a o o u ¯´ o u aa .u han l` c´c bˆ nhˆn dang ngˆn ng˜. sinh bo.i vˇn pham ch´ quy. ˙a ’ automat h˜ u . aa o a o u ınh . . . . Dinh ngh˜ 9.4.4 Automat h˜.u han l` mˆt bˆ nˇm th`nh phˆn -. ` ıa u . a o oa a a .. Af = (Q, Σ, δ, q0, F ), trong d ´ ¯o 1. Q l` tˆp h˜.u han kh´c trˆng goi l` tˆp trang th´i, ´ aa u a o . aa a . . . . 2. Σ l` bang ch˜. (h˜.u han k´ hiˆu), a˙ ’ uu ye . . 3. δ l` ´nh xa t`. Q × Σ v`o ho c´c tˆp con cua Q goi l` h`m chuyˆ’n trang th´i, ˙ ˙ ’ aa .u a .aa .aa e a . . 4. q0 l` trang th´i kho.i d` u, v` ˙ ¯ˆ ’a a. a a ´ ´ 5. F ⊂ Q l` tˆp c´c trang th´i cuˆi hay trang th´i chˆ p nhˆn. aa a a o a a a . . . . V´ du 9.4.5 X´t automat Af = (Q, Σ, δ, q0, F ), v´.i ı. e o Q = {q0, q1, q2 }, Σ = {a, b}, F = {q0}, δ (q0, a) = {q2}, δ (q0, b) = {q1}, δ (q1, a) = {q2}, δ (q1, b) = {q0}, δ (q2, a) = {q0}, δ (q2, b) = {q1}. Nˆu automat o. trang th´i q0 v` t´n hiˆu v`o l` a th` automat chuyˆ’n trang th´i l` q2. ˙ ´ ˙. ’ e a aı eaa ı e aa . . .o.ng tu., nˆu t´ hiˆu v`o kˆ tiˆp l` b th` automat s˜ chuyˆ’n sang trang th´i q , v` ˙ ´ ´´ Tu . e ın e a e e a ı e e a1a . . vˆn vˆn. Trong tru.`.ng ho.p n`y, trang th´i d` u tr`ng v´.i trang th´i kˆt th´c. ´ aa o a a ¯ˆa u o ae u . . . ı . e -ˆ . H` 9.15 l` d` thi trang th´i biˆ’u diˆn cho automat trong v´ du trˆn. D` thi ˙ ˜ ınh a ¯ˆ . . o a e e o .o.ng u.ng v´.i c´c trang th´i v` cung liˆn thuˆc hai d ˙nh a` trang th´i gˆm c´c d ˙nh tu ’ ’ o a ¯ı ´ oa aa e o ¯ı . . . .o.ng u.ng c´ thˆ’ chuyˆ’n t`. trang th´i n`y sang trang th´i kh´c. Trang th´i cuˆi ˙ ˙ ´ tu ´ oe eu. aa a a a o . . 328
b .. ...................................................................... ... ... ... ..... ... ..... . . ... ... ..... ... ..... ... ..... . ..... ... .... .............. ........... . ... ..... .... . ... ........... ....... .... ......... . ... ........ .... .... .... ... ........ ..... ...... . . ..... ...... ....... ..... ......... .. ... . .... .. . ....................... .. ...... .. .. . .... .... . .. . . .. . . .. . .. q q .. . . .. . . .. . .. . .. . 0 .... .. 1 ... .. .. . .. . . .. . . .. . .. ... .. .......... ............. .. ... ....... ..... ........ ......... . .. .. . ..... . . .. . ... ... ..... ..... ..... . ............... ............. .... ... . . ..... .... .... .......... .... ... ... . ....... .... .. .. .... .......... .... ... .. . . ... ... .... ........... . .. .. . .............. .. ... ... ...... .................................................................. . . . ..... ... ..... ... ...... ..... ... ..... ... ..... ... .. ... . ... .. ... ... . . . ... . .... . ... . . ... . ... . . . .... . . .... . . ... . . . ... .. b . .. . . ... ... .. .. .. ... .. ... . .. .. ... .. . ... .. . .. .. ... .. . .. ... .. ... ... a a . .. .. . .... .. .. .. .. . .. .. ... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. . .. .. .. .. .. .. .. .. .. ... .. .. .. .. .. .. .. .. .... a .. b .. ... .. .. .. ... .. ... .. .. .. . ... .. . .. ... .. .. .. .. .. .. ... .. .. ... .. ... ... .. .. ... . .. . ... ... .. ... ... .. . . .. . .... . .... . .. . . .. . ... . ... . ........... .... . .. . . . .. . .... ..... ... .... .. .... . .. .... .. .. .... .. .... .... . . ........ .... .. .. .. .... . q . .... ...... . ... . .. 2 ....... . . . . .. .. .. .. .... ..... ... .. ......... .... H` 9.15: V´ du vˆ automat h˜.u han. ı.` ınh e u . tu.o.ng u.ng d ˙nh d .o.c bao hai v`ng tr`n v` mˆi cung d .o.c g´n mˆt k´ hiˆu gˆy ra ˜ ’ ¯u . ´ ¯ı o oao ¯u . a oyea . . .a c´c trang th´i d u.o.c nˆi bo.i cung n`y. Trong tru.`.ng ho.p n`y, trang chuyˆ’n d o’i gi˜ a ˙ ˙ ´’ a¯. o ˙ e ¯ˆ u a o a . . . .i d` u tr`ng v´.i trang th´i kˆt th´c. Chuˆi w c´c k´ hiˆu kˆt th´c goi l` ˜ ´ ´ ˙a ’ th´i kho ¯ˆ a u o ae u o ayee u .a . . .o.c hay d u.o.c nhˆn dang bo.i mˆt automat nˆu kho.i d` u t`. trang th´i q , ´ ´ ˙’ ˙ ¯ˆ u . ’a chˆ p nhˆn d u . a a¯ ¯. a. o e a0 . . . d˜y c´c k´ hiˆu (bˇt gˇp khi duyˆt w t`. tr´i sang phai) s˜ khiˆn automat hoat d ˆng ´. ´ ˙e ’ aaye aa e ua e . ¯o . . . .o.c duyˆt. v` chuyˆ’n d e n trang th´i cuˆi sau khi k´ hiˆu cuˆi c`ng trong chuˆi w d u . ˙´ ˜ ´ ´ a e ¯ˆ a o ye ou o ¯ e . . . ˙ ng han, automat trong H` 9.15 nhˆn dang d .o.c chuˆi w = abbaabb nhu.ng loai ’ ˜ Chˇ a ınh a ¯u . o . . . . ˜ ˙ ’ bo chuˆi w = aabab. o Ta c´ tu.o.ng u.ng mˆt mˆt gi˜.a c´c vˇn pham ch´ quy v` c´c automat h˜.u han. o ´ oouaa ınh aa u . . . . .c l`, ngˆn ng˜. d u.o.c nhˆn dang bo.i automat h˜.u han nˆu v` chı nˆu ngˆn ng˜. d u.o.c ´ ’´ ˙ ’ . e a ˙e T´ a u o u¯ . a. u o u¯ . . sinh ra bo.i vˇn pham ch´ quy. Du.a v`o nh˜.ng thao luˆn trˆn c´ thˆ’ dˆ d`ng thiˆt ˙e e o e˜a ´ ˙a ’ ˙ ’ ınh a u a e . . . .ng automat h˜.u ˜ ´. ´ ˙` ’a a kˆ hˆ thˆng nhˆn dang chuˆi theo c´ ph´p: Ch´ng ta chı cˆn xˆy du ee o a o ua u u . . . han t`. mˆt vˇn pham ch´ qui. Thˆt vˆy, x´t vˇn pham G = (N, Σ, P, X0 ), trong d ´ .uoa ınh aa ea ¯o . . .. . . N l` ho.p cua X v` n k´ hiˆu khˆng kˆt th´c X , X , . . . , X . Ta ´ a˙˙ ’’ ˙ ’ X0 ≡ S, v` gia su a. 0a ye o e u . 1 2 n d ˇt tˆp c´c trang th´i Q = {q0, q1, . . . , qn, qn+1 } gˆm n + 2 trang th´i sao cho qi tu.o.ng ` ¯a a a a o a .. . . .ng v´.i X , i = 0, 1, . . . , n, v` qa n+1 l` trang th´i cuˆi. Tˆp c´c t´n hiˆu v`o tr`ng v´.i ´ u ´ o a. a o aaı ea u o . . i tˆp c´c k´ hiˆu kˆt th´c trong G. Anh xa chuyˆ’n δ d u.o.c xˆy du.ng du.a trˆn hai quy ´ ˙ ´ aayee u e ¯. a e . . . . . .i mˆi i, j, 0 ≤ i ≤ n, 0 ≤ j ≤ n, tˇc sinh cua G; cu thˆ’ v´ ˙ ´ ˜ ˙ ’ a . eo o 1. Nˆu quy tˇc Xi → aXj thuˆc P th` δ (qi, a) ch´.a qj . ´ ´ e a o ı u . 2. Nˆu quy tˇc Xi → a thuˆc P th` δ (qi, a) ch´.a qn+1 . ´ ´ e a o ı u . Ngu.o.c lai cho mˆt automat h˜.u han, Af = (Q, Σ, δ, q0, F ), ch´ng ta c´ thˆ’ xˆy ˙ o u u o ea .. . . .ng mˆt vˇn pham ch´ quy G = (N, Σ, P, X ), bˇ ng c´ch d ˇt N = Q, k´ hiˆu kho.i ` ˙ ’ du oa ınh a a ¯a ye . . . . . 0 329
d` u X0 tu.o.ng u.ng q0 v` c´c quy tˇc P nhu. sau: ´ ¯ˆ a ´ aa a ´ ´ ı` . 1. Nˆu qj thuˆc δ (qi, a) th` tˆn tai mˆt quy tˇc Xi → aXj thuˆc P. e o o o a o . . . ´ ´ ı` . 2. Nˆu mˆt trang th´i trong F thuˆc δ (qi, a) th` tˆn tai quy tˇc Xi → a trong P. e o a o o a . . . Trong ca hai tru.`.ng ho.p, tˆp c´c k´ hiˆu kˆt th´c Σ l` tr`ng nhau . ´ ˙ ’ o aayee u au . . . V´ du 9.4.6 Automat h˜.u han d oi v´.i vˇn pham ch´ quy cho trong H` 9.14 nhˆn ´ ı. u . ¯ˆ o a ınh ınh a . . .o.c bˇ ng c´ch x´t c´c quy tˇc sinh X → aX , X → bX , X → bX , v` X → c. ` ´ du . a ¯ a ea a a2 0 1 1 1 1 2 .i Q = {q0 , q1, q2, q3}, Σ = {a, b, c}, F = {q3 } v` ´nh Khi d o Af = (Q, Σ, δ, q0, F ), v´ ¯´ o aa - e ¯ˆ ¯ ˙ xa δ (q0, a) = {q1}, δ (q1, b) = {q1, q2}, δ (q2, c) = {q3}. Dˆ’ d` y d u, ta viˆt δ (q0, b) = ˙a ´ ’ e . δ (q0, c) = δ (q1, a) = δ (q1, c) = δ (q2, a) = δ (q2, b) = ∅ dˆ’ chı ra c´c chuyˆ’n d o’i trang ˙’ ˙ ˙. ¯e ˙ a e ¯ˆ th´i n`y khˆng d .o.c d .nh ngh˜ trong automat. aa o ¯u . ¯i ıa Nhˆn dang c´ ph´p du.a v`o vˇn pham cˆy a u a a a a . . . . Tu.o.ng tu. nhu. qu´ tr` nhˆn dang chuˆi, du.´.i d ay ch´ng ta d` cˆp d e n nhˆn dang ˜ ´ a ınh a o o ¯ˆ u ¯ˆ a ¯ˆ e. a . . . . . .o.c d ˇc tru.ng bo.i cˆy. Gia thiˆt rˇ ng d oi tu.o.ng trong anh d a d u.o.c biˆ’u ˙ ˜ ´` ´ ˙a ’ ˙ ’ ˙ ’ c´c mˆu d . ¯a a a ¯u ea ¯ˆ ¯˜ ¯ . e . . diˆn dang cˆy su. dung c´c nguyˆn so. th´ch ho.p nhu. d ˜ d` cˆp trong Phˆn 8.5. ˜ ` a˙. ’ e a e ı ¯a ¯ˆ a e. a . . Vˇn pham cˆy. a a . -. Dinh ngh˜ 9.4.7 Vˇn pham cˆy l` bˆ nˇm ıa a a aoa . . G = (N, Σ, P, r, S ), trong d o ¯´ ´ 1. N l` tˆp c´c k´ hiˆu khˆng kˆt th´c, aa a y e o e u . . ´ 2. Σ l` tˆp c´c k´ hiˆu kˆt th´c, aa a y e e u . . 3. S ⊂ N l` k´ hiˆu kho.i d` u, m` n´i chung c´ thˆ’ l` mˆt cˆy, ˙ ˙ ¯ˆ ’a ay e ao o ea o a . . ´ 4. P l` tˆp c´c quy tˇc sinh dang Ti → Tj , trong d o Ti v` Tj l` c´c cˆy, v` aa a a ¯´ a aa a a . . 5. h`m hang r : Σ → N l` ´nh xa thiˆt lˆp v´.i mˆi k ∈ Σ tu.o.ng u.ng mˆt tˆp con ˜ ´. a aa ea o o ´ oa . . .. . sau: n ∈ r(k ) nˆu tˆn tai cˆy T (x´c d nh trong quy e`.a ´o ˙ ’ r(k ) cua N d inh ngh˜ nhu ¯. ıa a ¯i. .c tiˆp cua n´t k trong cˆy T. ´ ´˙u ’ tˇc sinh) sao cho c´ n n´t con tru e a o u a . 330
Mˆi quan tˆm cua ch´ng ta l` khai triˆ’n vˇn pham cˆy c´ c´c quy tˇc sinh dang ˙ ´ ´ ˙ ’ o a u a ea a oa a . . X k ....................... . . . . . ... . . . . . ... ....... . . .. . ... . .... .... .... . ............... . .... . .... . .. ...... . . .. .... .... .... . . ...... . ....... . .. .... . ........ . ....... .... .... . ....... . ....... .. . . .... ........ .... . . .. ... . . . . ...... . .... ........ .... . . ....... . ....... .. . . .... .... ........ . .. .. . . ··· X1 X2 Xn ´ ´ trong d ´ X1 , X2 , . . . , Xn l` c´c k´ hiˆu khˆng kˆt th´c v` k l` k´ hiˆu kˆt th´c. ¯o aa y e o e u a ay e e u . . V´ du 9.4.8 Bˆ khung cua cˆ u tr´c trong H`nh 9.16(a) d u.o.c tao ra t`. vˇn pham cˆy ’´ ˙a ı. o u ı ¯. . ua a . . .i N = {X , X , X , S } v` Σ = {a, b, c, d, e}, trong d o c´c k´ hiˆu kˆt th´c biˆ’u diˆn ˙ ˜ ´ v´ o a ¯´ a y e e u e e . 1 2 3 c´c nguyˆn so. trong H` 9.16(b). Gia su. c´c m˜i tˆn d .o.c nˆi theo quan hˆ ngon-gˆc ´ ´ ˙˙a ’’ a e ınh u e ¯u . o e.o . v` m˜i tˆn d u.o.c nˆi d e n d .`.ng tr`n tai mˆt vi tr´ tu` y trˆn d ´. C´c quy tˇc sinh ´ ´´ a u e ¯ . o ¯ˆ ¯u o o. o . ı y ´ e ¯o a a . ˙a ’ cua vˇn pham c´ dang o. . S −→ a X1 −→ b X1 −→ c . . . .... . . .. .... . . . . ... .... . . .. . . . . .. ... . . . . .. ... ... . . . . . ... . . ... . . . . ... . . ... . . . .. . . . . . . . . X1 X1 X2 X3 (1) (2) (3) X2 −→ d X2 −→ e X3 −→ e X3 −→ a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X2 X3 (4) (5) (6) (7) Trong tru.`.ng ho.p n`y, h`m hang x´c d .nh bo.i ˙ ’ o a a a ¯i . . r(a) = {0, 1}, r(b) = r(d) = r(e) = {1}, r(c) = {2}. V´.i r`ng buˆc sˆ lˆn thu.c hiˆn c´c qui tˇc sinh 2, 4 v` 6 l` nhu. nhau, ta s˜ c´ cˆ u ´ o o` . ´a ´ oa ea a a a eoa . . tr´c v´.i c´c nh´nh c´ d ˆ d`i bˇ ng nhau. Tu.o.ng tu., nˆu ´p dung c´c qui tˇc sinh 4 ` ´ ´ uoa a o ¯o a a . ea a a . . v` 6 v´.i sˆ lˆn bˇ ng nhau s˜ tao cˆ u tr´c d ˆi x´.ng qua truc du.ng. Dˆy l` nh˜.ng tri -a a u ` o o` ´a a ´ ´ a e. a u ¯o u . ¯´ th´.c bˆ’ sung nhˇ m d ˙ m bao t´nh dung vˆ mˇt ng˜. ngh˜ cua cˆ u tr´c d u.o.c tao ra. ˙ ` ¯a `a ’´ ’ ˙ı ’ ıa ˙ a uo a ¯´ e. u u¯. . Automat cˆy. Trong khi automat h˜.u han duyˆt mˆt chuˆi t`.ng k´ hiˆu mˆt, t`. ˜ a u e o ou ye ou . . . . . .i tai mˆi n´t biˆn (c´c n´t l´ d u.o.c sˇp ´ao ˜u ´ tr´i sang phai, automat cˆy bˇt d` u d` ng th` . ˙ ’ a a a ¯ˆ ¯ˆ o o e a u a¯ . a theo th´. tu. t`. tr´i sang phai) cua cˆy (d .o.c tao bo.i vˇn pham cˆy) v` xu. l´ doc theo ˙ ’ ˙ a ¯u . . ’ ˙a ’ a˙y. ’ u.u a a . .`.ng d i tro. vˆ gˆc. Dˇc biˆt: ¯ ˙ ` o -a ’e´ c´c d o a ¯u e . . 331
....... . ... ... ... . . . . .. ...... ... .. .. .... .. . ..... . . . ... ... . . . . .. . . . . ...... . . . .. .. . . . .. ... .. ... . . ... ... ... . .. ... . ... . ... ... ... . . . . . . ... ... ... ... ... . ... . . . . . ... ... ... . . . . . . ... ... ... ... ... . . . ... . . . ... ... ... . . . ... . . . . . .. . . ... ... ....... . . . .... .... . . .... . . ... ... . . ....... ... ....... . .. .... ... ..... ..... .... ..... . . . .... . . ..... . ... ... .... .... .. . .... . . ...... ... .... ..... .... . . . . ... ... ...... . .... .. ... ... . . ... ... .. .. .... .. ..... ... ... .. ..... .. ... .. .. ...... ... ... .......... ...... .. . .. . .. . . .. .... . .... . .......... .. ...... .... ............. . . ....... .. . ... . .. . ..... . ... .. . ..... . . . . . .. .. . . . . .. .. . . . . . . .. . . . . .. .. . . . . ... . . .. . . . .... . . . ... .. ... . . .. ... .... . .. ..... . .. . .. ... ...... .... . .......... . ... . ... ..... . ... (a) a ................................ b .......... c............. .. . .. e . d............ .. .. .. .. .. .. . . . .. . .. ... ....... . . . .. .. . . .. .. . ... .... . . .. ... .. .. . ... .. .. ... . ............ ... .. ... .... ... ... ... ... .. . ... .. . . (b) H` 9.16: (a) Dˆi tu.o.ng v` (b) c´c nguyˆn so. d u.o.c su. dung d e’ biˆ’u diˆn bˆ khung -o ˙˙ ˜o ´ ¯. ˙ . ’ ınh a a e ¯ˆ e e . . theo vˇn pham cˆy. a a . Dinh ngh˜ 9.4.9 Automat cˆy t`. biˆn vˆ gˆc l` bˆ ba -. a u e `oao e´ ıa . At = (Q, F, {fk | k ∈ Σ}), trong d ´ ¯o 1. Q l` tˆp h˜.u han c´c trang th´i, aa u .a a . . ´ 2. F ⊂ Q l` tˆp c´c trang th´i kˆt th´c, v` aa a ae u a . . 3. fk l` quan hˆ hai ngˆi trˆn Qm × Q, trong d o m l` hang cua k. ˙ ’ a e oe ¯´ a. . Dˆi v´.i vˇn pham cˆy G = (N, Σ, P, r, S ) ch´ng ta xˆy du.ng automat cˆy tu.o.ng -o o a ´ a u a a . . .ng bˇ ng c´ch d at Q = N, F = {S } v` v´.i mˆi k´ hiˆu k ∈ Σ ta d nh ngh˜a quan hˆ ` ˜ u ´ a a ¯ˇ ao oye ¯i ı e . . . . ´ ´u v` chı nˆu tˆn tai quy tˇc sinh (trong G) ´` . fk sao cho (X1 , X2 , . . . , Xm , X ) ∈ fk nˆ a ˙ e o’ e a X k ........................ .. . . . . . . . . . . ... .... .... .... .... . .............. .... . .... . ....... ....... . .... .... ........ . . .. ..... . .. .... . ...... . . ........ .... .... . .. ...... . . .. ... . . . .... . ...... .... . ........ . .. . . ........ ..... . .... .... . . ........ ... .... . .. . . .... .... ........ ....... . . ... .. . ... .. ··· X1 X2 Xm Chˇng han, x´t vˇn pham cˆy G = (N, Σ, P, r, S ) v´.i N = {S, X }, Σ = {a, b, c, d} v` ˙ ’ a ea a o a . . 332
´ c´c quy tˇc sinh a a X −→ a X −→ b X −→ c S −→ d . ... ... . . ... ... . . .. .... . . .. .. . ... . .. . ... .. . . . ... .. . . ... . ... . . .. . .. .. . . . X X X v` h`m hang cho bo.i r(a) = {0}, r(b) = {0}, r(c) = {1} v` r(d) = {2}. Automat cˆy ˙’ aa a a . .o.ng u.ng A = (Q, F, {f | k ∈ Σ}) v´.i Q = {S, X }, F = {S } v` {f | k ∈ Σ} = tu ´ o a f k k {fa , fb , fc , fd } trong d ´ c´c quan hˆ d inh ngh˜a nhu. sau ¯o a e ¯. ı . fa = {(∅, X )}, suy t`. luˆt sinh X −→ a ua . fb = {(∅, X )}, suy t`. luˆt sinh X −→ b ua . . luˆt sinh X −→ c fc = {(X, X )}, suy t` a u. . . . . . . . . . . . . . . . . . . . X fd = {(X, X, S )}, suy t`. luˆt sinh S −→ d ua . . .. .. .. .. . ... ... ... ... ... ... . .. .. ... .. .. .. .. .. ... .. .. .. X X Quan hˆ fa c´ ngh˜ mˆt n´t d u.o.c g´n nh˜n a v` khˆng c´ n´t con (do d o k´ hiˆu e o ıa o u ¯ . a a ao ou ¯´ y e . . . .o.c g´n trang th´i X. f c´ ngh˜ mˆt n´t d u.o.c g´n nh˜n c v` c´ mˆt NULL l` ∅) d u . a a ¯ a co ıa o u ¯ . a a ao o . . . .o.c g´n trang th´i X. Quan hˆ f c´ ngh˜ mˆt n´t d u.o.c n´t con c´ trang th´i X d u . a u o. a ¯ a edo ıa o u ¯ . . . . .o.c g´n trang th´i S. ˜ g´n nh˜n d c´ hai n´t con, mˆi n´t con c´ trang th´i X d u . a a a o u ou o. a ¯ a . X´t cˆy T , chˇng han trong H`nh 9.17(a). Su. dung automat cˆy ch´ng ta s˜ nhˆn ˙ ’ ˙. ’ ea a ı a u ea . . .o.c tao ra bo.i vˇn pham G cho o. trˆn khˆng. Tru.´.c hˆt, automat ´ ˙a ’ ˙e ’ dang cˆy T c´ d u . . a o¯ o oe . . .i c´c n´t biˆn a v` b thˆng qua quan hˆ f v` f . Trong ´ At g´n c´c trang th´i d ˆi v´ a u aa a ¯o o e a o eaab . . .`.ng ho.p n`y, theo c´c quan hˆ d ˜ cho, trang th´i X d u.o.c g´n d ˆi v´.i ca hai n´t l´ ´ ¯ . a ¯o o ˙ ’ tru o a a e ¯a a ua . . . . trong H` 9.17(b). Kˆ tiˆp automat di chuyˆ’n lˆn mˆt m´.c dˆn n´t biˆn, trong ˙ ´´ ´ nhu ınh ee ee o u ¯e u e . tru.`.ng ho.p n`y l` c. Du.a trˆn quan hˆ fc , n´t c s˜ d .o.c g´n trang th´i X nhu. trong o aa e e u e ¯u . a a . . . . .c, ch´ng ta bˇt gˇp n´t d. Hai n´t con cua n´t d H` 9.17(c). Di chuyˆ’n lˆn mˆt m´ ˙ ´. ˙u ’ ınh ee o u u aau u . d ˜ d .o.c g´n trang th´i X nˆn theo quan hˆ fd ta g´n trang th´i S cho n´t d. Do d ¯a ¯u . a a e e a a u . . . l` n´t gˆc v` trang th´i S thuˆc F nˆn automat chˆ p nhˆn (nhˆn dang) cˆy T l` ho.p ´ ´ au o a . a o e a a a a a. . . . . .c l` T d u.o.c sinh bo.i vˇn pham G. H` 9.17(d) minh hoa kˆt qua cuˆi c`ng cua ´ ’´ ˙a ’ ˙ ou ˙ ’ lˆ; t´ a ¯ . eu ınh .e . . .`.ng d i t`. biˆn vˆ gˆc. ¯u e `o e´ d˜y c´c trang th´i trˆn d o aa a e ¯u . 333