Tham khảo tài liệu 'toán rời rạc ứng dụng trong tin học part 9', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 328 TOĂN RỜI RẬCỮNG DỤNG TRONG TIN HỌG Hàm chuyển ỏ cho dưới dạng bảng chuyển sau Trạng thái Ký hiệu vào a b qi 0 0 q2 4i q3 13 0 q4 q4 q4 q4 Ta có L N L M hay N tương ứng với M. 2. NGÔN NGỮ CHÍNH QUY VÀ Biểu THỬC CHÍNH QUY . Ngôn ngữ chính quy Giả sử z là bảng chữ hữu hạn không rỗng s ỉà tập tất cả xác xâu kể cả xâu rỗng được xây dựng trên s. Như đã định nghĩa trước đây thì - s AI. Tập con E C x được gọi là một ngón ngữ trèn bảng . Trên tập tất cả các ngôn ngữ ta có thể định nghĩa các phép toán hợp giao phần bù nhân và lặp các ngôn ngữ. Trong các phép toán trên ta dặc biệt chú ý ba phép toán sau đây a Phép hợp Cho hai ngôn ngữ E . E2 trên tập L ta định nghĩa phép hợp E u E2 íi 1 e E hoặc e E2ị. b Phép nhân Cho hai ngôn ngữ E E2 trên E phép nhân E với E2 là E .E2 ap ae E p eE2 . c Phép lặp Với ngôn ngữ E trên z ta định nghĩa phép lặp của E là EMu E2 u E3ư . jEn ởdây En n lần Giả sử s alt a2 . an ngôn ngữ 0 và ngôn ngữ a i 1 2 . n được gọi là ngón ngữ sơ cấp trên s. Phẩn fV. NGÔN NGỮHÌNH THỨC 329 Định nghĩa 2 a Các ngôn ngữ sơ cấp trên X gọi là ngủn ngữ chính quy trên X. b Nếu E và F là hai ngôn ngữ chính quy trên X thì E u F và E cũng là ngón ngữ chính quy trẽn X. c Không có ngôn ngữ chính quy nào khác trên X ngoài các ngôn ngữ chính quy được định nghĩa trong các bước a và b ở trên. Thông thường để diên đạt các ngôn ngữ chính quy người ta đưa vào bicu thức chính quy. . Biểu thức chính quy Trên bảng X ta dinh nghĩa biểu thức chính quy theo các bước đệ quy sau 1 0 là biểu thức chính quy nó biểu diẻn ngôn ngữ rồng. 2 Nếu a e X thì a là biểu thức chính quy nó biểu diễn ngôn ngữ a . 3 Nếu r s là hai biếu thức chính quy trên X biểu điền hai ngôn ngữ R và s tương ứng. Khi đó r s là biểu thức chính quy biếu diễn ngôn ngữ R VJ s. r . s là bicu thức chính quy biểu diễn ngông ngữ . r là biểu thức chính quy biểu diễn ngôn ngữ R . Từ dinh nghĩa về ngôn ngữ chính quy và biểu thức chính quy trên X ta có Định lý 2 Mọi ngôn ngữ chính quy trẽn bảng X đều nhận dược
