RÚT GỌN AUTOMAT HỮU HẠN ĐƠN ĐỊNH (DFA)

Chi tiết

AUTOMAT HỮU HẠN ĐƠN ĐỊNH

KHÁI NIỆM.

Automat đơn định là một automat mà trong đó mỗi di chuyển (move) là được xác định duy nhất bởi cấu hình hiện tại. Sự duy nhất này thể hiện tính đơn định, có nghĩa là ta sẽ biết chắc nó sẽ di chuyển đến đâu, đến trạng thái hay cấu hình nào

Accepter ñôn ñònh vaø ñoà thò chuyeån traïng thaùi

Ñònh nghóa 2.1

-----------------------------------------------------------------------------------------------

Moät accepter höõu haïn ñôn ñònh hay moät dfa ñöôïc ñònh nghóa bôûi boä naêm :

M = ( Q, Σ, δ, q₀ , F )

Trong ñoù :

Q : taäp höõu haïn caùc traïng thaùi noäi (internal states).

Σ : taäp höõu haïn caùc kyù hieäu ñöôïc goïi laø baûng chöõ caùi ñaàu nhaäp

(input alphabet).

δ : Q x Σ à Q laø moät haøm toaøn aùnh goïi laø haøm chuyeån dòch.

q₀ Î Q laø traïng thaùi ban ñaàu.

F Í Q laø taäp traïng thaùi keát thuùc

-------------------------------------------------------------------------------------------

Moät accepter höõu haïn ñôn ñònh hoaït ñoäng döïa theo caùc thöùc sau : Taïi thôøi ñieåm ban ñaàu, noù ñöôïc giaû ñònh ñang ôû trong traïng thaùi baét ñaàu q₀, vôùi cô cheá nhaäp ñang ôû taïi kyù hieäu beân traùi nhaát cuûa chuoãi nhaäp vaøo. Trong moãi laàn di chuyeån cuûa automat, ñaàu ñoïc tieán veà phía phaûi moät kyù hieäu. Nhö vaäy moãi laàn di chuyeån seõ laáy ñi moät kyù hieäu ñaàu nhaäp. Khi gaëp kyù hieäu keát thuùc chuoãi, chuoãi nhaäp ñöôïc chaáp nhaän neáu nhö automat ñang ôû moät trong nhöõng traïng thaùi keát thuùc cuûa noù. Ngöôïc laïi thì chuoãi bò töø choái. Ñaàu ñoïc chæ coù theå di chuyeån töø traùi sang phaûi vaø ñoïc duy nhaát moät kyù hieäu trong moãi böôùc.

Ñeå ñaëc tröng vaø bieåu dieãn cho moät automat höõu haïn moät caùc tröïc quan ta söû duïng ñoà thò chuyeån dòch (transition graphs). Caùc nhaõn treân caùc nuùt laø teân cuûa caùc traïng thaùi, coøn caùc nhaõn treân caùc caïnh laø giaù trò hieän taïi cuûa kyù hieäu nhaäp.

Xem q0 vaø q1 laø caùc traïng thaùi beân trong cuûa moät dfa M naøo ñoù, thì ñoà thò töông öùng vôùi M seõ coù moät nuùt mang nhaõn q0 vaø moät nuùt khaùc mang nhaõn q1. Moät caïnh (q0,q1) ñöôïc ñaùnh nhaõn a bieåu thò cho söï chuyeån dòch δ(q0, a) = q1. Traïng thaùi ban ñaàu seõ ñöôïc xaùc ñònh baèng moät muõi teân ñi ñeán khoâng gaùn nhaõn vaø muõi teân naøy cuõng khoâng xuaát phaùt töø nuùt naøo. Traïng thaùi keát thuùc ñöôïc veõ baèng voøng troøn ñoâi.

Moät caùch hình thöùc hôn, neáu M = ( Q, Σ, δ, q₀ , F ) laø moät accepter höõu haïn ñôn ñònh thì ñoà thò chuyeån dòch töông öùng cuûa noù G_M seõ coù ñuùng |Q| ñænh, moãi ñænh ñöôïc gaùn nhaõn qi khaùc nhau vôùi qi Î Q. Ñoái vôùi moãi quy taéc chuyeån traïng thaùi δ(qi, a) = qj, ñoà thò coù moät caïnh (qi, qj ) ñöôïc gaùn nhaõn a. Ñænh töông öùng vôùi q0 ñöôïc goïi laø nuùt baét ñaàu. Nhöõng nuùt mang nhaõn qf Î F laø caùc ñænh keát thuùc.

