Ngôn ngữ hình thức và ngôn ngữ phi ngữ cảnh

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG

ĐINH THỊ KIM ANH

NGÔN NGỮ CHÍNH QUY

VÀ NGÔN NGỮ PHI NGỮ CẢNH

Chuyên ngành: Phương pháp toán sơ cấp

Mã số: 60.46.40

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Người hướng dẫn khoa học: PGS. TS. Nguyễn Gia Định

Đà Nẵng, Năm 2012

MỤC LỤC

Trang

Trang phụ bìa

Lời cam đoan

Mục lục

Danh mục các hình

Mở đầu ...........................................................................................................................1

Chương 1: Văn phạm và ngôn ngữ sinh bởi văn phạm ............................................4

1.1. Khái niệm ngôn ngữ ................................................................................................4

1.2. Văn phạm và ngôn ngữ sinh bởi văn phạm ...........................................................10

1.3. Một số tính chất của ngôn ngữ ..............................................................................19

Chương 2: Ôtômat hữu hạn và ngôn ngữ chính quy ..............................................28

2.1. Ôtômat hữu hạn đơn định. ......................................................................................29

2.2. Ôtômat hữu hạn không đơn định ............................................................................36

2.3. Quan hệ giữa ôtômat hữu hạn và ngôn ngữ chính quy ..........................................40

2.4. Biểu thức chính quy............................................................................................... 46

2.5. Cực tiểu hóa ôtômat hữu hạn .................................................................................50

Chương 3: Ôtômat đẩy xuống và cây suy dẫn của nó .............................................60

3.1. Văn phạm phi ngữ cảnh và cây suy dẫn của nó .................................................... 60

3.2. Dạng chuẩn Chomsky ............................................................................................72

3.3. Ôtômat đẩy xuống .................................................................................................75

Kết luận ........................................................................................................................86

Danh mục tài liệu tham khảo .....................................................................................87

Quyết định giao đề tài luận văn (bản sao)

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi.

Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công

bố trong bất kì công trình nào khác.

Tác giả luận văn

Đinh Thị Kim Anh

DANH MỤC CÁC HÌNH

Số hiệu hình Tên hình Trang

1.1 Cây phân tích cú pháp 14

2.1 Đồ thị chuyển của A1, A2 32

2.2 Đồ thị chuyển của A 33

2.3 Đồ thị chuyển của A’ 33

2.4 Cây đoán nhận  37

2.5 Đồ thị chuyển của A 38

2.6 Đồ thị chuyển của A 39

2.7 Đồ thị chuyển của A 39

2.8 Đồ thị chuyển của A 41

2.9 Đồ thị chuyển của A’ 41

2.10 Đồ thị chuyển của A’’ 42

2.11 Đồ thị chuyển của A 43

2.12 Đồ thị chuyển của A 44

2.13 Đồ thị chuyển của L 44

2.14 Đồ thị chuyển của A 47

2.15 Đồ thị chuyển của A 49

2.16 Đồ thị chuyển của A 49

2.17 Đồ thị chuyển của A 53

2.18 Đồ thị chuyển của M 54

2.19 Đồ thị chuyển của A 58

2.20 Đồ thị chuyển của M 59

3.1 Cây suy dẫn của từ trong G1 61

3.2 Cây suy dẫn của từ trong G3 61

3.3 Cây suy dẫn của từ trong G2 62

3.4 Cây suy dẫn của từ trong G4 62

3.5 Cây suy dẫn của từ trong G

6

5

3.6 Mô hình của một ôtômat đẩy xuống

7

5

3.7 Cây biểu diễn các khả năng biến đổi 81

3.8 Đồ thị chuyển của

M 81

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM

Độc lập - Tự do – Hạnh phúc



LÝ LỊCH KHOA HỌC

I. LÝ LỊCH SƠ LƯỢC:

Họ và tên: Đinh Thị Kim Anh. Giới tính: Nữ.

Ngày, tháng, năm sinh: 03/01/1987. Nơi sinh: Đà Nẵng.

Quê quán: Điện Dương, Điện Bàn, Quảng Nam. Dân tộc: Kinh

Chức vụ, đơn vị công tác trước khi đi học tập, nghiên cứu:

