Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 2 - ThS. Nguyễn Thị Thùy Linh

Bài giảng Ôtômát và ngôn ngữ hình thức: Chương 2 Ngôn ngữ, văn phạm và ôtômát cung cấp cho người học những kiến thức như: Ngôn ngữ (languages); Văn phạm (grammar); Ôtômat (automata). Mời các bạn cùng tham khảo! | Nội dung Ba khái niệm cơ bản Chương 2 1. Ngôn ngữ languages Khái niệm ngôn ngữ Biểu diễn ngôn ngữ Ngôn ngữ văn phạm và Hệ viết lại và vấn đề biểu diễn ngôn ngữ. Văn phạm grammar ôtômát 2. Định nghĩa văn phạm Sự phân cấp văn phạm 3. Ôtômat automata 2 Tổng quan về ngôn ngữ Ký hiệu bộ chữ cái chuỗi Ngôn ngữ tự nhiên tiếng Việt tiếng Anh Ký hiệu symbol Ngôn ngữ lập trình Pascal C C Ví dụ các chữ cái a b c các chữ số 1 2 3 Bộ chữ cái alphabet hay bảng chữ cái Σ là một tập hợp không rỗng ĐN ngôn ngữ trong các từ điển các ký hiệu Là tập hợp các câu theo cấu trúc quy định nào đó Bảng chữ cái La Mã I V X L C D M Biểu thị các ý nghĩ các sự kiện hay các khái niệm Bảng chữ số nhị phân 0 1 Bao gồm một tập các ký hiệu và các quy tắc để vận dụng chúng Bảng chữ số thập phân 0 1 2 9 Định nghĩa trên chưa đủ chính xác để nghiên cứu về ngôn Bảng chữ cái Latinh A B C . Z a b c . z ngữ hình thức ngôn ngữ dùng chung cho cả ngôn ngữ tự Bảng chữ cái Hi Lạp β γ nhiên lẫn ngôn ngữ lập trình . Chúng ta cần xây dựng một Qui ước định nghĩa toán học cho khái niệm về ngôn ngữ. Bộ chữ cái thường dùng Σ a b c Σ 0 1 Các kí hiệu u v w x y z t dùng gọi cho tên chuỗi. 3 4 1 Ký hiệu bộ chữ cái chuỗi Ký hiệu bộ chữ cái chuỗi Chuỗi Xâu string là một dãy hữu hạn các ký hiệu xếp liên tục Chuỗi tiền tố là một chuỗi con bất kỳ nằm ở đầu chuỗi đó. nhau gồm Chuỗi hậu tố là một chuỗi con bất kỳ nằm ở cuối chuỗi đó. Các ký hiệu thuộc Σ Ví dụ chuỗi abc có các tiền tố là a ab abc và có các hậu tố Mỗi ký hiệu có thể xuất hiện nhiều lần là c bc abc. Ví dụ 010001 là một chuỗi trên bộ chữ cái Σ 0 1 Chuỗi nối kết ghép ký hiệu bởi vw là một chuỗi được tạo w abbcab là một chuỗi trên bộ chữ cái Σ a b c bằng cách viết v rồi viết w tiếp theo sau không có khoảng cách. Độ dài chuỗi w ký hiệu bởi w là số những ký hiệu hợp thành w. Ví dụ ghép Long và Int là LongInt. Chẳng hạn 010001 6. Nối kết với chuỗi rỗng εw wε w w Chuỗi rỗng ký hiệu hay là chuỗi có độ dài 0 tức là chuỗi khi đó ε là đơn vị của phép nối kết không có ký hiệu .

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.