GIẢNG V I Ê N : T S . H À C H Í T R U N G
BỘ M Ô N : K H M T
K H O A C N T T , H V K T Q S
Đ T : 0 1 6 8 . 5 5 8 . 2 1 . 0 2
E M A I L : H C T 2 0 0 9 @ Y A H O O . C O M
Lý thuyết automata và
ngôn ngữ hình thức
© PhD. C.T.Ha, Le Quy Don Technical University
Languague
Grammar
Automata
2
Bài 3. Ngôn ngữ và automata hữu hạn
(Formal Languagues and
Finite Automata)
MỤ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
3.1. Các khái niệm sơ lược
3.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à NFA
3.6. Sự tương đương giữa NFAε và DFA
3.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à RE
3
28/03/2012
Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University
Bài 3. Ngôn ngữ và automata hữu hạn
3.1. Các khái niệm sơ lược
3.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à NFA
3.6. Sự tương đương giữa NFAε và DFA
3.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à RE
4
28/03/2012
Automata và ngôn ngữ hình thức - © PhD. C.T.Ha, Le Quy Don Technical University
3.1. Các khái niệm sơ lược
28/03/2012
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
