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

Trong tất cả các ví dụ trên, ký hiệu * xác định “mọi” biểu thức a1 + a2 + ... + an trong đó các ai là tất cả các ký tự cho phép trong máy tính trừ ký tự xuống dòng (newline). Ta có thể chuyển một biểu thức chính quy r sang DFA chấp nhận mọi r. Chú ý rằng sự hiện diện của ký hiệu * sẽ cho phép ta nhận dạng một thành phần của L(r) bắt đầu từ bất kỳ vị trí nào trong dòng. Để làm được điều này, các ứng dụng phải thực hiện quá trình chuyển đổi từ một biểu thức chính quy sang NFA. Và vì cơ chế hoạt động của NFA khá phức tạp nên thông thường ngay sau đó, NFA lại phải được biến đổi tiếp thành dạng DFA tương đương. Tuy nhiên, sự chuyển đổi từ một biểu thức chính quy sang DFA tốn nhiều thời gian hơn việc sử dụng DFA để kiểm tra các mẫu bằng cách duyệt qua chúng một lần, tuy DFA có thể có số trạng thái là hàm mũ của độ dài biểu thức chính quy.

Thực tế, trong trình soạn thảo văn bản UNIX, biểu thức chính quy với mọi r được chuyển thành một NFA có -dịch chuyển và sau đó NFA này được mô phỏng một cách trực tiếp.

Câu hỏi :

?

Hãy tự liên hệ một số các ứng dụng thực tế khác dùng cơ chế ôtômát hữu hạn ?

Tổng kết chương III: Phần nội dung chương III tập trung nghiên cứu cơ chế hoạt động của các dạng ôtômát hữu hạn, mối tương quan giữa chúng, cũng như sự tương đương của chúng với biểu thức chính quy. Tùy theo các yêu cầu thực tế của ứng dụng, ta có thể chuyển từ dạng phức tạp nhất sang các dạng đơn giản hơn. Có thể tóm tắt sự tương quan giữa các Định lý trong chương này theo sơ đồ sau :

BÀI TẬP CHƯƠNG III

3.1. Mô tả ngôn ngữ được chấp nhận bởi các ôtômát hữu hạn với sơ đồ chuyển được cho như sau :

a)

b)

3.2. Xây dựng các sơ đồ chuyển ôtômát hữu hạn chấp nhận các ngôn ngữ sau trên bộ chữ cái  = {0, 1}

1. Tập các chuỗi kết thúc là 00.
2. Tập các chuỗi có 3 ký hiệu 0 liên tiếp.

c) Tập các chuỗi mà ký hiệu thứ 3 kể từ cận phải của chuỗi là 1.

d) Tập mọi chuỗi mà bất cứ chuỗi con nào có độ dài bằng 5 đều có chứa ít nhất 2 con số 0.

3.3. Tìm các sơ đồ chuyển ôtômát hữu hạn đoán nhận các ngôn ngữ sau :

a) Tập các chuỗi trên {0, 1} có chứa một số chẵn các số 0 và một số lẻ các số 1

b) Tập các chuỗi trên {0, 1} có độ dài chia hết cho 3.

c) Tập các chuỗi trên {0, 1} không chứa 101 như một chuỗi con.

3.4. Xây dựng DFA tương đương với mỗi NFA sau :

a) N1({0,1,2,3},{a,b},1,0,{3}) với 1 b) N2 ({0,1,2,3}, {a,b}, 2,0, {1,3}) với 2

1 a b2 a b

0 {0, 1}{1}0 {1, 3}{1}

1 {2}{2}1 {2}{1, 2}

2 {3}2 {3}{0}

3 {3}{3}3 {0}

c)

d)

3.5. Tìm NFA không có -dịch chuyển nhận dạng cùng ngôn ngữ với các NFA sau :

a)

b)

3.6. Viết biểu thức chính quy và vẽ NFA đoán nhận các ngôn ngữ sau :

1. Tập hợp các chuỗi trên  = {1, 2, 3} sao cho ký hiệu cuối cùng đã có xuất hiện trước đó .
2. Tập hợp các chuỗi trên  = {0, 1} trong đó có một cặp ký tự 0 cách nhau bởi một chuỗi con có độ dài 4i, với i  0 nào đó.

3.7. Viết biểu thức chính quy cho mỗi ngôn ngữ sau trên  = { 0, 1} :

a) Tập hợp các chuỗi trong đó mọi cặp 0 liên tiếp đều xuất hiện trước mọi cặp 1 liên tiếp.

b) Tập hợp các chuỗi chứa nhiều nhất một cặp 0 liên tiếp và nhiều nhất một cặp 1 liên tiếp.

3.8. Mô tả (bằng lời) ngôn ngữ được các biểu thức chính quy sau đặc tả :

1. 0(0 + 1)* 0
2. (0+ 1)*0(0 + 1) (0 + 1)
3. (11+ 0)*(00+ 1)
4. (1+ 01+ 001)*( + 0 + 00)
5. [ 00 + 11 + (01+ 10) (00+ 11)*(01+ 10)]*

3.9. Chứng tỏ các biểu thức chính quy sau ký hiệu cho cùng một ngôn ngữ :

(aa)*,(aa)* + (a),(aa + aaaa)*,(aa)* (aa)*

3.10. Vẽ NFA với -dịch chuyển được cho bởi các biểu thức chính qui sau. Sau đó, hãy chuyển sang DFA tương đương :

1. ( a* + b*)*
2. (( + a) b*)*
3. (a + b)* abb (a + b)*
4. ab + (a + bb) a*b
5. (a + ab + aab)*(+ a+ aa)
6. 10 + (0 + 11)0*1
7. 01 [ (( 10)*+ 111)* + 0]*1

3.11. Hãy tìm các biểu thức chính qui tương ứng với các sơ đồ chuyển trạng thái sau:

a)b)

BÀI TẬP LẬP TRÌNH

3.12. Viết chương trình trong Pascal / C mô phỏng một FA chấp nhận ngôn ngữ được biểu diễn bởi biểu thức chính quy sau :

[ A ... Z, a ... Z ]+ [ A ... Z, a ... Z, 0 ... 9, _ ]* + [ 0 ... 9]+ + op

3.13. Viết chương trình cho ra một FA tương ứng khi đầu vào là một biểu thức chính quy.

3.14. Viết chương trình cho ra DFA khi đầu vào là một NFA.