0.2 Ôtômat hữu hạn và biểu thức chính quy  (Page 3/16)

Trong một lần chuyển, DFA đang ở trạng thái q đọc ký hiệu nhập a trên băng, chuyển sang trạng thái được xác định bởi hàm chuyển (q, a), rồi dịch đầu đọc sang phải một ký tự. Nếu (q, a) chuyển đến một trong những trạng thái kết thúc thì DFA chấp nhận chuỗi được viết trên băng input phía trước đầu đọc, nhưng không bao gồm ký tự tại vị trí đầu đọc vừa dịch chuyển đến. Trong trường hợp đầu đọc đã dịch đến cuối chuỗi trên băng, thì DFA mới chấp nhận toàn bộ chuỗi trên băng.

Hàm chuyển trạng thái mở rộng

Để có thể mô tả một cách hình thức hoạt động của một DFA trên chuỗi, ta mở rộng hàm chuyển  để áp dụng đối với một trạng thái trên chuỗi hơn là một trạng thái trên từng ký hiệu. Ta định nghĩa hàm chuyển  như một ánh xạ từ Q  *  Q với ý nghĩa (q, w) là trạng thái DFA chuyển đến từ trạng thái q trên chuỗi w. Một cách hình thức, ta định nghĩa :

1. d (q, ) = q
2.  (q, wa) = ( (q, w), a), với mọi chuỗi w và ký hiệu nhập a.

Một số quy ước về ký hiệu :

• Q là tập các trạng thái. Ký hiệu q và p (có hoặc không có chỉ số) là các trạng thái, q0 là trạng thái bắt đầu.
•  là bộ chữ cái nhập. Ký hiệu a, b (có hoặc không có chỉ số) và các chữ số là các ký hiệu nhập.
•  là hàm chuyển.
• F là tập các trạng thái kết thúc.
• w, x, y và z (có hoặc không có chỉ số) là các chuỗi ký hiệu nhập.

Ngôn ngữ được chấp nhận bởi DFA

Một chuỗi w được chấp nhập bởi ôtômát hữu hạn M (Q, , , q0, F) nếu (q0, w) = p với p  F. Ngôn ngữ được chấp nhận bởi M, ký hiệu L(M) là tập hợp:

L(M) = { w   (q0, w)  F }

Thí dụ 3.2 : Xét sơ đồ chuyển ở hình 3.1. Theo khái niệm hình thức, ta có DFA được xác định bởi M (Q, , , q0, F) với Q = {q0, q1, q2, q3},  = {0, 1}, F = {q0} và hàm chuyển  như sau:

Giả sử chuỗi w = 110101 được nhập vào M.

Ta có (q0, 1) = q1 và (q1, 1) = q0 ,vậy (q0, 11) = ((q0,1),1) = (q1, 1) = q0.

Tiếp tục (q0, 0) = q2, vậy (q0, 110) = ((q0, 11), 0) = q2.

Tiếp tục ta có (q0, 1101) = q3, (q0, 11010) = q1

Và cuối cùng (q0, 110101) = q0  F.

(Hay d(q0, 110101) = d(q1, 10101) = d(q0, 0101) = d(q2, 101) = d(q3, 01) = d(q1, 1) = q0  F)

Vậy 110101 thuộc L(M). Ta có thể chứng minh rằng L(M) là tập mọi chuỗi có số chẵn số 0 và số chẵn số 1.

Theo mô tả DFA như trên, ta thấy cũng có thể dùng bảng hàm chuyển (transition table) để mô tả các phép chuyển trạng thái của một ôtômát hữu hạn. Trong bảng hàm chuyển, hàng chứa các trạng thái thuộc tập trạng thái của ôtômát và cột là các ký hiệu thuộc bộ chữ cái nhập. Bảng hàm chuyển gợi ý cho chúng ta một cấu trúc dữ liệu để mô tả cho một ôtômát hữu hạn, đồng thời cũng cho thấy có thể dễ dàng mô phỏng hoạt động của DFA thông qua một chương trình máy tính, chẳng hạn dùng cấu trúc vòng lặp.

Giải thuật mô phỏng hoạt động của một DFA

. Input : Chuỗi nhập x kết thúc bởi $. Output : Câu trả lời "YES" nếu DFA chấp nhận chuỗi x và "NO" nếu ngược lại.. Giải thuật :q := q0 ;c := nextchar ; { c là ký hiệu nhập được đọc tiếp theo }While c<>$ dobeginq := d(q, c);c := nextchar ;endIf q in F then write ("YES") else write("NO");