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

= 0*1((0 + 1)0*1)*

Vậy biểu thức chính quy có dạng :

r = r312 + r313 = 0*1((0 + 1)0*1)*( + (0 ­+ 1)(00)*) + 0(00)*

Một vài ứng dụng của ôtômát hữu hạn

Có nhiều kiểu phần mềm thiết kế nhằm đặc tả sự chuyển đổi tự động từ dạng biểu thức chính quy sang việc cài đặt máy tính một cách hiệu quả tương ứng với ôtômát hữu hạn. Trong phần này, ta sẽ đề cập đến hai ứng dụng trong số chúng.

Bộ phân tích từ vựng

Các ký hiệu từ vựng (token) trong một ngôn ngữ lập trình thì hầu hết không có sự ngọai lệ, được biểu diễn như các tập hợp chính quy. Chẳng hạn, các định danh của ALGOL: các chữ cái viết hoa hoặc thường, theo sau bởi một dãy bất kỳ của chữ cái (letter) hoặc chữ số (digit) với độ dài không giới hạn có thể được biểu diễn như sau :

(letter) (letter + digit)*

trong đó "letter" thay thế cho A + B +...+ Z + a + b +...+ z và "digit" là 0 + 1 +...+ 9.

Một ví dụ khác, các định danh của FORTRAN có độ dài giới hạn là 6 và các chữ cái chỉ cho phép dùng chữ viết hoa hoặc ký hiệu $ được biểu diễn như sau :

(letter) ( + letter + digit)5

với "letter" là $ + A + B + ... + Z .

Trong SNOBOL, các hằng số số học có thể được biểu diễn như sau :

( + ) (digit + ( digit * + ) +  digit+ )

Một số công cụ phát sinh bộ phân tích từ vựng nhận input như một dãy các biểu thức chính quy mô tả các ký hiệu từ vựng và phát sinh một ôtômát hữu hạn đơn giản nhận dạng mọi ký hiệu từ vựng. Thông thường, chúng chuyển đổi biểu thức chính quy thành một NFA với -dịch chuyển và sau đó xây dựng tập hợp con các trạng thái để có thể phát sinh DFA một cách trực tiếp hơn là tìm cách loại bỏ các phép chuyển nhãn . Mỗi trạng thái kết thúc xác định ký hiệu từ vựng cụ thể đã tìm thấy. Hàm chuyển của FA sẽ được mã hóa bằng một trong vài cách nhằm chiếm ít không gian hơn so với bảng hàm chuyển tổ chức dưới dạng mảng hai chiều. Bộ phân tích từ vựng được thiết lập bằng cách phát sinh một chương trình cố định thông dịch các bảng mã, cùng với các bảng minh họa cụ thể sự nhận dạng của FA trên các ký hiệu từ vựng (viết dưới dạng các biểu thức chính quy). Bộ phân tích từ vựng dạng này có thể được dùng như một chương trình con độc lập (module) trong một trình biên dịch ngôn ngữ.

Trình soạn thảo văn bản

Hiển nhiên, các trình soạn thảo văn bản hoặc các chương trình tương tự cho phép thay thế một chuỗi bởi mọi chuỗi kết hợp với một biểu thức chính quy cho trước.

Chẳng hạn, trình soạn thảo văn bản ed trong UNIX cho phép một câu lệnh như sau :

/aba*c/

để tìm sự xuất hiện đầu tiên của chuỗi có dạng như trên. Hay câu lệnh :

s/bbb*/b/

cho phép thay thế các chuỗi có dạng bbb* thành chuỗi có một ký tự b.

Hay trong các câu lệnh của MS-DOS và NC, ví dụ câu lệnh :

Del tmp*.???

sẽ cho phép xóa đi tất cả các file với tên tập tin bắt đầu bằng tmp, sau đó là một chuỗi bắt kỳ và có phần mở rộng là 3 ký tự tùy ý. Dấu * trong trường hợp này ký hiệu cho một chuỗi bất kỳ, còn dấu ? ký hiệu cho một ký tự tùy ý. Đây cũng là một dạng ký hiệu của biểu thức chính quy thay thế cho chuỗi.

Hay chẳng hạn, một ví dụ về xử lý chuỗi khác được áp dụng cho việc tìm kiếm theo mẫu trên các trang Web.