TAILIEUCHUNG - Bài giảng Ngôn ngữ hình thức: Chương 2 - Nguyễn Thị Hồng

Bài giảng Ngôn ngữ hình thức: Chương 2 Ôtômát hữu hạn và biểu thức chính quy, cung cấp cho người học những kiến thức như: Biểu thức chính quy; Nguyên lý hoạt động Ôtômát; Ôtômát hữu hạn tiền định; Sự tương đương giữa ô tô mát hữu hạn và biểu thức chính quy. Mời các bạn cùng tham khảo! | Chương 2 ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY 1 I. Biểu thức chính quy BTCQ Định nghĩa Cho bộ chữ là một BTCQ ε là một BTCQ a thì a là một BTCQ là các BTCQ . là các BTCQ 2 Biểu thức chính quy Quy ước Để lược bớt các vòng đơn áp dụng các mức ưu tiên với các toán tử theo thứ tự . Toán tử được viết ở vị trí chỉ số trên. Toán tử ghép tiếp . có thể được bỏ qua viết β thay vì .β 3 Giá trị của BTCQ Một BTCQ trên biểu diễn một ngôn ngữ trên L L ε ε L a a với a L L L L L .L L L Ta gọi ngôn ngữ chính quy là mọi ngôn ngữ có thể được chỉ định bởi một biểu thức chính quy. 4 Biểu thức chính quy Ví dụ 0 1 BTCQ Giá trị 00 00 0 1 0 1 0 1 00 0 1 x x 0 1 và x chứa 2 con 0 liên tiếp 1 10 x x 0 1 x có con 1 ở đầu và không có hai con 0 liên tiếp 5 Tính chất của BTCQ Cho r s t là các BTCQ 1 r s s r 8 r r r 2 r s t r s t 9 r st rs t 3 r s t rs rt 10 r s t rt st 4 rε εr r 11 r r 5 r r 12 ε 6 ε r r 13 r r r 7 r r 14 r s r s 6 Ví dụ Sử dụng các tính chất của biểu thức chính quy rút gọn công thức sau 0 0 0 1 1 1 7 Ô tô mát hữu hạn Ô tô mát hữu hạn Trực quan là máy trừu tượng đoán nhận ngôn ngữ Hình thức là hệ viết lại đoán nhận xâu bằng cách viết lại cho đến khi gặp tiên đề. Gồm hai loại Ôtômát hữu hạn tiền định DFA Ôtômát hữu hạn không tiền định NFA 8 Cấu tạo của OHT Băng vào 1 0 0 1 1 1 0 Đầu đọc q Cái điều khiển Hình. Ôtômát hữu hạn tiền định 9 Cấu tạo của OHT Cấu tạo Một băng vào chứa xâu cần xử lý xâu vào mỗi ô chứa một kí tự Một đầu đọc tại mỗi thời điểm trỏ vào một ô của băng vào và cho phép đọc kí hiệu trong ô đó Cái điều khiển bộ chuyển trạng thái tại mỗi thời điểm có một trạng thái Các trạng thái là hữu hạn Có một trạng thái đầu và các trạng thái thừa nhận Một hàm dịch chuyển cho phép xác định trạng thái tiếp theo dựa và trạng thái và kí hiệu đọc được hiện tại 10 Nguyên lý hoạt động Ban đầu OHT ở trạng thái đầu đầu đọc trỏ vào kí hiệu đầu tiên của xâu vào Lặp ÔHT đọc kí hiệu trên băng xác định trạng thái tiếp theo dựa vào hàm dịch chuyển đẩy đầu đọc sang phải một ô OHT dừng khi .

• Kỹ thuật lập trình
• Bài giảng Ngôn ngữ hình thức
• Ngôn ngữ hình thức
• Ôtômát hữu hạn
• Ngôn ngữ chính quy
• Văn phạm chính quy
• Bài toán bao hàm ngôn ngữ
• Lí thuyết Ngôn ngữ hình thức
• Bài giảng Lí thuyết Ngôn ngữ hình thức
• Lí thuyết Ngôn ngữ hình thức và ôtômat
• Ngôn ngữ phi ngữ cảnh
• Bài giảng Ngôn ngữ hình Đại cương về ngôn ngữ
• Biểu diễn ngôn ngữ
• Hệ viết lại
• Phép toán trên tập hợp
• Bài giảng Trị liệu ngôn ngữ
• Trị liệu ngôn ngữ
• Đánh giá ngôn ngữ
• Các dạng ngôn ngữ
• Các hình thức ngôn ngữ
• Trẻ bị rối loạn ngôn ngữ
• Âm vị học ngữ pháp
• Ngôn ngữ hình thức và ôtômát
• Văn phạm hình thức
• Phép toán trên từ
• Phép toán trên ngôn ngữ
• Máy Turing
• Dạng chuẩn Chomsky
• Văn phạm phi ngữ cảnh
• Otomat đẩy xuống
• Chương trình dịch
• Lí thuyết ngôn ngữ hình thức và ôtômát
• Lí thuyết ngôn ngữ
• Lớp ngôn ngữ chính quy
• Automat hữu hạn
• Bài giảng Ôtômát và ngôn ngữ hình thức
• Phân cấp văn phạm
• Cấu tạo Ôtômát
• Xây dựng văn phạm cho ngôn ngữ
• Phép toán trên xâu
• Ngôn ngữ lập trình Pascal
• Ôtômát đẩy xuống
• Suy dẫn phi ngữ cảnh
• Cây suy dẫn
• Ngôn ngữ lập trình
• Ôtômat đẩy xuống
• Bài toán xâu rỗng
• Thuật toán Thampson
• Ngôn ngữ đoán nhận
• Bản chất của thuật toán
• Otomat hữu hạn
• Bài giảng công nghệ thông tin
• Tập bài giảng Ngôn ngữ hình thức
• Automat hữu hạn đơn định
• Automat đẩy xuống
• Lý thuyết Automat
• Lý thuyết tính toán Otomat
• Lý thuyết ngôn ngữ hình thức
• Kỹ thuật mô phỏng
• Kỹ thuật chứng minh
• Otomat và ngôn ngữ hình thức
• Văn phạm và ngôn ngữ hình thức
• Bài giảng Đặc tả hình thức
• Đặc tả hình thức
• Mô hình Thế giới thực
• Ngôn ngữ đặc tả hình thức
• Quy trình công nghệ phần mềm
• Các tính chất của quan hệ
• Phép toán trên các tập hợp
• Các quan hệ tương đương
• Chương trình con
• Thiết kế thuật toán
• Ôtômát tuyến tính giới nội
• Máy turing tiền định
• Cấu tạo máy Turing
• Ngôn ngữ hình thức và Ôtômat
• Ôtomat hữu hạn