Ví duï 2.1

Ñoà thò töông öùng ôû hình 2.1

M = ({q0, q1, q2}, {0,1}, δ, q0, {q1} )

Trong ñoù δ ñöôïc cho bôûi

δ(q0, 0) = q0 , δ(q0, 1) = q1

δ(q1, 0) = q0 , δ(q1, 1) = q2

δ(q2, 0) = q2 , δ(q0, 1) = q1

Dfa naøy chaáp nhaän chuoãi 01. Baét ñaàu taïi traïng thaùi q0, kyù hieäu 0 ñöôïc ñoïc ñaàu tieân. Haõy nhìn vaøo caùc caïnh cuûa ñoà thò, chuùng ta coù theå thaáy raèng automat vaãn ôû traïng thaùi q0, keá tieáp, kyù töï 1 ñöôïc ñoïc vaø automat chuyeån sang traïng thaùi q1. Chuùng ta hieän ñang ôû kyù töï keát thuùc chuoãi vaø cuõng ñang ôû taïi traïng thaùi keát thuùc q1. Do ñoù, chuoãi 01 ñöôïc chaáp nhaän. Dfa naøy khoâng chaáp nhaän chuoãi 00, bôûi vì sau khi ñoïc xong hai kyù töï 0 lieân tieáp noù ôû vaøo traïng thaùi q0 (khoâng phaûi traïng thaùi keát thuùc). Moät caùch töông töï, chuùng ta thaáy raèng automat naøy seõ chaáp nhaän caùc chuoãi 101, 0111, vaø 11001, nhöng laïi khoâng chaáp nhaän chuoãi 100 hay 1100.

Hình 2.1

Ñeå cho tieän lôïi ngöôøi ta ñöa ra khaùi nieäm haøm chuyeån traïng thaùi môû roäng (Extended Transition Function)

δ* : Q x Σ * à Q

ñoái soá thöù hai cuûa δ* laø moät chuoãi, ít khi laø moät kyù hieäu ñôn

Neáu δ(q0, a) = q1

vaø δ(q1, b) = q2,

thì δ*(q0, ab) = q2

Moät caùch hình thöùc, chuùng ta ñònh nghóa δ* ñeä quy nhö sau :

δ*(q, l) = q (2.1)

δ*(q, wa) = δ(δ*(q, w), a) (2.2)

vôùi moïi q Î Q, w Î Σ*, a Î Σ. Ñeå hieåu taïi sao ñieàu naøy laïi ñuùng, chuùng ta haõy aùp duïng nhöõng ñònh nghóa naøy cho ví duï ñôn giaûn ôû treân. Ñaàu tieân, chuùng ta duøng (2.2) ta coù

δ*(q0, ab) = δ(δ*(q0, a), b) (2.3)

nhöng

δ*(q0, a) = δ(δ*(q0, l), a)

= δ(q0, a)

= q1

thay vaøo (2.3) ta ñöôïc :

δ*(q0, ab) = δ(q1, b) = q2

GIẢM SỐ LƯỢNG CÁC TRẠNG THÁI TRONG AUTOMAT TẤT ĐỊNH ( HAY RÚT GỌN DFA)

Baát cöù moät automat taát ñònh naøo ñeàu ñònh nghóa moät moät ngoân ngöõ duy nhaát, nhöng ngöôïc laïi thì khoâng ñuùng.Vôùi moät ngoân ngöõ ñöôïc cho, coù nhieàu automat taát ñònh chaáp nhaän noù. Coù theå coù söï khaùc nhau veà soá löôïng caùc traïng thaùi cuûa nhöõng automat naøy. Vaán ñeà ñaët ra laø giaûm bôùt traïng thaùi cuûa moät automat.

Ví duï 2.14

Hai automat taát ñònh trong hình 2.17(a) vaø 2.17(b) laø töông ñöông, deã thaáy ñieàu naøy, baèng caùch kieåm tra moät vaøi chuoãi nhaäp, treân chuùng. Chuùng ta xem laïi moät soá ñaëc tính roõ raøng laø khoâng caàn thieát trong hình 2.17(a). Traïng thaùi q5 khoâng ñoùng moät vai troø naøo trong automat, bôûi vì noù khoâng bao giôø ñeán ñöôïc töø traïng thaùi ban ñaàu q0. Nhö vaäy coù theå xoùa ñi ( cuøng vôùi taát caû caùc haøm chuyeån dòch lieân quan ñeán noù) maø khoâng laøm aûnh höôûng ñeán ngoân ngöõ ñöôïc chaáp nhaän bôûi automat naøy. Nhöng ngay caû sau khi loaïi boû traïng thaùi q5, automat ñaàu tieân vaãn coøn traïng thaùi thöøa. Traïng thaùi q1, q2 trong automat ñaàu ñöôïc keát noái thaønh moät traïng thaùi q1 trong atomat thöù hai (xem hình).

