Lý thuyết automata và ngôn ngữ hình thức - Bài 3

Automata là một máy trừu tượng (mô hình tính toán) có cơ cấu và hoạt động đơn giản nhưng có khả năng đoán nhận ngôn ngữ.Finite automata (FA) - mô hình tính toán hữu hạn: có khởi đầu và kết thúc, mọi thành phần đều có kích thước hữu hạn cố định và không thể mở rộng trong suốt quá trình tính toán;
Nội dung trích xuất từ tài liệu:
Lý thuyết automata và ngôn ngữ hình thức - Bài 3 Lý thuyết automata và ngôn ngữ hình thức AutomataGrammar GIẢNG VIÊN: TS. HÀ CHÍ TRUNG Languague BỘ MÔN: KHMT KHOA CNTT, HVKTQS ĐT:0168.558.21.02 EMAIL: HCT2009@YAHOO.COM © PhD. C.T.Ha, Le Quy Don Technical University Bài 3. Ngôn ngữ và automata hữu hạn (Formal Languagues and Finite Automata) 2MỤC ĐÍCH:  Trang bị những khái niệm về automata hữu hạn (FA);  Phân loại FA;  các phép biến đổi tương đương giữa các loại FA;  Biểu thức chính qui (RE) và sự tương đương với FA;YÊU CẦU:  Sinh viên nắm vững các khái niệm, các thuật toán biến đổi và làm các dạng bài tập. © PhD. C.T.Ha, Le Quy Don Technical University Bài 3. Ngôn ngữ và automata hữu hạn 33.1. Các khái niệm sơ lược3.2. Automata hữu hạn đơn định (DFA)3.3. Automata hữu hạn đa định (NFA)3.4. Automata với dịch chuyển ε (NFAε)3.5. Sự tương đương giữa DFA và NFA3.6. Sự tương đương giữa NFAε và DFA3.7. Biểu thức chính quy 3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và REAutomata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012 Bài 3. Ngôn ngữ và automata hữu hạn 43.1. Các khái niệm sơ lược3.2. Automata hữu hạn đơn định (DFA)3.3. Automata hữu hạn đa định (NFA)3.4. Automata với dịch chuyển ε (NFAε)3.5. Sự tương đương giữa DFA và NFA3.6. Sự tương đương giữa NFAε và DFA3.7. Biểu thức chính quy 3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tương đương giữa DFA và REAutomata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012 3.1. Các khái niệm sơ lược 5 Automata là một máy trừu tượng (mô hình tính toán) có cơ cấu và hoạt động đơn giản nhưng có khả năng đoán nhận ngôn ngữ. Finite automata (FA) - mô hình tính toán hữu hạn: có khởi đầu và kết thúc, mọi thành phần đều có kích thước hữu hạn cố định và không thể mở rộng trong suốt quá trình tính toán;  Hoạt động theo theo từng bước rời rạc (steps);  Nói chung, thông tin ra sản sinh bởi một FA phụ thuộc vào cả thông tin vào hiện tại và trước đó. Nếu sử dụng bộ nhớ (memory), giả sử rằng nó có ít nhất một bộ nhớ vô hạn; Sự phân biệt giữa các loại automata khác nhau chủ yếu dựa trên việc thông tin có thể được đưa vào memory hay không;Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012 3.1. Các khái niệm sơ lược 6 DFA (Deterministic RE (Regular Finite Automata) Expression) FA (Finite Automata) NFA RG (Regular (Nondeterministic Grammar) or RL Finite Automata)Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012 3.1. Các khái niệm sơ lược 7 Đoán nhận ngôn ngữ: đoán nhận các từ của ngôn ngữ đó. Hoạt động của automata bắt đầu từ một trạng thái đặc biệt, trang thái đầu tiên (start state); Giả sử rằng tại mỗi thời điểm (step, time step), automata đang ở một trạng thái nào đó (current state), đầu vào của automata đón nhận một ký tự của chuỗi cần xử lý, dưới tác động của ký tự đó automata chuyển sang một trạng thái kế tiếp (next state); Chuỗi được đoán nhận nếu trạng thái cuối cùng của automata rơi vào một trong các trạng thái kết thúc (finish states).Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University 28/03/2012 Bài 3. Ngôn ngữ và automata hữu hạn 83.1. Các khái niệm sơ lược3.2. Automata hữu hạn đơn định (DFA)3.3. Automata hữu hạn đa định (NFA)3.4. Automata với dịch chuyển ε (NFAε)3.5. Sự tương đương giữa DFA và NFA3.6. Sự tương đương giữa NFAε và DFA3.7. Biểu thức chính quy 3.7.1. khái niệm về biểu thức chính quy 3.7.2. Sự tương đương giữa FA và RE 3.7.3. Sự tươ ...