Máy chuyển đổi trạng thái hữu hạn

32 CHƢƠNG 4. MÁY CHUYỂN ĐỔI TRẠNG THÁI HỮU HẠN Chƣơng này trình bày định nghĩa và ứng dụng của máy chuyển đổi trạng thái hữu hạn (Finite State Transducer - FST) trong xử lý ngôn ngữ. 4.1. Giới thiệu 4.1.1. Tổng quan về máy trạng thái hữu hạn (FSM) Máy trạng thái hữu hạn (Finite State Machine - FSM) hay còn gọi là máy tự động trạng thái hữu hạn (Finite State Automaton - FSA) là một dạng mô hình đa trạng thái, gồm 3 thành phần chính: - Các trạng thái - Các cung chuyển trạng thái - Các hành động (Actions) Hình 4.1 Máy trạng thái hữu hạn có 2 trạng thái. 33 Hình 4.1 minh họa một máy trạng thái hữu hạn với 2 trạng thái và các hành động tƣơng ứng. Có 4 loại hành động khác nhau: - Hành động vào (Entry action): đƣợc thực hiện khi vào trạng thái tƣơng ứng. - Hành động thoát (Exit action): đƣợc thực hiện khi rời trạng thái tƣơng ứng. - Hành động nhập (Input action): đƣợc thực hiện theo dữ liệu nhập và trạng thái tƣơng ứng. - Hành động chuyển trạng thái (Transition action): đƣợc thực hiện khi chuyển trạng thái theo cung tƣơng ứng. Một máy trạng thái hữu hạn có thể đƣợc biểu diễn bằng sơ đồ trạng thái. Bảng 5.1 minh họa sơ đồ trạng thái của máy trạng thái hữu hạn trong hình 4.1. Bảng 4.1 Sơ đồ trạng thái của máy trạng thái hữu hạn. Mở cửa Đóng cửa mở_cửa --- Mở đóng_cửa Đóng --- Về mặt ứng dụng, máy trạng thái hữu hạn đóng vai trò quan trọng trong nhiều lĩnh vực nhƣ công nghệ điện tử, ngôn ngữ học, khoa học máy tính, triết học, sinh học, toán học, logic học… Trong khoa học máy tính, máy trạng thái hữu hạn đƣợc sử dụng rộng rãi trong việc mô hình hóa hoạt động của phần mềm, thiết kế hệ thống phần cứng, trình biên dịch, công nghệ mạng, xử lý ngôn ngữ tự nhiên … Về mặt phân loại, máy trạng thái hữu hạn gồm 2 nhóm chính: - Máy trạng thái hữu hạn chấp nhận (Acceptor Finite State Machine – A-FSM) 34 - Máy chuyển đổi trạng thái hữu hạn (Finite State Transducer – FST) 4.1.2. Máy trạng thái hữu hạn chấp nhận (A-FSM) và Máy chuyển đổi trạng thái hữu hạn (FST) Máy trạng thái hữu hạn chấp nhận (A-FSM) là một dạng máy chuyển đổi trạng thái hữu hạn cho kết xuất nhị phân (yes/no) để xác định việc một chuỗi nhập có đƣợc chấp nhận bởi máy trạng thái hữu hạn chấp nhận hay không. Một trạng thái của máy trạng thái hữu hạn chấp nhận sẽ có 2 dạng quyết định là chấp nhận hay bác bỏ. Khi tất cả các tín hiệu nhập đã đƣợc duyệt, nếu trạng thái cuối cùng chấp nhận thì chuỗi tín hiệu đó xem nhƣ là hợp lệ, ngƣợc lại thì chuỗi tín hiệu sẽ bị bác bỏ bởi máy trạng thái hữu hạn chấp nhận. Đối với dạng Máy trạng thái hữu hạn chấp nhận, tín hiệu nhập là chuỗi các ký tự, tín hiệu xuất là nhị phân (yes/no); hành động (action) không áp dụng trong mô hình này. Hình 4.2 minh họa một Máy trạng thái hữu hạn chấp nhận duyệt chính tả cho từ “công”. Nếu từ đƣợc nhập đạt đƣợc đến trạng thái 7 thì xem nhƣ hợp lệ, ngƣợc lại là sai chính tả. 35 Hình 4.2 Máy trạng thái hữu hạn chấp nhận (A-FST) duyệt chính tả cho từ “công” Thông thƣờng, Máy trạng thái hữu hạn chấp nhận đƣợc dùng để duyệt cú pháp văn phạm cho các dạng ngôn ngữ hình thức, với trạng thái khởi đầu đƣợc ký hiệu là một vòng tròn có mũi tên khống trỏ vào, và trạng thái đích đƣợc ký hiệu là một vòng tròn viền đôi. Hình 4.3 minh họa một Máy trạng thái hữu hạn chấp nhận duyệt chuỗi nhị phân xem số lƣợng số 0 là chẵn hay lẻ. Hình 4.3 Máy trạng thái hữu hạn chấp nhận duyệt chuỗi nhị phân có số lƣợng số 0 là chẵn Một dạng khác của máy trạng thái hữu hạn là máy chuyển đổi trạng thái hữu hạn (Finite State Transducer - FST). Không giống nhƣ máy chuyển đổi trạng thái hữu hạn chấp nhận (A-FST) chỉ phát sinh kết xuất 1 Bắt đầu 2 Có c c 3 Có ô ô 4 Có n n 6 Lỗi g Không có c Không có ô Không có n Không có g 5 Có g 7 Thành công 36 nhị phân, máy chuyển đổi trạng thái hữu hạn phát sinh kết xuất tùy theo tín hiệu nhập và các hành động (action) tƣơng ứng trên trạng thái đi qua. Có rất nhiều dạng máy chuyển đổi trạng thái hữu hạn khác nhau, phần tiếp theo sẽ trình bày một cách hình thức hơn về máy chuyển đổi trạng thái hữu hạn và một dạng đặc biệt của nó là máy chuyển đổi trạng thái hữu hạn có trọng số (Weighted Finite State Transducer – WFST). 4.1.3. Máy chuyển đổi trạng thái hữu hạn có trọng số (WFST) Máy chuyển đổi trạng thái hữu hạn có trọng số (Weighted Finite State Transducer - WFST) hày còn gọi là máy chuyển đổi chuỗi sang trọng số tuần tự (subsequential string-to-weight transducer) là một dạng của máy chuyển đổi trạng thái hữu hạn với tín hiệu nhập là các chuỗi và kết xuất là các trọng số. Dạng mô hình này đƣợc sử dụng trong nhiều lĩnh vực nhƣ xử lý ngôn ngữ tự nhiên, xử lý tiếng nói, tổng hợp tiếng nói… Hình 4.4 thể hiện vị trí của máy chuyển đổi trạng thái hữu hạn có trọng số (WFST) trong họ máy trạng thái hữu hạn của nó. Các phần tiếp theo sẽ trình bày về định nghĩa hình thức của máy chuyển đổi trạng thái hữu hạn có trọng số cũng nhƣ các thuật toán phổ biến áp dụng trên nó. 37 Hình 4.4 Các dạng máy trạng thái hữu hạn. 4.2. Các định nghĩa 4.2.1. Máy chuyển đổi chuỗi sang trọng số Một máy chuyển đổi chuỗi sang trọng số đƣợc định nghĩa là T = {Q, ∑, I, F, E, λ, ρ}, trong đó: - Q: tập hữu hạn các trạng thái - ∑: các ký tự nhập. - QI : tập các trạng thái khởi đầu - QF : tập các trạng thái kết thúc - QRQE : tập các cung chuyển trạng thái - λ: hàm trọng số khởi đầu, ánh xạ từ I sang R+ - ρ: hàm trọng số kết, ánh xạ từ F sang R+ Ngoài ra, ta còn có thể định hàm chuyển trạng thái δ, ánh xạ từ Q x ∑ sang 2 Q nhƣ sau: FSM A-FSM FST WFST … 38 EqxaqRxqaqQaq )',,,(:|'),(,),( và một hàm kết xuất σ, ánh xạ từ E sang R+ nhƣ sau: xtEqxapt )(,),,,( Đƣờng đi π trong T từ q Q sang q‟ Q đƣợc định nghĩa là một tập các cung chuyển trạng thái từ q đến q‟: ),(,1,0)),,,,(),...,,,,(( 11111000 iiimmmm aqqmiqxaqqxaq Từ đây, ta có thể mở rộng định nghĩa của σ cho các đƣờng đi nhƣ sau: 110 ...)( mxxx Vớ ký hiệu w qq ' là một tập các đƣờng đi từ q đến q‟ đƣợc gán nhãn theo chuỗi nhập w, ta sẽ mở rộng định nghĩa δ sang Q x ∑* và sang 2 Q x ∑* nhƣ sau: ',in path :'),(,),( * qqTqwqQwq w  Rq wqwRwQR ),(),(,, * Với bộ (q,w,q‟) Q x ∑ x Q mà tồn tại đƣờng đi từ q đến q‟ gán nhãn theo w, ta định nghĩa θ(q,w,q‟) là kết xuất tối tiểu của tất cả các con đƣờng từ q đến q‟ theo w: )(min)',,( 'qq w qwq Đƣờng đi trọn vẹn trong T là một đƣờng đi từ trạng thái khởi đầu đến trạng thái đích. Chuỗi w ∑* đƣợc chấp nhận bởi T nếu và chỉ nếu tồn tại một đƣờng đi trọn vẹn đƣợc gán nhãn theo w, kết xuất ƣơng ứng sẽ là: ))(),,()((min ),(:)( ffwii wifFIif 39 Một máy chuyển đổi T đƣợc gọi là đầy đủ nếu tất cả các trạng thái của T đều thuộc về một đƣờng đi trọng vẹn nào đó. Các máy chuyển đổi chuỗi sang trọng số tƣơng đƣơng với các hàm ánh xạ từ ∑* sang R+, ta gọi các hàm này là các chuỗi lũy thừa hình thức. Một máy chuyển đổi chuỗi sang trọng số đƣợc gọi là không mờ nếu với mọi chuỗi w, có tối đa một đƣờng đi trọn vẹn gán nhãn theo w. Một dạng đặc biệt của máy chuyển đổi chuỗi sang trọng số là máy chuyển đổi chuỗi sang trọng số tuần tự, hay còn gọi là máy chuyển đổi trạng thái hữu hạn có trọng số (WFST). 4.2.2. Máy chuyển đổi trạng thái hữu hạn có trọng số (WFST) Một mô hình máy chuyển đổi trạng thái hữu hạn có trọng số đƣợc định nghĩa là τ = (Q, i, F, ∑, δ, σ, λ, ρ) với: - Q là tập các trạng thái - i Q là các trạng thái khởi đầu - QF là tập các trạng thái đích - ∑: các ký tự nhập - δ: hàm chuyển trạng thái, ánh xạ từ Q x ∑ sang Q, δ có thể đƣợc mở rộng theo chuỗi để ánh xạ từ Q x ∑* sang Q. - σ: hàm kết xuất, ánh xạ từ Q x ∑ sang R+, σ cũng có thể đƣợc mở rộng sang trƣờng hợp Q x ∑* - λ R+ là các trọng số khởi đầu - ρ là hàm trọng số đích, ánh xạ từ F sang R+ Chuỗi w ∑* đƣợc chấp nhận bởi máy chuyển đổi trạng thái hữu hạn có trọng số T nếu tồn tại f F sao cho δ(i, w) = f, và kết xuất tƣơng ứng của w là: λ + σ(i, w) + ρ(f). 40 Hai trạng thái q và q‟ của một máy chuyển đổi chuỗi sang trọng số T, không nhất thiết bán tuần tự, đƣợc gọi là song đôi nếu: )',,'(),,()),'('),,(),,(}',({,)(),( 2* qvqqvqvqqvqquIqqvu T có tính chất song đôi nếu mọi cặp trạng thái (q, q‟) bất kỳ đều là song đôi. 4.3. Thuật toán Determinization của máy chuyển đổi trạng thái hữu hạn có trọng số Phần này trình bày thuật toán xây dựng một máy chuyển đổi bán tuần tự τ2 = (Q2, i2, F2, ∑, δ2, σ2, λ2, ρ2) tƣơng đƣơng với một máy chuyển đổi bất bán tuần tự τ1 = (Q1, i1, F1, ∑, δ1, σ1, λ1, ρ1) cho trƣớc. Hình 4.5 minh họa các bƣớc của thuật toán Determinization [8]. 41 1 1 1 2 1 2 2 2 1 2 2 1 2 2 2 1 2 2 2 2 1 ,( , ) Determinization( , ) 1 F 2 ( ) 3 i ( , ( ) 4 Q i 5 while Q 6 do q [ ] 7 if ( (q,x) such that q F ) 8 then F { } 9 (q ) ( ) 10 fo i I i I q F q x q i i i head Q q F Q x q 2 1 1 1 2 12 2 2 2 1 ( , ) ( , ) ( , , ( ), ( )) 1 2 2 2 2 1 (q,x,t) (q , ), ( ) '' ( , ) 2 2 r each a such that (q , ) 11 do ( , ) ( ) 12 ( , ) ', ( , ) ( ) 13 if ( ( , ) is new sta q x q a t q a t n t E a n t qq v q a a q a x t q a q q a x t q a 2 2 te) 14 then ENQUEUE(Q, ( , )) 15 DEQUEUE(Q) q a Hình 4.5 Thuật toán Determinization Trọng khởi đầu λ2 của τ2 sẽ là giá trị nhỏ nhất trong số các trọng số khởi đầu của τ1 (dòng 2). Trạng thái khởi đầu i2 là tập con từ các cặp (i,x) với i là trạng thái khởi đầu của τ1 và x = λ1(i) - λ2 (dòng 3). Thuật toán sử dụng một hàng đợi Q đề lƣu lại các tập con q2. Ban đầu, Q chỉ chứa tập con i2. q2 là trạng thái đích của τ2 nếu và chỉ nếu q2 chứa ít nhất một cặp (q, x) với q là trạng thái đích của τ1 (dòng 7-8). Kết xuất cuối cùng sẽ là kết xuất nhỏ nhất của các trạng thái đích trong q2 cộng với trọng tƣơng ứng (dòng 9). 42 Đối với mỗi nhãn nhập a mà có tồn tại ít nhất một trạng thái q của tập q2 liên kết với cung xuất có chứa a, ta xây dựng một cung chuyển trạng thái từ q2 với nhãn nhập a (dòng 10-14). Kết xuất σ2 (q2, a) của cung chuyển trạng thái này là kết xuất nhỏ nhất của tất cả các cung rời trạng thái trong q2 mà mang nhãn a, cộng với trọng số tƣơng ứng của nó. Thành phần δ2(q2, a) là tập con của các bộ (q‟, x‟) với q‟ là một trạng thái của τ1 có thể đạt đến bằng cung mang nhãn a, và x‟ là trọng tƣơng ứng (dòng 12). δ2(q2, a) sẽ đƣợc đặt vào hàng đợi Q chỉ khi nào nó là một tập con mới. Với ký hiệu n1(t) là trạng thái đến của cung t E1, các thành phần Г(q2, a), γ(q2, a) và v(q2, a) của thuật toán đƣợc định nghĩa nhƣ sau: 2 2 1 1 1 2 2 1 1 1 1 2 2 1 1 ( , ) ( , ) : ( , , ( ), ( )) ( , ) ( , , ) : ( , , ( ), ( )) ( , ) ' : ( , ) , ( , , ( ), ') q a q x q t q a t n t E q a q x t q E t q a t n t E q a q q x q t q a t q E Hình 4.7 minh họa kết quả của việc áp dụng thuật toán Determinization lên máy chuyển đổi trong hình 4.6. Hình 4.6 Máy chuyển đổi μ1 đại diện cho chuỗi lũy thừa định nghĩa trên {R+ U{∞}, min, +} 49 tính tƣơng đƣơng giữa 2 máy chuyển đổi trạng thái hữu hạn có trọng số này không ? Một thuật toán xét tính tƣơng đƣơng giữa 2 máy chuyển đổi trạng thái hữu hạn có trọng số là dựa trên phƣơng pháp của Aho, Hopcroft, và Ullman (1974). Độ phức tạp của thuật toán này cũng ở mức tƣơng đƣơng với thuật toán Minimization [8]. 4.7. Thuật toán Compose Thuật toán này kết hợp hai máy chuyển đổi trạng thái hữu hạn, ký hiệu AoB, trong đó nhãn đầu ra (output label) của máy chuyển đổi trạng thái hữu hạn A và nhãn đầu vào (input label) của máy chuyển đổi trạng thái hữu hạn B phải đƣợc sắp xếp trƣớc. Nếu máy chuyển đổi trạng thái hữu hạn A có cung (transition) x:i/w1 và máy chuyển đổi trạng thái hữu hạn B có cung i:y/w2 thì máy chuyển đổi trạng thái hữu hạn kết quả có cung x:y/w3 với w3=w1+w2 [7, 8] Một ví dụ: Hình 4.11 Máy chuyển đổi trạng thái hữu hạn A 0 1/0 2/2.5 a:q/1 a:r/2.5 c:s/1 43 Hình 4.7 Máy chuyển đổi μ2 – kết quả của việc áp dụng thuật toán Determinization lên μ1. Thuật toán Determinization đã đƣợc chứng minh là sẽ tạo ra một máy chuyển đổi tƣơng đƣơng với máy chuyển đổi nhập. Tuy nhiên, độ phức tạp tính toán của thuật toán này ở mức lũy thừa. Chỉ trong một số ít trƣờng hợp, thuật toán có thể chạy tƣơng đối nhanh. Nhƣng nếu xét về hoạt động duyệt, WFST có độ phức tạp tính toán là tuyến tính theo chiều dài chuỗi nhập. Chính vì vậy, việc áp dụng thuật toán Determinization để tăng tốc hoạt động duyệt cũng là thỏa đáng. Không phải máy chuyển đổi nào cũng có thể áp dụng đƣợc thuật toán Determinization [8]. Thuật toán này chỉ áp dụng đƣợc trên các máy chuyển đổi khả quyết. Phần tiếp theo trình bày về máy chuyển đổi khả quyết và các đặc tính của nó. 4.4. Máy chuyển đổi khả quyết (Determinizable Transducers) Có một số máy chuyển đổi mà khi áp dụng thuật toán Determinization, thuật toán sẽ không có điểm dừng, và phát sinh vô số tập con. Ta định nghĩa máy chuyển đổi khả quyết là các máy chuyển đổi làm dừng thuật toán Determinization [8]. 44 Định lý: Một máy chuyển đổi chuỗi sang trọng số τ1 = (Q1, ∑, I1, F1, E1, λ1, ρ1) là khả quyết nếu nó có tính chất song đôi (nhƣ đã trình bày trong phần định nghĩa). Ngoài ra, có một số máy chuyển đổi không có tính chất song đôi nhƣng vẫn khả quyết. Để xác định các dạng máy chuyển đổi này, cần có những điều kiện phức tạp, tuy nhiên trong trƣờng hợp của các máy chuyển đổi đầy đủ- không mờ (đã nêu ở phần định nghĩa), điều kiện khả quyết của nó cũng là tính chất song đôi. Phần tiếp theo trình bày thuật toán xét tính khả quyết của một máy chuyển đổi đầy đủ-không mờ. 4.5. Xét tính khả quyết (Test of Determinizability) Nhƣ đã trình bày trong phần 4.3.4, một máy chuyển đổi đầy đủ-không mờ là khả quyết nếu nó có tính chất song đôi. Một máy chuyển đổi chuỗi sang trọng số đầy đủ-không mờ τ1 = (Q1, ∑, I1, F1, E1, λ1, ρ1) có tính chất song đôi nếu và chỉ nếu: * 2 2 1 1 1 1 1 1 ( , ) ( ) ,| | 2 | | 1, ({ , '} ( , ), ( , ), ' ( ', )) ( , , ) ( ', , ') u v uv Q q q I u q q v q q v q v q q v q Thuật toán xét tính chất song đôi của máy chuyển đổi τ1 gồm các bƣớc sau: 1) Tính bao đóng của I: T(I) 2) Xác định các cặp trạng thái (q1, q2) của T(I) với q1 ≠ q2 3) Với mỗi cặp (q1, q2), tính bao đóng của (q1, q2, 0) trong A. Nếu bao đóng này chứa (q1, q2, c) với c ≠ 0 thì τ1 không có tính chất song đôi. trong đó, c là một số thực thuộc tập K định nghĩa bên dƣới, A = {Q, I, F, E} là một máy trạng thái hữu hạn đƣợc tạo thành từ kết quả của phép tích chéo giữa τ1 và chính nó. Các thành phần của A gồm: - Gọi K là một tập hữu hạn các số thực, cho bởi biểu thức sau: 45 ' 2 ' 2 1 1 1 ( ( ) ( )) :1 2 | | 1, ( , ) k i i i i i K t t k Q i k t t E - Q = Q1 x Q1 x K = tập các trạng thái của A - I = I1 x I1 x {0} = tập các trạng thái khởi đầu của A - F = F1 x F1 x K = tập các trạng thái đích của A - E = tập các cung chuyển trạng thái: 1 2 1 2 1 2 1 1 2 1 (( , , ), , ( ' , ' , ')) : ( , , , ) , ( ' , , ', ' ) , ' ' E q q c a q q c Q Q q a x q E q a x q E c c x x Thuật toán xét tính chất song đôi của một máy chuyển đổi có độ phức tạp tính toán theo thời gian đa thức. Với thuật toán này, ta có thể xét tính khả quyết của một máy chuyển đổi đầy đủ-không mờ. Tuy nhiên, trong nhiều trƣờng hợp trên thực tế, các máy chuyển đổi cần xét tính khả quyết lại là máy chuyển đổi mờ [8]. Giải pháp cho vấn đề này là xây dựng máy chuyển đổi không mờ từ máy chuyển đổi mờ đã cho theo phƣơng pháp của Eilenberg (1974-1976) với độ phức tạp tính toán là lũy thừa trong trƣờng hợp xấu nhất. Nhƣ vậy, độ phức tạp của thuật toán xét tính khả quyết cũng là lũy thừa trong trƣờng hợp xấu nhất. 4.6. Thuật toán Minimization Phần này trình bày thuật toán xác định máy chuyển đổi trạng thái hữu hạn có trọng số tối tiểu của một chuỗi lũy thừa S cho trƣớc. Với mọi chuỗi lũy thừa S, ta định nghĩa quan hệ RS trên ∑* nhƣ sau: 1 * s -1 1 -1 1 / supp(S) ( , ) , R v k R, (u supp( ) supp(S)) and ( u ) u u v u S v S v S k Đối với một chuỗi lũy thừa S bất kỳ, luôn tồn tại một máy chuyển đổi trạng thái hữu hạn có trọng số tối tiểu để tính S, số trạng thái của máy chuyển 46 đổi trạng thái hữu hạn có trọng số này bằng với số chỉ mục của RS. Trƣớc khi trình bày thuật toán xác định máy chuyển đổi trạng thái hữu hạn có trọng số tối tiểu từ một máy chuyển đổi trạng thái hữu hạn có trọng số cho trƣớc, trƣớc hết ta định nghĩa thao tác pushing. Cho trƣớc một máy chuyển đổi trạng thái hữu hạn có trọng số T = (Q, i, F, ∑, δ, σ, λ, ρ), kết quả của thao tác pushing trên T là máy chuyển đổi trạng thái hữu hạn có trọng số T‟ = (Q, i, F, ∑, δ, σ‟, λ‟, ρ‟). Điểm khác biệt giữa T và T‟ nằm ở trọng kết xuất nhƣ sau: ' ( ); ( , ) , '( , ) ( , ) ( ( , )) ( ); , '( ) 0 d i q a Q q a q a d q a d q q Q q trong đó, d(q) đƣợc định nghĩa cho mỗi trạng thái q Q: ( , ) ( ) ( ( , ) ( ( , )))min q w F d q q w q w với định nghĩa này của d, ta có: * : ( , ) , ( ) ( , ) ( ( , ), ) ( ( ( , ), ))w q aw F d q q a q a w q a w điều này dẫn đến: ( ) ( , ) ( ( , ))d q q a d q a Do đó, ta đƣợc: ( , ) , '( , ) 0q a Q q a Chính vì vậy, ta luôn có T‟ (có đƣợc từ phép pushing) là tƣơng đƣơng với T. Thuật toán tìm máy chuyển đổi trạng thái hữu hạn có trọng số tối tiểu: cho trƣớc T = (Q, i, F, ∑, δ, σ, λ, ρ), nếu áp dụng lên T lần lƣợt 2 phép biến đổi sau: 1) pushing 2) automata minimization 47 ta sẽ đƣợc một máy chuyển đổi trạng thái hữu hạn có trọng số kết quả T‟. T‟ này chính là máy chuyển đổi trạng thái hữu hạn có trọng số tối tiểu tƣơng đƣơng với T. Thông thƣờng, có nhiều máy chuyển đổi trạng thái hữu hạn có trọng số tối tiểu tƣơng đƣơng với một máy chuyển đổi trạng thái hữu hạn có trọng số cho trƣớc. Tuy nhiên, các máy chuyển đổi trạng thái hữu hạn có trọng số tối tiểu này có cùng một cấu trúc, chúng chỉ khác nhau về nhãn xuất và cách phân phối của các trọng xuất. Độ phức tạp của thuật toán Minimization xác định máy chuyển đổi trạng thái hữu hạn có trọng số tối tiểu trong trƣờng hợp tổng quát là: O(|E|log|Q|) Hình 4.8, 4.9 và 4.10 minh họa kết quả từng bƣớc của thuật toán Minimization. Hình 4.8 minh họa máy chuyển đổi trạng thái hữu hạn có trọng số β1. máy chuyển đổi trạng thái hữu hạn có trọng số γ1 trong hình 4.9 là kết quả của thao tác pushing trên β1. Và cuối cùng, δ1 trong hình 4.10 là kết quả cuối cùng của thuật toán Minimization – máy chuyển đổi trạng thái hữu hạn có trọng số tối tiểu tƣơng đƣơng với β1 ban đầu. Hình 4.8 Máy chuyển đổi trạng thái hữu hạn có trọng số β1. 48 Hình 4.9 Máy chuyển đổi trạng thái hữu hạn có trọng số γ1 có đƣợc từ việc pushing β1. Hình 4.10 Máy chuyển đổi trạng thái hữu hạn có trọng số tối tiểu δ1 có đƣợc từ việc áp dụng bƣớc automata minimization lên γ1. Máy chuyển đổi trạng thái hữu hạn có trọng số kết quả T‟ của thuật toán Minimization sẽ có số trạng thái ít nhất và tƣơng đƣơng với máy chuyển đổi trạng thái hữu hạn có trọng số ban đầu T. Một câu hỏi đặt ra là có một máy chuyển đổi trạng thái hữu hạn có trọng số nào cũng tƣơng đƣơng với T nhƣng có số cung chuyển trạng thái ít nhất hay không ? Hệ quả đã đƣợc chứng minh sau đây trả lời cho câu hỏi này. Hệ quả: một máy chuyển đổi trạng thái hữu hạn có trọng số tối tiểu thì cũng có số lƣợng cung chuyển trạng thái là ít nhất so với các máy chuyển đổi trạng thái hữu hạn có trọng số tƣơng đƣơng không tối tiểu. Một vấn đề khác nữa đƣợc đặt ra là: nếu cho trƣớc 2 máy chuyển đổi trạng thái hữu hạn có trọng số bất kỳ, liệu có một thuật toán nào giúp cho việc xét 50 Hình 4.12 Máy chuyển đổi trạng thái hữu hạn B Hình 4.13 Kết quả của thuật toán compose C=AoB 0 2/2 q:f/1 r:h/3 s:j/1.5 1 s:g/2.5 0 3/2 2/4.5 a:f/2 a:h/5.5 c:j/2.5 1 c:g/3.5