Ñònh nghóa 2.7

Hai traïng thaùi p vaø q cuûa automat taát ñònh ñöôïc goïi laø khoâng theå phaân bieät ñöôïc neáu:

δ(q, w) Î F suy ra δ(p, w) Î F,

vaø

δ(p, w) Ï F suy ra δ(q, w) Ï F,

vôùi moïi chuoãi w Î Σ*. Neáu toàn taïi chuoãi w Î Σ* sao cho

δ(q, w) Î F vaø δ(p, w) Ï F

hay ngöôïc laïi, thì traïng thaùi p vaø q ñöôïc goïi laø coù theå phaân bieät ñöôïc bôûi chuoãi w.

Roõ raøng hai traïng thaùi hoaëc laø khoâng theå phaân bieät ñöôïc hoaëc laø coù theå phaân bieät ñöôïc. Söï khoâng theå phaân bieät ñöôïc coù nhöõng tính chaát cuûa quan heä töông ñöông. Neáu p vaø q khoâng phaân bieät ñöôïc vaø neáu q vaø r cuõng khoâng phaân bieät ñöôïc, thì p, q, r cuõng khoâng theå phaân bieät ñöôïc.

Moät phöông phaùp giaûm soá traïng thaùi cuûa moät automat taát ñònh laø döïa vaøo vieäc tìm kieám vaø keát hôïp laïi nhöõng traïng thaùi khoâng phaân bieät ñöôïc. Ñaàu tieân chuùng ta moâ taû moät phöông phaùp (thuû tuïc Mark) tìm kieám moät caëp traïng thaùi coù theå phaân bieät ñöôïc.

Thuû tuc: Mark (Ñaùnh daáu)

Loaïi boû taát caû caùc traïng thaùi khoâng theå ñi ñeán ñöôïc. Ñieàu naøy coù theå ñöôïc thöïc hieän baèng caùch ñaùnh soá taát caû nhöõng ñöôøng ñi ñôn treân ñoà thò cuûa automat taát ñònh, baét ñaàu töø traïng thaùi ban ñaàu.

Xem xeùt taát caû caëp traïng thaùi (p,q). Neáu pÎ F vaø q Ï F hoaëc ngöôïc laïi, ñaùnh daáu caëp (p,q) laø coù theå phaân bieät ñöôïc.

Laëp laïi ôû nhöõng böôùc sau cho ñeán khi khoâng coù caëp naøo chöa ñöôïc ñaùnh daáu.

Vôùi taát caû caëp (p,q) vaø taát caû kí töï a Î å, tính δ(p, a) = p_a vaø δ(q, a) = q_a. Neáu caëp (p_a,q_a) ñöôïc ñaùnh daáu laø phaân bieät ñöôïc thì cuõng ñaùnh daáu (p,q) laø coù theå phaân bieät ñöôïc.

Ñònh lyù 2.3:

Thuû tuïc mark, ñöôïc aùp duïng cho automat taát ñònh M = (Q, å, δ , q0, F) keát thuùc vaø xaùc ñònh nhöõng traïng thaùi coù theå phaân bieät ñöôïc.

Thuû tuïc: Reduce

Cho dfa M = (Q, Σ, δ, q0,F), chuùng ta taïo ra moät automat giaûm thieåu traïng thaùi

Duøng thuû tuïc mark ñeå ñaùnh daáu taát caû nhöõng caëp traïng thaùi khoâng theå phaân bieät ñöôïc. Töø ñoù, tìm nhöõng taäp caùc traïng thaùi khoâng phaân bieät ñöôïc, ñoù laø

{ qi, qj. . .,qk}, {ql, qm, . . .,qn}, v . v.

Vôùi moãi taäp { qi, qj,. . .,qk} laø nhöõng traïng thaùi khoâng phaân bieät ñöôïc,

taïo ra moät traïng thaùi ñöôïc gaùn nhaõn ij . . .k cho

3. Vôùi moãi haøm chuyeån dòch cuûa M coù daïng:

