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

Chia sẻ: _ _ | Ngày: | Loại File: PPT | Số trang:46

Thêm vào BST

Báo xấu

12
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Ngôn ngữ hình thức: Chương 1 Đại cương về ngôn ngữ và biểu diễn ngôn ngữ, cung cấp cho người học những kiến thức như: Nhắc lại một số kiến thức toán liên quan; Khái niệm chung về ngôn ngữ; Hệ viết lại và vấn đề biểu diễn ngôn ngữ; Văn phạm. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Ngôn ngữ hình thức: Chương 1 - Nguyễn Thị Hồng

NGÔN NGỮ HÌNH THỨC GV: Nguyễn Thị Hồng Email: nguyenhong@hnue.edu.vn
Giới thiệu môn học  Số tín chỉ: 3  Chuyên cần: nghỉ quá 20 % số buổi Cấm thi  Điểm giữa kì: 4 bài  Kiểm tra viết  Bài tập nhóm  Điểm giữa kì
Chương 1 ĐẠI CƯƠNG VỀ NGÔN NGỮ VÀ BIỂU DIỄN NGÔN NGỮ
Nội dung I. Nhắc lại một số kiến thức toán liên quan II. Khái niệm chung về ngôn ngữ III. Hệ viết lại và vấn đề biểu diễn ngôn ngữ IV. Văn phạm
I. Một số kiến thức toán liên quan  Tập hợp  Kí hiệu: A, B, C, …  Cách cho: Liệt kê: A={0, 2, 4, 6, 8} Chỉ ra tính chất của phần tử: B={x/x là số chẵn}
Tập hợp  Các phép toán trên tập hợp: • Hợp: A B={x/x A hoặc x B} • Giao: A B={x/x A và x B} • Hiệu: A\B={x/x A và x B} • Tích Đềcác A×B={(a,b)/a A và b B} • Lũy thừa 2A hay (A) là tập mọi tập con của A
Quan hệ  Định nghĩa: Cho hai tập hợp A và B. Ta gọi quan hệ(hai ngôi) giữa A và B là tập hợp các cặp có thứ tự (a,b) sao cho a A và b B. R A×B  Kí hiệu: R(a,b) R ta viết aRb  Tính chất: R={(a,a)|a A} là quan hệ đồng nhất trên A  Phản xạ: nếu a A: aRa  Bắc cầu (truyền ứng): a, b, c A: aRb và bRc kéo theo aRc  Đối xứng: a, b A: aRb kéo theo bRa.  R là phản đối xứng nếu a, b A: aRb và bRa kéo theo a=b
Quan hệ  Quan hệ phản xạ và truyền ứng  quan hệ tiền thứ tự  Quan hệ tiền thứ tự đối xứng  quan hệ tương đương  Quan hệ tiền thứ tự phản đối xứng  quan hệ thứ tự bộ phận  Quan hệ thứ tự bộ phận sao cho a, b A: aRb hoặc bRa quan hệ thứ tự toàn phần  VD: quan hệ
Quan hệ…  Bao đóng của quan hệ:  Bao đóng truyền ứng (phản xạ, đối xứng) của quan hệ R trên tập A là tập nhỏ nhất chứa quan hệ đã cho mà có tính chất truyền ứng (phản xạ, đối xứng)  Ví dụ:  Cho tập A={x1, x2, x3}  Một quan hệ trên tập A R={(x1,x1); (x1,x2); (x2,x3)}  Bao đóng phản xạ của R: {(x1,x1); (x1,x2); (x2,x3); (x2,x2); (x3,x3)}
Đồ thị  Định nghĩa:Đồ thị G=(V, E) trong đó: V là một tập hữu hạn các đỉnh hay nút E là tập hợp các cặp đỉnh (cạnh)  Ví dụ: G=(V,E) trong đó: V={1,2,3,4,5,6} E={(1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6) }
Đồ thị …  Đồ thị có hướng: G=(V,E) trong đó E là cặp đỉnh có thứ tự (cung)  Cây: là đồ thị có hướng có một nút là Gốc, các nút cha, nút con
II. Ngôn ngữ  Bộ chữ  Xâu  Các phép toán trên xâu  Ngôn ngữ  Các phép toán trên ngôn ngữ
Một số ví dụ  Ví dụ 1: ngôn ngữ Tiếng Việt  Tập hợp các từ Tiếng Việt: “Tôi”, “bạn”, “chơi”, “ăn”, …  Tập hợp các câu Tiếng Việt có nghĩa được xây dựng từ các từ Tiếng Việt: “Tôi ăn cơm” “Tôi đi ngủ”  Các câu gồm hữu hạn các từ Tiếng Việt không có nghĩa thì không thuộc ngôn ngữ Tiếng Việt
Một số ví dụ  Ví dụ 2: Ngôn ngữ lập trình Pascal:  Từ các kí hiệu cơ sở: chu số(0, …,9), chữ cái (a, …,z), các kí hiệu đặc biệt (#, &, …)  Các từ tố được xây dựng từ các kí hiệu cơ sở: BEGIN, END, Return, :=, …  Không phải tất cả các từ được xây dựng từ các kí hiệu cơ sở đều là từ tố.
Một số ví dụ  Nhận xét:  Một ngôn ngữ (tự nhiên hoặc nhân tạo) đều gồm: tập hợp hữu hạn các đối tượng sơ đẳng (từ Tiếng Việt, các kí hiệu cơ sở) và từ các đối tượng này xây dựng được các đơn vị mang nghĩa (câu, từ tố)  Như vậy, nghiên cứu ngôn ngữ phải đề cập đến:  Quy tắc tạo lập đơn vị mang nghĩa từ các đối tượng sơ đẳng  Phương pháp xác định nghĩa của các câu
Ngôn ngữ  Bộ chữ (bảng chữ): là tập hữu hạn các kí hiệu(chữ, kí tự). Số phần tử của bộ chữ V kí hiệu là #V  Ví dụ:  Ngôn ngữ Tiếng Việt: bộ chữ là các từ Tiếng Việt.  Ngôn ngữ các từ tố Pascal: bộ chữ là các kí hiệu cơ sở: chữ cái, chữ số, kí hiệu đặc biệt.
II. Ngôn ngữ  Xâu (từ, câu): trên bộ chữ V là một dãy các kí hiệu trong V viết liên liền nhau.  Ví dụ: Cho V là {0,1}  Xâu: 00101 là xâu trên bộ chữ V 0 0001  không là xâu trên V 10a001 không là xâu trên V
Xâu…  Chiều dài xâu: là số kí hiệu trong xâu  Xâu rỗng là xâu có chiều dài là 0. Kí hiệu: ε (hoặc )  Xâu con là một phần của xâu. Ví dụ: xâu w=abc có các xâu con là ε, a, b, c, ab, bc, abc.  Cho bộ chữ V, Kí hiệu: V* là tập tất cả các xâu trên V, V+ là tập các xâu không rỗng trên V
Xâu …  Tiền tố: của một xâu là xâu con ở đầu xâu  Hậu tố: của một xâu là xâu con ở cuối xâu Ví dụ: w=abcd  Tiền tố: ε, a, ab, abc, abcd Hậu tố: ε, d, cd, bcd, abcd
Xâu …  Một số quy ước: Cho bộ chữ V  Vn (n N) là tập hợp các xâu trên V có độ dài n  V0={ }: xâu rỗng là xâu trên mọi bộ chữ;  V1=V: các xâu có độ dài 1 là đồng nhất với các kí hiệu  V* là tập hợp tất cả các xâu trên V. V*= U Vi (i≥0)  V+ là tập các xâu không rỗng trên V V+= U Vi (i>0)