Chỗ ở riêng hoặc địa chỉ liên lạc: Đường Suối Đá 3, Sơn Trà, Đà Nẵng

Điện thoại : 0905643501

E-mail: [email protected]

II. QUÁ TRÌNH ĐÀO TẠO:

1. Đại học:

Hệ đào tạo: Chính quy tập trung . Thời gian đào tạo: từ 2005 đến 2009.

Nơi học (trường, thành phố): Trường Đại học Sư Phạm – Đại học Đà Nẵng.

Ngành học: Sư phạm Toán – Tin.

Tên đồ án, luận văn hoặc môn thi tốt nghiệp:

Ngày và nơi bảo vệ đồ án, luận văn hoặc thi tốt nghiệp:

Người hướng dẫn:

2. Thạc sĩ:

Hệ đào tạo: Chính quy không tập trung . Thời gian đào tạo: từ 2010 đến 2012.

Nơi học (trường, thành phố): Đại học Đà Nẵng.

Ngành học: Phương pháp toán sơ cấp.

Tên luận văn: Ngôn ngữ chính quy và ngôn ngữ phi ngữ cảnh.

Ngày và nơi bảo vệ luận văn: Ngày 1/7/2012 tại Đại Học Đà Nẵng.

Người hướng dẫn: PGS. TS. Nguyễn Gia Định.

3. Trình độ ngoại ngữ ( biết ngoại ngữ gì, mức độ): Tiếng Anh

Tôi xin cam đoan những lời khai ở trên là đúng sự thật, nếu có gì sai xót tôi xin chịu

hoàn toàn trách nhiệm

Đà Nẵng, ngày 16 tháng 6 năm 2012

Người khai ký tên

Đinh Thị Kim Anh

MỞ ĐẦU

1. Lý do chọn đề tài

Mấy chục năm gần đây, chúng ta đã chứng kiến sự phát triển mãnh liệt trong

các lĩnh vực nghiên cứu toán học liên quan đến máy tính và tin học. Sự phát triển

phi thường của các máy tính và những thay đổi sâu sắc trong phương pháp luận

khoa học đã mở ra những chân trời mới cho toán học với một tốc độ không thể sánh

được trong suốt lịch sử lâu dài của toán học. Những phát triển đa dạng của toán học

đã trực tiếp tạo ra “thuở ban đầu” của máy tính và tin học và các tiến bộ trong tin

học đã dẫn đến sự phát triển rất mạnh mẽ một số ngành toán học.

Vì vậy, toán học đóng vai trò trung tâm trong các cơ sở của tin học. Có thể

kể ra một số lĩnh vực nghiên cứu đáng chú ý trong mối quan hệ này. Thật là thú vị

khi nhận thấy rằng các lĩnh vực này cũng phản ánh sự phát triển lịch sử của tin học.

1. Lý thuyết kinh điển về tính toán bắt đầu bằng công trình của Gödel, Tarski,

Church, Post, Turing và Kleene chiếm vị trí trung tâm.

2. Trong lý thuyết ôtômat và ngôn ngữ hình thức kinh điển, các khái niệm cơ bản là

ôtômat, văn phạm và ngôn ngữ, với các công trình sáng giá của Axel Thue,

Chomsky, Post.

Ngoài hai lĩnh vực trên, nhiều lĩnh vực quan trọng khác thuộc về các cơ sở

toán học của tin học; chẳng hạn, lý thuyết độ phức tạp, ngữ nghĩa và lý thuyết về

tính đúng đắn của các ngôn ngữ lập trình, lý thuyết mật mã, lý thuyết các cấu trúc

dữ liệu và lý thuyết các cơ sở dữ liệu.

Lý thuyết ngôn ngữ hình thức và ôtômat đóng một vai trò rất quan trọng

trong các cơ sở toán học của tin học. Ngôn ngữ hình thức được sử dụng trong việc

xây dựng các ngôn ngữ lập trình, lý thuyết về các chương trình dịch. Các ngôn ngữ

hình thức tạo thành một công cụ mô tả đối với các mô hình tính toán cả cho dạng

thông tin vào-ra lẫn kiểu thao tác. Lý thuyết ngôn ngữ hình thức, chính vì thực chất

