intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Tập bài giảng Ngôn ngữ hình thức

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

Thêm vào BST
Báo xấu
44
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tập bài giảng “Ngôn ngữ hình thức” được biên soạn theo chương trình chi tiết môn học “Ngôn ngữ hình thức” của trường Đại học Sư phạm Kỹ thuật Nam Định. Mục tiêu của tập đề cương bài giảng nhằm cung cấp các kiến thức cơ bản, tổng quan về ngôn ngữ, văn phạm và automat; giúp sinh viên nắm vững các kiến thức cơ bản về văn phạm chính quy và automat hữu hạn, văn phạm phi ngữ cảnh và automat đẩy xuống là công cụ dùng để xây dựng và phân tích từ vựng, cú pháp của các ngôn ngữ lập trình. 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: Tập bài giảng Ngôn ngữ hình thức

  1. Ngôn ngữ hình thức Mục lục LỜI NÓI ĐẦU ............................................................................................................ 4 Chƣơng 1. TỔNG QUAN VỀ NGÔN NGỮ VÀ AUTOMAT ................................. 6 1.1. Các khái niệm cơ bản ....................................................................................... 6 1.1.1. Khái niệm ngôn ngữ hình thức.................................................................. 6 1.1.2. Bảng chữ cái (alphabet) ............................................................................ 8 1.1.3. Xâu trên bảng chữ cái ............................................................................... 8 1.1.4. Các phép toán trên xâu .............................................................................. 9 1.1.5. Ngôn ngữ (language)............................................................................... 10 1.2. Văn phạm và ngôn ngữ .................................................................................. 13 1.2.1. Văn phạm ................................................................................................ 13 1.2.2. Ngôn ngữ sinh bởi Văn phạm ................................................................. 15 1.2.3. Văn phạm tƣơng đƣơng .......................................................................... 16 1.3. Phân loại văn phạm và ngôn ngữ ................................................................... 16 1.3.1. Văn phạm và ngôn ngữ loại 0 ................................................................. 16 1.3.2. Văn phạm và ngôn ngữ loại 1 ................................................................. 17 1.3.3. Văn phạm và ngôn ngữ loại 2 ................................................................. 17 1.3.4. Văn phạm và ngôn ngữ loại 3 ................................................................. 17 1.3.5. Ví dụ ........................................................................................................ 18 1.4. Một số tính chất của ngôn ngữ....................................................................... 19 1.4.1. Tính chất 1............................................................................................... 19 1.4.2 Tính chất 2................................................................................................ 20 1.4.3. Tính chất 3............................................................................................... 20 1.4.4. Tính chất 4............................................................................................... 21 1.4.5. Tính chất 5 (Tính đệ quy của ngôn ngữ) ................................................. 21 1.5. Automat ......................................................................................................... 23 1.5.1. Mô tả automat ......................................................................................... 23 1.5.2. Phân loại automat .................................................................................... 24 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 1 ..................................................................... 25 Phạm Hùng Phú 1
  2. Ngôn ngữ hình thức Chƣơng 2. VĂN PHẠM CHÍNH QUY VÀ AUTOMAT HỮU HẠN .................... 30 2.1. Automat hữu hạn (FINITE AUTOMAT - FA) ................................................ 31 2.1.1. Định nghĩa Automat hữu hạn .................................................................. 31 2.1.2. Automat hữu hạn đơn định ...................................................................... 36 2.1.3. Automat hữu hạn không đơn định-NFA (Nondeterministic Finite Automata) .......................................................................................................... 42 2.1.4. Sự tƣơng đƣơng giữa DFA và NFA ........................................................ 49 2.1.5. NFA với ε-dịch chuyển (NFAε) .............................................................. 56 2.1.6. Sự tƣơng đƣơng giữa NFA có và không có ε-dịch chuyển ..................... 62 2.2. Biểu thức chính quy (RE: Regular Expressions) ........................................... 64 2.2.1. Định nghĩa ............................................................................................... 65 2.2.2. Một số tính chất đại số của biểu thức chính quy ..................................... 66 2.2.3. Sự tƣơng đƣơng giữa automat hữu hạn và biểu thức chính quy ............. 67 2.3. Văn phạm chính quy ...................................................................................... 79 2.3.1. Văn phạm tuyến tính ............................................................................... 79 2.3.2. Sự tƣơng đƣơng giữa văn phạm chính quy và automat hữu hạn ............. 80 2.3.3. Tính chất của ngôn ngữ chính quy .......................................................... 87 2.3.4. Bổ đề bơm cho ngôn ngữ chính quy........................................................ 90 2.3.5. Xác định ngôn ngữ chính quy ................................................................. 92 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 ..................................................................... 94 Chƣơng 3. VĂN PHẠM PHI NGỮ CẢNH VÀ AUTOMAT ĐẨY XUỐNG....... 107 3.1. Văn phạm phi ngữ cảnh (CFG: Context Free Grammar) ............................. 107 3.1.1. Định nghĩa ............................................................................................. 109 3.1.2. Dẫn xuất và ngôn ngữ............................................................................ 110 3.1.3. Cây dẫn xuất .......................................................................................... 111 3.1.4. Quan hệ giữa dẫn xuất và cây dẫn xuất ................................................. 113 3.1.5. Dẫn xuất trái nhất, dẫn xuất phải nhất ................................................... 115 3.1.6. Văn phạm nhập nhằng (mơ hồ) ............................................................. 116 3.2. Rút gọn văn phạm phi ngữ cảnh .................................................................. 117 3.2.1. Loại bỏ các ký tự thừa ........................................................................... 118 2 Phạm Hùng Phú
  3. Ngôn ngữ hình thức 3.2.2. Luật sinh ε (ε quy tắc) ........................................................................... 124 3.2.3. Luật sinh đơn vị..................................................................................... 128 3.3. Chuẩn hóa văn phạm phi ngữ cảnh .............................................................. 130 3.3.1. Dạng chuẩn Chomsky - CNF (Chomsky Normal Form) ...................... 130 3.3.2. Dạng chuẩn Greibach (Greibach Normal Form - GNF) ....................... 134 3.4. Tính chất của ngôn ngữ phi ngữ cảnh .......................................................... 140 3.4.1. Bổ đề bơm đối với CFL (Dùng để chứng minh một ngôn ngữ không là ngôn ngữ phi ngữ cảnh) .................................................................................. 140 3.4.2. Tính chất đóng của CFL ........................................................................ 143 3.5. Automat đẩy xuống (Push down Automata) ............................................... 145 3.5.1. Mô tả PDA ............................................................................................ 145 3.5.2. Định nghĩa Automat đẩy xuống ............................................................ 146 3.5.3. Ngôn ngữ đoán nhận bởi PDA .............................................................. 150 3.5.4. PDA và văn phạm phi ngữ cảnh .......................................................... 153 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 3 ................................................................... 161 LỜI GIẢI TÓM TẮT HOẶC HƢỚNG DẪN ........................................................ 168 TÀI LIỆU THAM KHẢO ...................................................................................... 246 Phạm Hùng Phú 3
  4. LỜI NÓI ĐẦU LỜI NÓI ĐẦU Ngôn ngữ hình thức (Formal Languages) là bộ môn khoa học quan trọng của khoa học máy tính. Ở nhiều nước trên thế giới, môn học này đã trở thành môn học cơ sở đối với sinh viên các ngành thuộc lĩnh vực công nghệ thông tin. Ở nước ta, hiện nay nhiều trường đại học cũng đang giảng dạy môn học “Ngôn ngữ hình thức” cho sinh viên các ngành khoa học máy tính và công nghệ thông tin. Tuy nhiên tài liệu phục vụ giảng dạy cho môn học ở nước ta còn ít, thời lượng dành cho môn học cũng còn rất khác nhau ở mỗi trường. §Ó cã mét néi dung thèng nhÊt cho c¸c ngµnh thuộc lÜnh vùc c«ng nghÖ th«ng tin cña Tr-êng, tr-êng §¹i häc S- ph¹m Kü thuËt Nam §Þnh ®· ban hµnh ch-¬ng tr×nh chi tiÕt cho m«n häc. Việc xuất bản tập đề cương bài giảng nhằm đáp ứng nhu cầu cung cấp tài liệu môn học cho việc giảng dạy của giảng viên và học tập của sinh viên các ngành thuộc khoa Công nghệ Thông tin trường Đại học Sư phạm Kỹ thuật Nam Định nói riêng và làm tại liệu tham khảo cho sinh viên và cán bộ giảng dạy các trường nói chung. Tập đề cương bài giảng “Ngôn ngữ hình thức” được biên soạn theo chương trình chi tiết môn học “Ngôn ngữ hình thức” của trường Đại học Sư phạm Kỹ thuật Nam Định. Mục tiêu của tập đề cương bài giảng nhằm cung cấp các kiến thức cơ bản, tổng quan về ngôn ngữ, văn phạm và automat; giúp sinh viên nắm vững các kiến thức cơ bản về văn phạm chính quy và automat hữu hạn, văn phạm phi ngữ cảnh và automat đẩy xuống là công cụ dùng để xây dựng và phân tích từ vựng, cú pháp của các ngôn ngữ lập trình. Đây là các kiến thức nền tảng, làm cơ sở cho việc xây dựng ra các ngôn ngữ lập trình và các chương trình dịch. Về nội dung, tập đề cương bài giảng được chia thành 3 chương: Chương 1. Tổng quan về ngôn ngữ và automat. Chương này trình bày: Các khái niệm, kiến thức cơ bản về bảng chữ cái, xâu trên bảng chữ cái, các phép toán trên xâu; khái niệm văn phạm và ngôn ngữ, phân loại văn phạm và ngôn ngữ, các phép toán trên ngôn ngữ và biểu diễn ngôn ngữ; khái niệm, phân loại automat. Chương 2. Văn phạm chính quy và automat hữu hạn. Chương này trình bày các kiến thức cơ bản về: Automat hữu hạn (FA); automat hữu hạn đơn định (DFA) và Automat hữu hạn không đơn định (NFA); Sự tương đương giữa DFA và NFA; Biểu thức chính quy; sự tương đương giưa FA và biểu thức chính quy; Văn phạm chính quy, sự tương đương giữa văn phạm chính quy và FA; tính chất của văn phạm chính quy. 4 Phạm Hùng Phú
  5. Ngôn ngữ hình thức Chương 3. Văn phạm phi ngữ cảnh và automat đẩy xuống. Chương này trình bày các kiến thức cơ bản về: Văn phạm phi ngữ cảnh (CFG); rút gọn văn phạm phi ngữ cảnh; chuẩn hoá văn phạm phi ngữ cảnh; tính chất của văn phạm phi ngữ cảnh; automat đẩy xuống (PDA); sự tương đương của PDA và CFG. Đặc biệt cuối mỗi chương còn đưa ra hệ thống câu hỏi, bài tập nhằm củng cố, khắc sâu, nâng cao và vận dụng các kiến thức vào giải các bài tập và cuối cùng là phần lời giải tóm tắt hoặc hướng dẫn cho các bài tập nhằm giúp sinh viên tự rèn luyện kỹ năng và kiểm tra kiến thức. Trong quá trình biên soạn, tập đề cương bài giảng không tránh khỏi những sai sót, rất mong đồng nghiệp và các em sinh viên góp ý kiến để tập đề cương bài giảng ngày càng được hoàn thiện hơn. Người biên soạn Phạm Hùng Phú Phạm Hùng Phú 5
  6. Chương 1. Tổng quan về Ngôn ngữ và Automat Chƣơng 1 TỔNG QUAN VỀ NGÔN NGỮ VÀ AUTOMAT Mục tiêu: Giúp sinh viên có khả năng: - Hiểu đƣợc các khái niệm cơ bản: xâu, ngôn ngữ, văn phạm. - Hiểu đƣợc các phép toán trên xâu, ngôn ngữ. - Xác định đƣợc các thành phần của văn phạm. - Biết đƣợc mối quan hệ giữa văn phạm và ngôn ngữ, cách phân loại văn phạm và ngôn ngữ, các phƣơng pháp biểu diễn ngôn ngữ. - Vận dụng đƣợc các kiến thức vào giải các bài tập. Nội dung chính: - Các khái niệm cơ bản. - Khái niệm, phân loại văn phạm và ngôn ngữ. - Các phép toán trên ngôn ngữ và biểu diễn ngôn ngữ. - Khái niệm, phân loại và biểu diễn automat. 1.1. Các khái niệm cơ bản 1.1.1. Khái niệm ngôn ngữ hình thức Ta đã từng nghe, từng nói nhiều về ngôn ngữ nhƣ ngôn ngữ tiếng Anh, tiếng Việt, ngôn ngữ lập trình Pascal, ngôn ngữ thuật toán, … Song ít ngƣời có thể trả lời chính xác câu hỏi ngôn ngữ là gì?; có bao nhiêu loại ngôn ngữ? và điều quan trọng hơn, thu hút sự quan tâm hơn là làm thế nào để có ngôn ngữ?. Từ lâu các nhà ngôn ngữ học đã nghiên cứu về ngôn ngữ, song việc nghiên cứu của họ thiên về các khía cạnh xã hội, lịch sử của ngôn ngữ nhƣ: quá trình hình thành ngôn ngữ, các đặc trƣng ngôn ngữ của các dân tộc, … Từ khi máy tính ra đời, xuất hiện nhu cầu phải dùng ngôn ngữ đễ diễn đạt thuật toán, phải dịch từ ngôn ngữ thuật toán này sang ngôn ngữ thuật toán khác, … khi đó bắt buộc phải giải quyết một loạt các vấn đề đƣợc đặt ra nhƣ: - Ngôn ngữ là gì?. 6 Phạm Hùng Phú
  7. Chương 1. Tổng quan về Ngôn ngữ và Automat - Làm thế nào để biểu diễn ngôn ngữ?. - Ngôn ngữ thuật toán cần phải có đặc trƣng gì?. - Thế nào là dịch từ ngôn ngữ này sang ngôn ngữ khác?. - Thế nào là bản dịch đúng? … Quan tâm nghiên cứu, giải quyết những vấn đề nêu trên là lĩnh vực nghiên cứu của ngôn ngữ hình thức và chƣơng trình dịch. Trƣớc hết đề cập đến ngôn ngữ hình thức, một cách ngắn gọn ngôn ngữ hình thức đƣợc coi là bộ môn khoa học mà đối tƣợng nghiên cứu của nó là ngôn ngữ và công cụ nghiên cứu của nó là toán học. Nhờ toán học, ngƣời ta có thể gạt bỏ đi những đặc trƣng riêng của từng loại ngôn ngữ, trừu tƣợng hoá, hình thức hoá những vấn đề bản chất nhất của ngôn ngữ để nghiên cứu chúng. Chính vì lý do này mà ngôn ngữ hình thức còn có tên gọi là “Lý thuyết ngôn ngữ lập trình”. Để minh hoạ cho cách tiếp cận nghiên cứu ngôn ngữ của bộ môn khoa học này, ta xét ví dụ sau: Xét trong câu tiếng Việt: “Tôi ăn cơm” Từ “tôi” là , từ “ăn” là , từ “cơm” là , khi đó ta có thể khái quát câu trong tiếng Việt gồm 3 thành phần sắp xếp ở dạng sau: Trong đó có thể là hoặc , thay cho các viết này ta viết ngắn gọn:  | Tƣơng tự nhƣ vậy ta có thể viết:  anh | tôi | nó| ông | bà | em |….  cam | bánh | kẹo | xôi | báo | voi….   đi | đứng | học | làm | nhảy | viết | vẽ…  Theo nguyên tắc này, ngƣời ta có thể tạo ra các câu một cách máy móc. Ví dụ nhƣ: tôi viết báo cáo, anh ấy học bài, … Phạm Hùng Phú 7
  8. Chương 1. Tổng quan về Ngôn ngữ và Automat 1.1.2. Bảng chữ cái (alphabet) Một bảng chữ cái hay bộ chữ cái là một tập hợp hữu hạn, khác rỗng các phần tử, ký hiệu là . Các phần tử của một bảng chữ cái  đƣợc gọi là các chữ cái hoặc các ký tự (character) hay ký hiệu (symbol). Ví dụ: - Tập hợp các chữ cái La tinh a, b, c, …, A, B, …, Z  là một bảng chữ cái và a, b, ..., A, ... là các chữ cái hay các ký tự. - Tập hợp các bít nhị phân 0, 1 là một bảng chữ cái và 0, 1 là các ký hiệu hay các ký tự. - Tập hợp các chữ cái Hy Lạp  = , , , …,  là một bảng chữ cái và , , , …, , là các ký hiệu hay các ký tự. - Tập hợp các chữ số thập phân 0, 1, …, 9 là một bảng chữ cái và 1, …, 9 là các chữ cái hoặc các ký hiệu hay các ký tự. Để chỉ một chữ cái hoặc ký tự hay ký hiệu thuộc hay không thuộc một bảng chữ cái ta dùng ký hiệu  hoặc . Ví dụ: ; 9 1.1.3. Xâu trên bảng chữ cái Xâu (string) hay từ (word) trên một bảng chữ cái  là một dãy hữu hạn gồm một số lớn hơn hay bằng không các ký tự của bảng chữ cái đó; Trong đó, một ký tự có thể xuất hiện nhiều lần. Ví dụ: - Aaab, bbbbb là các từ trên bảng chữ cái La Tinh. - , 0, 1, 00101, 000011 là các từ trên bảng chữ cái  = 0, 1. Độ dài của từ hay xâu w là số ký tự tạo thành xâu w và đƣợc ký hiệu là |w| Chú ý: - Thuật ngữ xâu hay từ còn đồng nghĩa với xâu ký tự. - Xâu rỗng là xâu không có chữ cái nào, độ dài của xâu rỗng bằng không, xâu rỗng đƣợc ký hiệu là . 8 Phạm Hùng Phú
  9. Chương 1. Tổng quan về Ngôn ngữ và Automat Xâu x  đƣợc gọi là xâu con của xâu w nếu x đƣợc tạo từ các ký tự nằm liền kề nhau trong xâu w. Tiền tố của xâu w là một xâu con bất kỳ nằm ở đầu xâu w. Hậu tố của xâu w là một xâu con bất kỳ nằm ở cuối xâu w. Ví dụ: cho các xâu w = abc và x = de trên bảng chữ cái La tinh; - |w| = 3; |x| = 2. - Các xâu a, b, c, ab, bc, abc là các xâu con của xâu w. - Các xâu a, ab, abc là các tiền tố của xâu w. - Các xâu c, bc, abc là các hậu tố của xâu w. 1.1.4. Các phép toán trên xâu 1) Phép nhân ghép hai xâu Cho hai xâu x = x1x2…xn và y = y1y2…ym trên bảng chữ cái , phép nhân ghép hai xâu x và y là phép cho ta một xâu xy = x1x2…xny1y2…ym trên bảng chữ cái  . Xâu xy đƣợc gọi là xâu ghép của hai xâu x và y. Nhƣ vậy, xâu ghép của hai xâu là một xâu đƣợc tạo ra bằng cách viết xâu thứ nhất, sau đó là xâu thứ hai (không có khoảng trống ở giữa). Ví dụ: Xâu ghép của hai xâu w = abc và u = de trên bảng chữ cái La Tinh là xâu wu = abcde và w = w = w. Ta ký hiệu: w0 = ; w1 = w; w2 = ww; ..., wi = wwi-1 với i > 0. 2) Phép đảo ngược xâu: Cho xâu w = a1a2…an trên bảng chữ cái , phép đảo ngƣợc xâu w là phép cho ta kết quả là một xâu trên bảng chữ cái , ký hiệu là wR và wR = anan-1…a2a1. Xâu wR đƣợc gọi là xâu đảo ngƣợc của xâu w. Nhƣ vậy, xâu đảo ngƣợc của xâu w là một xâu đƣợc tạo ra từ xâu w bằng cách viết w theo thứ tự ngƣợc lại và hiển nhiên εR = ε. Phạm Hùng Phú 9
  10. Chương 1. Tổng quan về Ngôn ngữ và Automat 1.1.5. Ngôn ngữ (language) 1) Khái niệm ngôn ngữ Cho  là một bảng chữ cái, ký hiệu * là tập hợp tất cả các xâu trên  kể cả xâu rỗng, + là tập hợp tất cả các xâu trên  trừ xâu rỗng; nhƣ vậy, giữa * và + có mối liên hệ * = +  {} hay + = *- {}. Ví dụ:  = a, b, c; *= aabcc, aaaaa, cab,…. là các xâu trên bảng chữ cái .  = 0,1; * = e,0,1,00,01,10,11,000… là tập các xâu trên . + = 0,1,00,01,10,11,000… Ta quy ƣớc xâu dạng aaaa…a gồm n kí tự a ký hiệu là an. Cho bảng chữ cái , tập con bất kỳ của tập hợp * đƣợc gọi là ngôn ngữ (ngôn ngữ hình thức) trên bảng chữ cái . Ví dụ: Cho  = a; L = ai với a   và i  N thì L là ngôn ngữ trên bảng chữ cái . 2) Các phép toán trên ngôn ngữ Theo khái niệm ngôn ngữ thì ngôn ngữ L là một tập hợp. Ký hiệu |L| là số các xâu hay số phần tử của L; nếu |L| là một số hữu hạn thì nói rằng L là ngôn ngữ hữu hạn. Từ các ngôn ngữ cho trƣớc, ta có thể thu đƣợc các ngôn ngữ mới nhờ áp dụng các phép toán trên ngôn ngữ. Vì ngôn ngữ L là một tập hợp nên các phép toán hợp (union), giao (intersect), hiệu (difference) của lý thuyết tập hợp đều có thể áp dụng trên các ngôn ngữ của cùng một bảng chữ cái để thu đƣợc ngôn ngữ mới cũng trên bảng chữ cái đó. Tức là: - Cho  là bảng chữ cái. L1, L2 là hai ngôn ngữ trên  thì: L1  L2 = x xL1 hoặc x L2; 10 Phạm Hùng Phú
  11. Chương 1. Tổng quan về Ngôn ngữ và Automat L1  L2 = x xL1 và x L2; L1 - L2 = x xL1 và x L2 cũng là các ngôn ngữ trên . Ngoài ra, còn có một số phép toán thƣờng gặp khác nhƣ: - Phép lấy phần bù (complement): Phần bù của một ngôn ngữ L trên bảng chữ cái  là một ngôn ngữ trên , ký hiệu là L và đƣợc xác định nhƣ sau: L=-L * - Phép nhân ghép (concatenation): Tích ghép của hai ngôn ngữ L1và L2 trên bảng chữ cái Σ là một ngôn ngữ trên bảng chữ cái Σ và đƣợc xác định nhƣ sau: L1L2 = {w1w2 | w1L1 và w2  L2 } - Phép lặp (loop) Cho L là ngôn ngữ trên bảng chữ cái . Ký hiệu: L0 = , ở đây  ký hiệu cho từ rỗng, đó là từ không chứa ký hiệu nào của bảng chữ cái, hay là từ có độ dài bằng 0. L1 = L; L2 = L1L; L3 = L2L, ... Tổng quát: ký hiệu Li = Li-1L với i = 1, 2, …, n - Phép lấy bao đóng (closure) + Bao đóng dƣơng (positive)  L+ = L1  L2  L3 … =  Li với mọi n > 0; có thể coi L+ là tập tất cả i 1 các xâu có độ dài hữu hạn và khác không. + Bao đóng kleene  L* =  Li với mọi n  0; nhƣ vậy, L* là tập tất cả các xâu có độ dài hữu hạn. i 1 Chú ý: L+ = LL* = L*L = L* - {ε}. L* = L+  {ε}. Hiển nhiên, lặp, bao đóng của một ngôn ngữ L trên bảng chữ cái Σ là một ngôn ngữ trên bảng chữ cái Σ. Phạm Hùng Phú 11
  12. Chương 1. Tổng quan về Ngôn ngữ và Automat Ví dụ: Cho ngôn ngữ L = { a, ba } thì: - L2 = {aa, aba, baa, baba}; - L3 = { aaa, aaba, abaa, ababa, baaa, baaba, babaa, bababa}; - L* = { ε, a, ba, aa, aba, baa, baba, aaa, aaba, abaa, ababa, baaa, baaba, … }. 3) Biểu diễn ngôn ngữ Ta biết rằng một ngôn ngữ L trên một bảng chữ cái Σ là một tập con của tập Σ*. Vậy vấn đề đặt ra là đối với một ngôn ngữ L, làm thế nào có thể chỉ rõ các xâu có thuộc vào L hay không ?. Đó chính là vấn đề biểu diễn ngôn ngữ. Để biểu diễn ngôn ngữ, ta có thể: - Liệt kê: + Liệt kê hết: Đối với một ngôn ngữ hữu hạn, số lƣợng xâu của nó có ít, để biểu diễn nó, một cách đơn giản, ta chỉ cần liệt kê tất cả các xâu thuộc vào ngôn ngữ đó. Ví dụ: L1 = {ε} L2 = { a, ba, aaba, bbbbb } + Liệt kê không hết hết: Liệt kê một số xâu của ngôn ngữ và có ám chỉ quy luật để tìm các xâu khác. Ví dụ: L1 = { ε, a, aa, aaa, aaaa, ... } L 2 = { ε, ab, aabb, aaabbb, ... } - Chỉ ra tính chất đặc trƣng: Trong trƣờng hợp một ngôn ngữ là vô hạn hoặc không thể liệt kê đƣợc tất cả các xâu thuộc vào ngôn ngữ đó. Trong những trƣờng hợp không phức tạp lắm, ngƣời ta thƣờng phải tìm ra tính chất đặc trƣng chung của các xâu và xác định các xâu bằng cách chỉ rõ tính chất đặc trƣng của các xâu đó. Tính chất đặc trƣng này thƣờng đƣợc mô tả thông qua một vị từ. Ví dụ: L1 = { ai | i là một số nguyên tố } L2 = { ai bi | i ≥ 0 } L3 = { ai bj | i ≥ j ≥ 0 } - Trong phần lớn các trƣờng hợp, ngƣời ta thƣờng biểu diễn ngôn ngữ một cách tổng quát thông qua một văn phạm hoặc một automat. Văn phạm là cơ chế hay 12 Phạm Hùng Phú
  13. Chương 1. Tổng quan về Ngôn ngữ và Automat công cụ cho phép sản sinh ra mọi xâu của một ngôn ngữ; trong khi đó automat lại là cơ chế hay công cụ cho phép đoán nhận một xâu bất kỳ có thuộc ngôn ngữ hay không. Về mặt hình thức, cả văn phạm và automat đều là cách biểu diễn khác nhau của ngôn ngữ. Ví dụ: Cho L là một ngôn ngữ trên bộ chữ cái Σ = {a, b} đƣợc định nghĩa nhƣ sau: - εL (1) - Nếu w  L thì awb  L (2) - Không còn xâu nào khác thuộc L (3) Định nghĩa đệ quy trên cho ta một cách sản sinh ra các xâu thuộc ngôn ngữ L nhƣ sau: Do (1) nên ta có xâu đầu tiên trong L là ε. Xem đó là w thì theo (2) ta lại có đƣợc xâu thứ hai aεb hay ab. Áp dụng lặp đi lặp lại quy tắc (2) ta lại tìm đƣợc các xâu: aabb, rồi lại aaabbb, … Cứ nhƣ thế có thể phát sinh tất cả các xâu thuộc ngôn ngữ L. Bằng cách áp dụng (một số hữu hạn) quy tắc phát sinh nhƣ trên, ta có thể phát sinh bất kỳ xâu nào trong ngôn ngữ. Dễ dàng nhận thấy: L = {ai bi | i ≥ 0}. Trong giáo trình này, các chƣơng sau sẽ tập trung nghiên cứu hai công cụ dùng để biểu diễn ngôn ngữ, nhƣ đã nói ở trên, đó là văn phạm và automat, bằng cách ấn định các dạng khác nhau vào các công cụ để có thể đƣa ra đƣợc nhiều loại văn phạm và automat khác nhau, từ đơn giản đến phức tạp và cũng sẽ nghiên cứu các ngôn ngữ đƣợc sinh bởi văn phạm hoặc đƣợc đoán nhận bởi automat và mối liên quan của chúng với nhau. 1.2. Văn phạm và ngôn ngữ 1.2.1. Văn phạm Một công cụ để mô tả ngôn ngữ là văn phạm. Đây là công cụ có định nghĩa toán học chặt chẽ, đƣợc các nhà toán học nghiên cứu kỹ và trở thành một thành phần quan trọng, chính yếu của lý thuyết ngôn ngữ. 1) Định nghĩa Văn phạm G là một hệ thống gồm bốn thành phần đƣợc xác định nhƣ sau: G = (N, T, P, S) trong đó: Phạm Hùng Phú 13
  14. Chương 1. Tổng quan về Ngôn ngữ và Automat + N – Là một tập hữu hạn các ký hiệu không kết thúc (Nonterminal) hay tập các biến (variables). + T – Là tập hữu hạn các ký hiệu kết thúc hay ký hiệu cuối (Terminal) với N T = . + P – Là tập hữu hạn các quy tắc sinh hay còn đƣợc gọi là luật sinh. Nói một cách khác P là một ánh xạ từ tập (N  T) + sang tập (N  T)* P: (N  T)+ → (N  T)* α  β Giả sử α  (N  T)+, β (N  T)* và β là ảnh của α qua ánh xạ P, khi đó cặp (α, β) là một luật sinh và đƣợc ký hiệu là α  β. + SN - là ký hiệu chƣa kết thúc đặc biệt dùng làm ký hiệu bắt đầu (start). Ví dụ: Văn phạm G = (N, T, P, S) trong đó: - N = {S}; - T = {a, b}; - P = {S1  aS1b; S1  }; - S = S. 2) Quy ước - Các chữ cái La Tinh viết hoa (A, B, C, ...) để chỉ các ký hiệu trong tập ký hiệu không kết thúc N; Chữ cái in hoa nằm ở vế trái của luật sinh đầu tiên là ký tự khởi đầu của văn phạm. - Các chữ cái viết thƣờng ở đầu bảng chữ cái La Tinh (a, b, c, ...) hoặc các chữ số để chỉ các ký hiệu kết thúc thuộc tập ký hiệu kết thúc T. - Các chữ cái viết thƣờng ở cuối bảng chữ cái La Tinh (x, y, z, w, ...) để chỉ xâu các ký hiệu kết thúc. Nhận xét: Bằng quy ƣớc này có thể suy ra đƣợc các ký hiệu không kết thúc, các ký hiệu kết thúc và ký hiệu bắt đầu của văn phạm một cách xác định và duy nhất bằng cách xem xét các luật sinh. Vì vậy, để biểu diễn một văn phạm, một cách đơn giản ngƣời ta chỉ cần liệt kê tập các luật sinh mà không cần chỉ rõ đầy đủ các thành phần của của văn phạm. 14 Phạm Hùng Phú
  15. Chương 1. Tổng quan về Ngôn ngữ và Automat 1.2.2. Ngôn ngữ sinh bởi Văn phạm 1) Dẫn xuất Nếu α → β là một luật sinh thì γ α δ  γ β δ đƣợc gọi là một dẫn xuất (trực tiếp), có nghĩa là áp dụng luật sinh α → β vào xâu γ α δ để sinh ra xâu γ β δ. Nếu các xâu α , α , ...., α  (NT)* và α  α , α  α , ..., α  α thì ta nói 1 2 m 1 2 2 3 m-1 m rằng: α đƣợc suy dẫn ra từ α thông qua dãy dẫn xuất α  α , α  α , ..., α α m 1 1 2 2 3 m-1 m hay α dẫn xuất (gián tiếp) ra α . 1 m Ký hiệu: - α i  α là dẫn xuất qua i bƣớc; 1 m - α * α là dẫn xuất qua không, một hoặc nhiều bƣớc; 1 m - α + α là dẫn xuất qua một hoặc nhiều bƣớc. 1 m 2) Ngôn ngữ sinh bởi văn phạm Ngôn ngữ sinh bởi văn phạm G = (N, T, P, S) là tập hợp các xâu w  T* đƣợc dẫn xuất ra từ ký hiệu bắt đầu S của văn phạm bởi các luật sinh thuộc tập P và đƣợc ký hiệu là L(G). Nhƣ vậy: L (G) = {w | w  T* và S * w} . Ví dụ: 1. Cho G = (N, T, P, S) Với N = S, T = a P = S  aaa, S  aaaS Khi đó L(G) = a3i iN 2. Cho văn phạm G = (N, T, P, S) với: N = S, T = 0,1; P = S  0S1; S  01; Ta có nhận xét mọi dãy dẫn xuất có thể có trong G phải có dạng: S  0S1  00S11  … 0i S1i Từ đây suy ra L(G) =  0i1i  i  1 Phạm Hùng Phú 15
  16. Chương 1. Tổng quan về Ngôn ngữ và Automat 1.2.3. Văn phạm tƣơng đƣơng Cho hai văn phạm G1 = (N1, T, P1, S1) và G2 = (N2, T, P2, S2), ta nói rằng G1 tƣơng đƣơng với G2 , ký hiệu là G1  G2 nếu L(G1) = L(G2). Nói cách khác hai văn phạm đƣợc gọi là tƣơng đƣơng nếu chúng sinh ra cùng một ngôn ngữ. Ví dụ: Cho văn phạm G1 = (N1, T1, P1, S1) trong đó: N1 = {S1}; T1 = {a, b}; P1 = {S1  aS1b; S1  }. Ta thấy ngay L(G1) = {anbn | n  0}. Và G2 = (N2, T2, P2, S2) trong đó: N2 = {S2};T2 = {a, b}; P2 = {S2  aS2b; S2  ab; S2  }. Ta cũng thấy ngay L(G2) = {anbn | n  0} Nhƣ vậy, G1 và G2 là hai văn phạm tƣơng đƣơng. 1.3. Phân loại văn phạm và ngôn ngữ Ở trên đã xem xét văn phạm là một công cụ để sinh ra ngôn ngữ, tiếp theo ta sẽ xem xét các vấn đề liên quan đến câu hỏi có bao nhiêu loại ngôn ngữ ?. Quan hệ giữa chúng nhƣ thế nào ?. Liên quan đến các câu hỏi trên đã có nhiều nhà khoa học đƣa ra cách phân loại khác nhau, song một cách phân loại đƣợc coi là tốt nhất, phù hợp với mục đích nghiên cứu là cách phân loại của nhà toán học Chomsky. Chomsky đƣa ra cách phân loại ngôn ngữ dựa vào các quy tắc sinh và đƣợc sử dụng nhƣ là cách phân loại chủ yếu trong lý thuyết ngôn ngữ hình thức. 1.3.1. Văn phạm và ngôn ngữ loại 0 Văn phạm G đƣợc gọi là văn phạm loại 0 nếu các quy tắc sinh của nó không có bất kỳ một điều kiện ràng buộc nào. Văn phạm loại 0 còn có tên gọi là văn phạm ngữ cấu hay văn phạm không hạn chế (Unrestricted Grammar). Ngôn ngữ sinh bởi văn phạm loại 0 đƣợc gọi là ngôn ngữ loại 0. 16 Phạm Hùng Phú
  17. Chương 1. Tổng quan về Ngôn ngữ và Automat 1.3.2. Văn phạm và ngôn ngữ loại 1 Văn phạm G đƣợc gọi là văn phạm loại 1 nếu các quy tắc sinh của nó có dạng:    , với điều kiện (NT)+ và      Văn phạm loại 1 còn đƣợc gọi là văn phạm cảm ngữ cảnh (Context Sensitive Grammar - CSG). Ngôn ngữ sinh bởi văn phạm loại 1 đƣợc gọi là ngôn ngữ loại 1 và còn đƣợc gọi là ngôn ngữ cảm ngữ cảnh (CSL). 1.3.3. Văn phạm và ngôn ngữ loại 2 Văn phạm G đƣợc gọi là văn phạm loại 2 nếu các quy tắc sinh của nó có dạng:   ; với N (NT)*. Văn phạm loại 2 còn đƣợc gọi là văn phạm phi ngữ cảnh (Context free Grammar - CFG). Ngôn ngữ sinh bởi văn phạm loại 2 đƣợc gọi là ngôn ngữ loại 2 và còn đƣợc gọi là ngôn ngữ phi ngữ cảnh (CFL). 1.3.4. Văn phạm và ngôn ngữ loại 3 Văn phạm G đƣợc gọi là văn phạm loại 3 nếu mọi quy tắc sinh của nó có một trong hai dạng: 1. A  Bw hoặc A  w (văn phạm tuyến tính trái); 2. A  wB hoặc A  w (văn phạm tuyến tính phải). * Trong đó: A, BN và wT . Văn phạm loại 3 còn đƣợc gọi là văn phạm chính quy (Regular Grammar - RG). Ngôn ngữ sinh bởi văn phạm loại 3 đƣợc gọi là ngôn ngữ loại 3 và còn đƣợc gọi là ngôn ngữ chính quy (RL). Chú ý: Từ cách phân loại trên ta có nhận xét: Văn phạm loại 3 cũng là văn phạm loại 2; văn phạm loại 2 cũng là văn phạm loại 1; văn phạm loại 1 cũng là văn phạm loại 0. Tức là: G3  G2  G1  G0. Từ đây suy ra nhận xét trên cũng đúng với các loại ngôn ngữ. Tức là: L3  L2  L1  L0 . Phạm Hùng Phú 17
  18. Chương 1. Tổng quan về Ngôn ngữ và Automat 1.3.5. Ví dụ 1) Xét văn phạm G = (N, T, P, S): a) - N = {S, A}; - T = {a, b}; - S = S; - P = {S → aS; S → aA; A → bA; A → b} Đây là văn phạm loại 3 (vì tập luật sinh có dạng tuyến tính phải). Chẳng hạn, một dẫn xuất từ S có dạng: 3 4 S  aS  aaS  aaaA  aaabA  aaabbA  aaabbbA  aaabbbb = a b m n Hay văn phạm sinh ra ngôn ngữ L(G) = {a b | m, n ≥ 1} b) - N = {S}; - T = {a, b}; - S = S; - P: S → abS  a là văn phạm tuyến tính phải. c) - N = {S, A, B}; - T = {a, b}; - S = S; - P: S → Aab; A → Aab B; B → a   là văn phạm tuyến tính trái. 2) Xét văn phạm G = (N, T, P, S): N = {S}; T = {a, b}; P = { S → aSb; S → ab } Đây là văn phạm loại 2 (CFG). Chẳng hạn, một dẫn xuất từ S có dạng: 4 4 S  aSb  aaSbb  aaaSbbb  aaaabbbb = a b n n Hay văn phạm sinh ra ngôn ngữ L(G ) = {a b | n ≥ 1} 2 18 Phạm Hùng Phú
  19. Chương 1. Tổng quan về Ngôn ngữ và Automat 3) Xét văn phạm G = (N, T, P, S): N = {S, B, C}; T = {a, b, c}; P = { S → aSBC; S → aBC; CB → BC; aB →ab; bB → bb; bC → bc; cC → cc}. Đây là văn phạm loại 1 (CSG). Chẳng hạn, một dẫn xuất từ S có dạng: S  aSBC  aaBCBC  aabCBC  aabBCC  aabbCC  aabbcC 2 2 2  aabbcc = a b c n n n Hay văn phạm sinh ra ngôn ngữ L(G ) = {a b c | n > 0}. 1 4) Xét văn phạm G = (N, T, P, S): N = {S, A}; T = {a, b, c}; S = S; P: SA → a; S → bcA; acS → cA. Đây là văn phạm loại 0. 1.4. Một số tính chất của ngôn ngữ Bản chất của ngôn ngữ là tập hợp vì vậy ngôn ngữ mang đầy đủ các tính chất của tập hợp, mặt khác ngôn ngữ lại đƣợc sinh ra bởi văn phạm vì vậy cần phải xem xét ngoài các tính chất của tập hợp ngôn ngữ còn có thêm những tính chất gì ?. Phần này sẽ trình bày một số tính chất của ngôn ngữ do văn phạm sinh ra. 1.4.1. Tính chất 1 Loại của ngôn ngữ đóng với phép hợp. Nói cách khác, tính chất 1 khẳng định rằng hợp của 2 ngôn ngữ cùng loại là ngôn ngữ cùng loại. Giả sử cho 2 văn phạm cùng loại G1 = (N1, T, P1, S1), G2 = (N2, T, P2, S2), văn phạm G1, G2 tƣơng ứng sinh ra ngôn ngữ L1, L2. Giả sử L = L1  L2 ta cần chứng minh: L là ngôn ngữ đƣợc sinh ra bởi văn phạm G cùng loại với văn phạm G 1, G2. Điều đáng lƣu ý ở đây là hai văn phạm phải có cùng bảng chữ cái T thì việc xem xét mới có nghĩa. Phạm Hùng Phú 19
  20. Chương 1. Tổng quan về Ngôn ngữ và Automat Ta xây dựng văn phạm G = (N, T, P, S) thoả mãn 2 điều kiện: - G cùng loại với G1, G2; - G sinh ra L mà L = L1  L2. Muốn thế, ta lấy N = N1N2 S (S không thuộc N1, N2); P = P1P2 SS1, SS2. Với cách xây dựng G nhƣ trên rõ ràng G cùng loại với G1, G2. Bây giờ, ta cần chứng tỏ: L = L(G) = L1L2. Giả sử wL, theo định nghĩa S * w trong G, từ cách xây dựng P, bƣớc đầu tiên trong G chỉ có thể: S  S1* w hoặc S  S2 * w; nhƣng từ S1 * w hoặc S2 * w ta suy ra w  L1L2. Ngƣợc lại nếu w  L1  L2, khi đó w  L1 hoặc w L2. Theo định nghĩa suy ra S1 * w hoặc S2 * w. Nếu w  L1 có nghĩa là S1 * w . Suy ra S  S1 * w ; tức là S * w hay w  L, còn nếu w L2 có nghĩa là S2 * w. Suy ra S  S2 * w suy ra S * w hay w  L. 1.4.2 Tính chất 2 Loại của ngôn ngữ đóng với phép lặp. Tính chất 2 khẳng định rằng phép lặp của một ngôn ngữ là một ngôn ngữ cùng loại. Nghĩa là nếu M = L L…L = Li thì M là ngôn ngữ cùng loại với L. Ta có thể kiểm tra tính đúng đắn của các tính chất trên. 1.4.3. Tính chất 3 Cho G = (N, T, P, S) không phải là văn phạm loại 0, có ký hiệu ban đầu S ở vế phải của quy tắc sinh khi đó tồn tại văn phạm G‟ cùng loại và tƣơng đƣơng với G không có ký hiệu bắt đầu ở vế phải của quy tắc sinh. Chứng minh: Giả sử cho G = (N, T, P, S) là văn phạm loại 1, hoặc loại 2, hoặc loại 3, ta xây dựng G‟= (N‟, T, P‟, S‟) nhƣ sau: N‟= N  S‟; ở đây S‟ là ký hiệu mới chƣa có trong N và T. P‟ = P  S‟  nếu S    P,   (NT)+ 20 Phạm Hùng Phú
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
5=>2