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

Biểu diễn ngôn ngữ một cách tổng quát thông qua văn phạm (grammar) và automata:Văn phạm: cơ chế sản sinh ra mọi chuỗi của ngôn ngữ;Automata: là một máy trừu tượng, hay một cơ chế cho phép đoán nhận một chuỗi bất kỳ có thuộc một ngôn ngữ L hay không
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 2 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 ©copyright by PhD. C.T.Ha, Le Quy Don Technical University Bài 2. Văn phạm và ngôn ngữ hình thức Grammars and formal languagues 2MỤC ĐÍCH:  Trang bị những khái niệm cơ bản của môn học TA&FL;YÊU CẦU:  Sinh viên nắm vững các khái niệm làm cơ sở cho các bài học tiếp theo. ©copyright by PhD. C.T.Ha, Le Quy Don Technical University Bài 2. Văn phạm và ngôn ngữ hình thức 3 2.1. Ngôn ngữ 2.1.1. Các khái niệm cơ bản 2.1.2. Các phép toán trên từ 2.1.3. Các phép toán trên ngôn ngữ 2.2. Văn phạm 2.2.1. Văn phạm và các khái niệm liên quan 2.2.2. Phân loại văn phạm theo Chomsky 2.2.3. Tính chất của văn phạm và ngôn ngữ 2.2.4. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm 2.3. Sơ lược về automataAutomata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012 Bài 2. Văn phạm và ngôn ngữ hình thức 4 2.1. Ngôn ngữ 2.1.1. Các khái niệm cơ bản 2.1.2. Các phép toán trên từ 2.1.3. Các phép toán trên ngôn ngữ 2.2. Văn phạm 2.2.1. Văn phạm và các khái niệm liên quan 2.2.2. Phân loại văn phạm theo Chomsky 2.2.3. Tính chất của văn phạm và ngôn ngữ 2.2.4. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm 2.3. Sơ lược về automataAutomata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012 2.1.1. Các khái niệm cơ bản 5 ĐN 2.1. Tập Σ khác rỗng gồm hữu hạn hay vô hạn các ký hiệu được gọi là bảng chữ cái. Mỗi phần a   tử được gọi là một chữ cái hay một ký hiệu.  ∑ = {a, b, c, … , x, y, z} bảng chữ cái tiếng Anh;  Δ = {α, β, γ, δ, ε, η, ϕ, κ, μ, χ, ν, π, θ, ρ, ζ, η, ω,ξ, ψ};  Г = {0, 1} bảng chữ cái nhị phân; ĐN 2.2. Cho   a1 , a2 ,..., am  , một dãy   ai1ai 2 ...ait , aij  được gọi là một từ hay một xâu (chuỗi) trên bảng Σ.  ε, 0, 01, 101, 1010, 110011 là các từ trên bảng chữ cái Г = {0,1};  ε, beautiful, happy… là các từ trên Σ = {a, b, c, …, z}.Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012 2.1.1. Các khái niệm cơ bản 6 ĐN 2.3. Độ dài chuỗi: là số các ký hiệu tạo thành chuỗi • |abca| = 4 ĐN 2.4. Chuỗi rỗng: ký hiệu ε, chuỗi không có ký hiệu nào • |ε| = 0 ĐN 2.5. Chuỗi con: chuỗi v là chuỗi con của w nếu v được tạo bởi các ký hiệu liền kề nhau trong chuỗi w. • Chuỗi 10 là chuỗi con của chuỗi 010001 ĐN 2.6. Chuỗi tiền tố: là chuỗi con bất kỳ nằm ở đầu chuỗi ĐN 2.7. Chuỗi hậu tố: là chuỗi con bất kỳ nằm ở cuối chuỗi • Chuỗi abc có các tiền tố a, ab, abc • Chuỗi 0246 có các hậu tố 6, 46, 246, 0246Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012 2.1.1. Các khái niệm cơ bản 7 Ngôn ngữ: theo từ điển, là một hệ thống thích hợp cho việc biểu thị các ý nghĩ, các sự kiện, hay các khái niệm, bao gồm tập các ký hiệu, các qui tắc để vận dụng chúng. ĐN 2.8: Một ngôn ngữ (hình thức) L trên bộ chữ cái  là một tập hợp các chuỗi từ các ký hiệu của bộ chữ cái .  * : tập hợp tất cả các chuỗi con, kể cả chuỗi rỗng ε, sinh ra từ bộ chữ cái .  + : tập hợp tất cả các chuỗi con, ngoại trừ chuỗi rỗng ε, sinh ra từ bộ chữ cái . * = + + {ε} + = * - {ε}Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012 2.1.1. Các khái niệm cơ bản 8 Ví dụ 1: Cho  = {0,1} thì:  * = {ε, 0, 1, 00, 01, 10, 11, 000, …}  + = {0, 1, 00, 01, 10, 11, 000, …}  Chuỗi 010210  * vì có số 2  Automata và ngôn ngữ hình thức - ©copyright by PhD. C.T.Ha, Le Quy Don Technical University 07/03/2012 2.1.1. Các khái niệm cơ bản 9 Biểu diễn ngôn ngữ: Liệt kê các phần tử (chuỗi): L = {aa, aba, baa, baba} Mô tả đặc điểm chủ yếu: L = {ai | i là số nguyên tố} Biểu diễn ...