của nó là một lĩnh vực khoa học liên ngành; nhu cầu mô tả hình thức văn phạm

được phát sinh trong nhiều ngành khoa học khác nhau từ ngôn ngữ học đến sinh

học.Từ ngàn xưa con người muốn giao tiếp với nhau phải dùng ngôn ngữ. Ngôn

ngữ để con người có thể giao tiếp với nhau được gọi là ngôn ngữ tự nhiên, chẳng

hạn như tiếng Anh, tiếng Nga, tiếng Việt là các ngôn ngữ tự nhiên. Con người muốn

giao tiếp với máy tính tất nhiên cũng thông qua ngôn ngữ. Con người muốn máy

tính thực hiện công việc, phải viết các yêu cầu đưa cho máy bằng ngôn ngữ máy

hiểu được. Việc viết các yêu cầu ta gọi là lập trình. Ngôn ngữ dùng để lập trình

được gọi là ngôn ngữ lập trình.

Cả ngôn ngữ lập trình lẫn ngôn ngữ tự nhiên đều có thể xem như những tập

các từ, tức là các xâu hữu hạn các phần tử của một bộ chữ cái cơ sở nào đó. Về mặt

truyền thống, lý thuyết ngôn ngữ hình thức liên quan đến các đặc tả cú pháp của

ngôn ngữ nhiều hơn là đến những vấn đề ngữ nghĩa. Một đặc tả về cú pháp của một

ngôn ngữ có hữu hạn từ, ít nhất về nguyên tắc, có thể được cho bằng cách liệt kê

các từ. Điều đó không thể áp dụng đối với các ngôn ngữ có vô hạn từ. Nhiệm vụ

chính của lý thuyết ngôn ngữ hình thức là nghiên cứu các cách đặc tả hữu hạn của

các ngôn ngữ vô hạn. Hai ngôn ngữ quan trọng nhất là ngôn ngữ chính quy và ngôn

ngữ phi ngữ cảnh, các ngôn ngữ lập trình thuộc loại hai ngôn ngữ này, vì vậy người

ta tập trung nghiên cứu hai loại ngôn ngữ này và các bộ đoán nhận chúng.

Xuất phát từ nhu cầu phát triển của lý thuyết ngôn ngữ hình thức và những

ứng dụng của nó, chúng tôi quyết định chọn đề tài với chủ đề: Ngôn ngữ hình thức

và ngôn ngữ phi ngữ cảnh để tiến hành nghiên cứu. Chúng tôi hy vọng đây là một

tài liệu tham khảo tốt cho những người bắt đầu tìm hiểu về Lý thuyết ngôn ngữ hình

thức và ôtômat và trình bày một số ví dụ minh hoạ đặc sắc nhằm góp phần làm

phong phú thêm các kết quả trong lĩnh vực này.

2. Mục tiêu nghiên cứu

Mục tiêu của đề tài nhằm nghiên cứu ngôn ngữ chính quy và ôtômat hữu hạn

đoán nhận nó, ngôn ngữ phi ngữ cảnh và ôtômat đẩy xuống đoán nhận nó.

3. Đối tượng và phạm vi nghiên cứu

Đối tượng nghiên cứu của đề tài là ngôn ngữ chính quy và ngôn ngữ phi ngữ

cảnh. Phạm vi nghiên cứu của đề tài là lý thuyết ngôn ngữ, ôtômat hữu hạn và sự

đoán nhận của nó đối với lớp ngôn ngữ chính quy, ôtômat đẩy xuống và sự đoán

nhận của nó đối với lớp ngôn ngữ phi ngữ cảnh.

4. Phương pháp nghiên cứu

1. Thu thập các bài báo khoa học và tài liệu của các tác giả nghiên cứu liên

quan đến ngôn ngữ hính thức và ôtômat, đặc biệt là ngôn ngữ chính quy và ngôn

ngữ phi ngữ cảnh.

2. Tham gia các buổi seminar của thầy hướng dẫn để trao đổi các kết quả đang

nghiên cứu.

5. Đóng góp của đề tài

1. Tổng quan các kết quả của các tác giả đã nghiên cứu liên quan đến ngôn