δ(q_r, a) = q_p

Tìm nhöõng taäp maø qr vaø qp thuoäc veà noù. Neáu qr Î {qi,qj , . .,qk} vaø

qp Î { ql,qm,. . . ,qn}, haõy theâm vaøo qui luaät

( ij . . .k, a) = lm . . . n

4. Traïng thaùi ban ñaàu cuûa coù nhaõn laø 0.

5. laø taäp taát caû nhöõng traïng thaùi maø nhaõn chöùa i sao cho qi Î F.

Ví duï 2.15

Xem xeùt automat ñöôïc moâ taû trong hình 2.18.

Trong böôùc hai, thuû tuïc mark seõ xaùc ñònh nhöõng caëp phaân bieät ñöôïc

(q0, q4), (q1, q4), (q2, q4) vaø (q3, q4). Qua moät soá laàn laëp ôû böôùc 3, thuû tuïc ñöa ra:

d(q1,1) = q4

vaø d(q0,1) = q3

Vì (q3, q4) laø moät caëp coù theå phaân bieät ñöôïc, caëp (q0, q1) cuõng ñöôïc ñaùnh daáu. Tieáp tuïc nhöõng caëp sau ñöôïc ñaùnh daáu

(q0, q1), (q0, q2), (q0, q3), (q0, q4), (q1, q4), (q2, q4), (q3, q4)

laø coù theå phaân bieät ñöôïc, coøn laïi nhöõng caëp khoâng phaân bieät ñöôïc

(q1, q2),(q1, q3) vaø (q2, q3).

Hình 2.8

Do ñoù,nhöõng traïng thaùi q1, q2, q3 taát caû laø khoâng phaân bieät ñöôïc.

Automat baây giôø goàm ba taäp traïng thaùi vaø taát caû nhöõng traïng thaùi naøy ñöôïc phaân hoaïch vaøo nhöõng taäp {q0},{q1, q2, q3} vaø {q4}. Aùp duïng böôùc 2 vaø 3 cuûa thuû tuïc reduce ta coù automat taát ñònh nhö ôû hình 2.19.

123

0,1

Hình 2.19

CHƯƠNG TRÌNH RÚT GỌN AUTOMAT HỮU HẠN ĐƠN ĐỊNH HAY DFA.

ĐẶC TẢ.

Chương trình cho phép người dùng nhập vào một DFA thông qua giao diện đồ họa, người dùng có thể kiểm tra xem automat nhập vào có thỏa mãn điều kiện là một DFA không, nếu là DFA thì mới có thể thực hiện chức năng chính của chương trình là rút gọn DFA và vẽ ra đồ thị chuyển trạng thái.

$Description: C:\Users\NguyenCuongcs\Desktop\Tieu Luan AutoMat\giao dien.jpg$

Nhập tập trạng thái: cho phép nhập các trạng thái của automat, mỗi trạng thái cách nhau bởi dấu “,”. Tên trạng thái phải bắt đầu bằng một kí tự alphabet và các kí tự chỉ thuộc tập số nguyên và bảng chữ cái.Mặc định trạng thái nhập đầu tiên là trạng thái bắt đầu.
Nhập tập xích ma: cho phép nhập nhãn của chuyển dịch giữa các trạng thái mỗi nhãn cách nhau bởi dấu “,”. Tên nhãn chỉ là một kí tự hoặc số hoặc kí tự alphabet.
Nhập các dẫn xuất hay tập δ: cho phép nhập các dẫn xuất của automat, để là một dfa thì: số dẫn xuất = số trạng thái x số nhãn. Mỗi dẫn xuất cách nhau bới dấu “;”.

Các dẫn xuất được nhập vào theo dạng:

trạng thái vào,nhãn,trạng thái ra;

vd: q0,0,q1 tương đương với δ(q0, 0) = q1

Trạng thái kết thúc: cho phép nhập tên trạng thái kết thúc và phải thuộc tập trạng thái đã nhập ở trên.
Kiểm tra DFA: cho phép thực thi kiểm tra xem automat người dung nhập vào có thỏa mãn điều kiện là một dfa không. Nếu không sẽ hiển thị thông báo cho người dùng và không thể thực hiện chức nằng rút gọn dfa cùng như vẽ dfa.
Vẽ: thực hiện vẽ dfa đã nhập vào.
Rút gọn: cho phép thực thi rút gọn dfa.
Vẽ_rútgọn: thực hiện vẽ dfa đã rút gọn.