ngữ chính quy và ngôn ngữ phi ngữ cảnh, các ôtômat đoán nhận chúng nhằm xây

dựng một tài liệu tham khảo cho những ai muốn nghiên cứu Lý thuyết ngôn ngữ

hình thức và ôtômat.

2. Chứng minh chi tiết và làm rõ một số mệnh đề, cũng như đưa ra một số ví

dụ minh hoạ đặc sắc nhằm làm cho người đọc dễ dàng tiếp cận vấn đề được đề cập.

6. Bố cục luận văn

Ngoài các phần mở đầu, kết luận, tài liệu tham khảo, phần nội dung chính của

luận văn gồm 3 chương:

-- Trong Chương 1, chúng tôi trình bày khái niệm ngôn ngữ, văn phạm, ngôn ngữ

sinh bởi văn phạm và một số tính chất của ngôn ngữ.

-- Trong Chương 2, chúng tôi khảo sát ôtômat hữu hạn, mối quan hệ giữa ôtômat

hữu hạn và ngôn ngữ chính quy, mối quan hệ giữa biểu thức chính quy và ngôn ngữ

chính quy, cực tiểu hóa ôtômat hữu hạn.

-- Ôtômat đẩy xuống và ngôn ngữ phi ngữ cảnh được đề cập trong Chương 3. Cụ

thể là văn phạm phi ngữ cảnh và cây suy dẫn của nó, ôtômat đẩy xuống và mối quan

hệ giữa nó và ngôn ngữ phi ngữ cảnh.

CHƯƠNG 1

VĂN PHẠM VÀ NGÔN NGỮ SINH BỞI VĂN PHẠM

Các khái niệm và kết quả trong chương này có thể tìm thấy trong các tài liệu

[2], [3], [6], [8].

1.1. KHÁI NIỆM NGÔN NGỮ

Ngôn ngữ là phương tiện giao tiếp. Sự giao tiếp ở đây có thể là sự giao tiếp

giữa người với nhau hoặc giữa người và máy, hoặc giữa máy và máy. Ngôn ngữ để

con người có thể giao tiếp với nhau được gọi là ngôn ngữ tự nhiên, chẳng hạn như

tiếng Anh, tiếng Nga, tiếng Việt là các ngôn ngữ tự nhiên. Như chúng ta đã biết các

quy tắc cú pháp của ngôn ngữ tự nhiên rất phong phú, đa dạng, phức tạp. Tuy nhiên,

những yêu cầu nghiêm ngặt về ngữ nghĩa trong các ngôn ngữ tự nhiên chưa cao,

chẳng hạn như cùng một từ hoặc cùng một câu ta có thể hiểu chúng theo những

nghĩa khác nhau tùy theo những ngữ cảnh cụ thể. Để có sự giao tiếp giữa người và

máy, hoặc giữa máy và máy cần phải có một ngôn ngữ mà các quy tắc cú pháp chặt

chẽ hơn, nói cách khác là với một từ hoặc một câu thì nghĩa của chúng phải là duy

nhất. Những ngôn ngữ như thế được gọi là ngôn ngữ hình thức.

Để xây dựng một ngôn ngữ hình thức cần có một tập hợp hữu hạn khác rỗng

các ký hiệu nào đó gọi là bảng chữ cái. Dãy hữu hạn các phần tử của bảng chữ cái

được gọi là một từ hay xâu trên bảng chữ cái. Một tập hợp các từ trên bảng chữ cái

được gọi là một ngôn ngữ.

Định nghĩa 1.1.1. Một bảng chữ cái (hay đơn giản là bảng chữ) là một tập hữu

hạn khác rỗng. Mỗi phần tử của một bảng chữ cái  được gọi là một chữ cái hay

một ký hiệu trên .

Ví dụ 1.1.1. -- Bảng chữ cái của ngôn ngữ tiếng Việt là 29 ký hiệu, cụ thể là

 = {a, b, c, d, đ…, y},

-- Để có các xâu nhị phân ta thường dùng bảng chữ cái gồm hai ký hiệu 0, 1;

tức là  = {0, 1}.

--  = {0, 1, 2, …, 8, 9} là bảng chữ cái thập phân.