Nghiên cứu Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata đẩy xuống

LỜI CẢM ƠN
Trước hết, em xin chân thành cảm ơn các thầy cô giáo trong khoa Công nghệ
thông tin Trường ĐH Kỹ thuật – Hậu cần CAND đã trang bị những kiến thức cơ
bản, cần thiết và quý báu để em thực hiện chuyên đề của mình.
Đặc biệt, em xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy Nghiêm
Văn Hưng, giáo viên giảng dạy, và thầy Cao Xuân Trường, người đã tận tình
hướng dẫn, chỉ bảo và tạo mọi điều kiện thuận lợi giúp em trong quá trình thực
hiện chuyên đề.
Mặc dù đã rất cố gắng cùng nhận được sự giúp đỡ tận tâm của thầy giáo
hướng dẫn, xong do trình độ còn hạn chế, tài liệu chưa được phong phú, và nội
dung này khá khó đối với em nên không tránh khỏi những thiếu sót trong quá trình
tiếp nhận kiến thức. Em rất mong nhận được sự quan tâm giúp đỡ, chỉ dẫn của thầy
cô và sự góp ý từ bạn bè để trong thời gian tới em có thể tiếp tục tìm hiểu và xây
dựng chuyên đề một cách hoàn thiện nhất.
Em xin chân thành cảm ơn!
https://dethithptquocgia.com/

GIỚI THIỆU TỔNG QUAN VỀ CHUYÊN ĐỀ
Tên chuyên đề: Nghiên cứu Ngôn ngữ hình thức, Văn phạm phi ngữ
cảnh và Automata đẩy xuống
Sinh viên thực hiện: Hoàng Văn Thao
Lớp: B3-D2B
Giáo viên hướng dẫn: Thiếu úy Cao Xuân Trường
Tính cấp thiết của chuyên đề:
Lý thuyết ngôn ngữ hình thức và Automata đó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 vật học. Do đó những khía
cạnh thích hợp của lý thuyết ngôn ngữ hình thức sẽ có tầm quan trọng quyết
định trong các giáo trình về Lý thuyết ngôn ngữ hình thức và Automata.
Lĩnh vực mà lý thuyết ngôn ngữ hình thức nghiên cứu là những mẫu
hình (pattern) có cấu trúc bên trong ngôn ngữ hình thức, và đó là những
khía cạnh hoàn toàn mang tính chất có cú pháp. Ngôn ngữ hình thức không
còn đơn giản chỉ là để định nghĩa ngôn ngữ tự nhiên, mà nó vượt ra ngoài
khỏi phạm vi đó và nó cũng là một cách để thể hiện được những quy tắc có
cú pháp của ngôn ngữ tự nhiên.
Mục tiêu của chuyên đề: Nghiên cứu tổng quan về văn phạm hình thức
và các Automata, là những công cụ sinh ngôn ngữ, đồng thời đề cập đến các
tính chất của ngôn ngữ chính quy, ngôn ngữ phi ngữ cảnh. Ngoài ra, cũng
giới thiệu sơ lược về Trình biên dịch, một phần quan trọng của học phần
Chương trình dịch gắn bó chặt chẽ với Lý thuyết ngôn ngữ hình thức và
Automata, trong đó Văn phạm phi ngữ cảnh là cơ sở lý thuyết để xây dựng
Bộ phân tích cú pháp, là thành phần quan trọng nhất trong một Trình biên
dịch.
Đối tượng nghiên cứu: Ngôn ngữ hình thức và lý thuyết Automata.
Phạm vi nghiên cứu:
 Ngôn ngữ phi ngữ cảnh cùng hai phương tiện để xác định chúng là
Văn phạm phi ngữ cảnh;
 Automata đẩy xuống.
https://dethithptquocgia.com/

Phương pháp nghiên cứu:
 Phương pháp nghiên cứu tài liệu;
 Phương pháp chuyên gia;
 Phương pháp thực nghiệm.
Nội dung nghiên cứu:
 Lý thuyết về Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata
đẩy xuống;
 Các tính chất của Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata
đẩy xuống;
 Ứng dụng của Ngôn ngữ hình thức và Automata với trình biên dịch.
Chuyên đề gồm 5 chương:
Chương I: Nhập môn về văn phạm và ngôn ngữ hình thức
1.1 Khái niệm ngôn ngữ
1.2 Văn phạm và ngôn ngữ sinh bởi văn phạm
1.3 Một số tính chất của ngôn ngữ
Chương II: Văn phạm phi ngữ cảnh
2.1 Suy dẫn phi ngữ cảnh
2.2 Biến đổi các Văn phạm phi ngữ cảnh
Chương III: Automata đẩy xuống
3.1 Automata đẩy xuống không tiền định
3.2 Automata đẩy xuống và Văn phạm phi ngữ cảnh
Chương IV: Tổng quan về trình biên dịch
4.1 Ngôn ngữ lập trình
4.2 Trình biên dịch
4.3 Ứng dụng của Văn phạm phi ngữ cảnh và Automata đẩy xuống với trình
biên dịch
Chương V: Demo một bài toán
5.1 Bài toán và cơ sở lý thuyết
5.2 Demo ví dụ về sự tương đương giữa BTCQ và NFAε
Sản phẩm:
 Báo cáo chuyên đề;
 Chương trình demo cơ bản.

https://dethithptquocgia.com/

MỤC LỤC
LỜI NÓI ĐẦU ................................................................................................................ 1
CHƯƠNG 1. NHẬP MÔN VỀ VĂN PHẠM VÀ NGÔN NGỮ HÌNH THỨC ........ 3
1.1. Khái niệm ngôn ngữ ............................................................................................. 3
1.1.1. Các khái niệm cơ bản .................................................................................... 3
1.1.2. Các phép toán trên các từ .............................................................................. 4
1.1.3. Các phép toán trên ngôn ngữ. ....................................................................... 6
1.2. Văn phạm và ngôn ngữ sinh bởi văn phạm .......................................................... 9
1.2.1. Định nghĩa văn phạm .................................................................................. 10
1.2.2. Ngôn ngữ sinh bởi văn phạm ...................................................................... 11
1.2.3. Phân loại văn phạm theo Chomsky ............................................................. 12
1.3. Một số tính chất của ngôn ngữ ........................................................................... 14
1.3.1. Một số tính chất của văn phạm và dẫn xuất................................................ 14
1.3.2. Tính đóng của lớp ngôn ngữ sinh bởi văn phạm ........................................ 14
CHƯƠNG 2. VĂN PHẠM PHI NGỮ CẢNH ........................................................... 17
2.1. Suy dẫn phi ngữ cảnh ......................................................................................... 17
2.1.1. Các thí dụ về văn phạm phi ngữ cảnh ......................................................... 17
2.1.2. Tính chất cơ bản (phân rã các suy dẫn phi ngữ cảnh) ................................ 19
2.1.3. Cây suy dẫn ................................................................................................. 20
2.1.4. Suy dẫn trái, suy dẫn phải và tính nhập nhằng ........................................... 23
2.2. Biến đổi các văn phạm phi ngữ cảnh ................................................................. 26
2.2.1. Loại bỏ các ký hiệu vô ích .......................................................................... 26
2.2.2. Loại bỏ các ε-sản xuất ................................................................................ 31
2.2.3. Loại bỏ các sản xuất đơn ............................................................................ 33
2.2.4. Dạng chuẩn Chomsky ................................................................................. 35
CHƯƠNG 3. Ô TÔ MÁT ĐẨY XUỐNG .................................................................. 37
3.1. Ô tô mát đẩy xuống không tiền định .................................................................. 37
3.1.1. Khái niệm và định nghĩa ............................................................................. 37
3.1.2. Các tính chất cơ bản của ô tô mát đẩy xuống ............................................. 38
3.1.3. Tương đương giữa hai loại ô tô mát đẩy xuống thừa nhận theo stack rỗng và
thừa nhận theo trạng thái cuối ....................................................................................... 41
3.2. Tương đương giữa ô tô mát đẩy xuống và văn phạm phi ngữ cảnh ............. 44
3.2.1. Từ văn phạm phi ngữ cảnh đến ô tô mát đẩy xuống .................................. 44
3.2.2. Từ ô tô mát đẩy xuống đến văn phạm phi ngữ cảnh .................................. 46 https://dethithptquocgia.com/

CHƯƠNG 4. TỔNG QUAN VỀ TRÌNH BIÊN DỊCH ............................................. 49
4.1. Ngôn ngữ lập trình ............................................................................................. 49
4.1.1. Mở đầu ........................................................................................................ 49
4.1.2. Phân loại ...................................................................................................... 49
4.1.3. Cú pháp và ngữ nghĩa ................................................................................. 50
4.2. Trình biên dịch ................................................................................................... 51
4.2.1. Định nghĩa ................................................................................................... 51
4.2.2. Các phần của trình biên dịch ....................................................................... 52
4.3. Ứng dụng của ngôn ngữ hình thức và ôtômat với trình biên dịch ..................... 57
4.3.1. Bộ tiền xử lý ................................................................................................ 57
4.3.2. Trình biên dịch hợp ngữ .............................................................................. 59
4.3.3. Trình biên dịch hợp ngữ hai chuyến (two pass assembler) ......................... 59
4.3.4. Bộ cất liên kết soạn thảo (loader/link editor): ............................................. 60
CHƯƠNG 5. DEMO MỘT BÀI TOÁN .................................................................... 63
5.1. Cơ sở lý thuyết ................................................................................................... 63
Bài toán chuyển từ BTCQ sang NFAε ....................................................... 63
Phương hướng giải quyết ............................................................................ 63
5.2. Demo ví dụ về sự tương đương giữa BTCQ và NFAε ...................................... 65
Giao diện ban đầu ....................................................................................... 65
Giao diện kết quả ........................................................................................ 66

KẾT LUẬN .................................................................................................................. 69
TÀI LIỆU THAM KHẢO ........................................................................................... 70

https://dethithptquocgia.com/

MỤC LỤC HÌNH
Hình 1.1 Cây dẫn xuất cho ví dụ ................................................................................... 12
Hình 2.1 Một cây suy dẫn .............................................................................................. 21
Hình 2.2 Một A-cây ....................................................................................................... 21
Hình 2.3 Một A-cây có một đỉnh trong ......................................................................... 22
Hình 2.4 Một A-cây và các cây con của nó ................................................................... 23
Hình 2.5 Một cây suy dẫn trong G0 ............................................................................... 24
Hình 2.6 Một cây suy dẫn khác của G0 ......................................................................... 25
Hình 2.7 Một cây suy dẫn của G1 .................................................................................. 26
Hình 2.8 Một cây suy dẫn của G1 .................................................................................. 26
Hình 4.1 Sơ đồ trình biên dịch ...................................................................................... 50
Hình 4.2 Sơ đồ trình thông dịch .................................................................................... 50
Hình 4.3 Cây cú pháp A ................................................................................................ 51
Hình 4.4 Cây cú pháp B ................................................................................................ 56
Hình 4.5 Sơ đồ hoạt động loader ................................................................................... 61
Hình 5.1 Giao diện làm việc của Demo ........................................................................ 65
Hình 5.2 Nhập BTCQ cần chuyển ................................................................................. 66
Hình 5.3 Kết quả là bảng biểu diễn một NFAε ............................................................. 67
Hình 5.4 Một cách biểu diễn khác của NFAε ............................................................... 68

MỤC LỤC BẢNG
Bảng IV.1 Bảng danh biểu 1 ............................................................................... 54
Bảng IV.2 Bảng danh biểu 2 ............................................................................... 60 https://dethithptquocgia.com/

1

LỜI NÓI ĐẦU
Ngôn ngữ là phương tiện để giao tiếp, sự giao tiếp có thể hiểu là giao tiếp
giữa con người với nhau, giao tiếp giữa người với máy, hay giao tiếp giữa máy
với 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. Các quy tắc cú pháp của ngôn ngữ tự nhiên nói chung rất phức tạp nhưng
các yêu cầu nghiêm ngặt về ngữ nghĩa thì lại thiếu chặt chẽ, chẳng hạn cùng
một từ hay cùng một câu ta có thể hiểu chúng theo những nghĩa khác nhau tùy
theo từng ngữ cảnh cụ thể. 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ữ. Để có sự giao tiếp giữa người với máy hay giữa máy
với nhau, cần phải có một ngôn ngữ với các quy tắc cú pháp chặt chẽ hơn so với
các ngôn ngữ tự nhiên, nói cách khác, với một từ hay một câu thì ngữ nghĩa của
chúng phải là duy nhất mà không phụ thuộc vào ngữ cảnh. Những ngôn ngữ
như thế được gọi là ngôn ngữ hình thức. 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 như thế 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ác ngôn ngữ lập trình đều là các ngôn ngữ hình thức.
Cả ngôn ngữ hình thức 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.
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 vật học.
Báo cáo này nhằm trình bày về văn phạm hình thức và ôtômat đẩy xuống,
là những công cụ sinh ngôn ngữ, đồng thời đề cập đến các tính chất của ngôn
ngữ chính quy, ngôn ngữ phi ngữ cảnh, ngôn ngữ đệ quy và ngôn ngữ đệ quy
đếm được. Ngoài ra cũng giới thiệu sơ lược về trình biên dịch, một phần quan
trọng của học phần Chương trình dịch/.
Chuyên đề gồm 8 phần chính:
Lời mở đầu: Giới thiệu về chuyên đề https://dethithptquocgia.com/

2

Chương I: Nhập môn về văn phạm và ngôn ngữ hình thức
Chương II: Văn phạm phi ngữ cảnh
Chương III: Automata đẩy xuống
Chương IV: Tổng quan về trình biên dịch
Chương V: Giới thiệu về chương trình Demo
Kết luận: Đưa ra một số đánh giá tổng quan về kết quả nghiên cứu, nêu
ra hướng phát triển trong thời gian tới.
Tài liệu tham khảo: Đưa ra các tài liệu đã được trích dẫn, tham khảo
khi thực hiện chuyên đề.
https://dethithptquocgia.com/

3

CHƯƠNG 1. NHẬP MÔN VỀ VĂN PHẠM VÀ NGÔN NGỮ HÌNH THỨC
1.1. Khái niệm ngôn ngữ
Các khái niệm cơ bản
1.1.1.1. Bảng chữ cái
Theo tài liệu [3], tác giả: Phan Đình Diệu, có viết “Một dãy hữu hạn hay vô
hạn các phần tử, kí hiệu  được gọi là một bảng chữ cái trong đó mỗi phần tử a
  được gọi là một kí hiệu (một chữ cái).”.
Từ đó ta có Định nghĩa I.1.
Định nghĩa I.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 tử a  được gọi là một chữ cái hay một ký hiệu.
Thí dụ 1.1:
Dưới đây là các bảng chữ cái:
 = {a, b, c, …, x, y, z},
Δ = {, , , , , , , , , , , , , , , , ,, },
Г = {0, 1},
W = {if, then, else, a, b, c, d, e, f, +, −, , /, =, }.
1.1.1.2. Từ
Định nghĩa I.2
Giả sử có bảng chữ cái  = {a
1, a
2, …, a
m}, một dãy các chữ cái α = a
i1 a
i2
… a
it, với a
ij   (1 ≤ j ≤ t) được gọi là một từ hay một xâu trên bảng chữ cái .
Tổng số vị trí của các ký hiệu xuất hiện trong xâu α được gọi là độ dài của
từ α và ký hiệu là | α |. Như vậy, một từ trên bảng chữ cái  là một xâu hữu hạn
gồm một số lớn hơn hay bằng không các chữ cái của , trong đó một chữ cái có
thể xuất hiện nhiều lần.
Xâu không có chữ cái nào được gọi là từ rỗng và được ký hiệu là . Rõ
ràng từ rỗng là từ thuộc mọi bảng chữ cái. Hai từ  = a
1a
2…a
n và  = b
1b
2…b
m
được gọi là bằng nhau, và được ký hiệu là  = , nếu n = m và ai = bi với mọi i
= 1, 2, …, n.
Nếu α là một từ trên bảng chữ cái , và   Δ thì α cũng là từ trên bảng chữ
cái Δ. Tập mọi từ trên bảng chữ cái  được ký hiệu là 
*,
còn tập mọi từ khác
rỗng trên bảng chữ cái  được ký hiệu là 
+
. Như vậy 
+
= 
*
\ {} và 
*
= 
+
 {}. Dễ thấy rằng các tập 
*
và 
+
là vô hạn. https://dethithptquocgia.com/

4

Về cấu trúc đại số thì 
*
là một vị nhóm tự do sinh bởi  với đơn vị
là từ rỗng , còn 
+
là một nửa nhóm tự do sinh bởi . Có thể chứng minh
được rằng các tập 
*
và 
+
là vô hạn đếm được.
Thí dụ 1.2:
Ta có  , 0, 01, 101, 1010, 110011 là các từ trên bảng chữ cái Г = {0,1}.
Các xâu , beautiful, happy, holiday là các từ trên bảng chữ cái  = {a, b, c,
…, z}.
1.1.1.3. Ngôn ngữ
Định nghĩa I.3
Cho bảng chữ cái , mỗt tập con L  
*
được gọi là một ngôn ngữ hình
thức (hay ngôn ngữ) trên bảng chữ cái .
Tập rỗng, ký hiệu , là một ngôn ngữ không gồm một từ nào và được
gọi là ngôn ngữ rỗng. Vậy ngôn ngữ rỗng là ngôn ngữ trên mọi bảng chữ
cái.
Chú ý rằng ngôn ngữ rỗng: L =  là khác với ngôn ngữ chỉ gồm một từ
rỗng: L = {}.
Thí dụ 1.3:
• 
*
là ngôn ngữ gồm tất cả các từ trên  còn 
+
là ngôn ngữ gồm tất
cả các từ khác từ trống trên .
• L = { , 0, 1, 01, 10, 00, 11, 011,100} là một ngôn ngữ trên bảng chữ
cái Г = {0, 1}.
• L = {a, b, c, aa, ab, ac, abc} là ngôn ngữ trên bảng chữ cái  = {a, b,
c}.
• L1 = {, a, b, abb, aab, aaa, bbb, abab}, L2 = {a
n
b
n
| n N} là hai
ngôn ngữ trên bảng chữ  = {a, b}, L1 là ngôn ngữ hữu hạn trong khi L2
là ngôn ngữ vô hạn. Mỗi từ thuộc ngôn ngữ L2 có số chữ cái a bằng số chữ
cái b với a và b không xen kẽ, a nằm ở phía trái và b ở phía phải của từ.
Các phép toán trên các từ
1.1.2.1. Phép nhân ghép
Theo tài liệu [5], tác giả: Nguyễn Văn Định, có viết “
Tích ghép (hay
nhân ghép) của hai từ α = a
1a
2…am và từ  = b
1b
2…b
n trên bảng chữ
cái
, là từ  = a
1a
2…a
mb
1b
2…bn trên bảng chữ cái .
Kí hiệu phép nhân ghép là  = α. (hay  = α).” https://dethithptquocgia.com/

5

Từ đó ta có Định nghĩa I.4.
Định nghĩa I.4
Tích ghép (hay nhân ghép) của hai từ α = a
1a
2…a
m và từ  =
b
1b
2…b
n trên bảng chữ cái , là từ  = a
1a
2…a
mb
1b
2…b
n trên bảng chữ cái .
Kí hiệu phép nhân ghép là  = α. (hay  = α).
Thí dụ 1.4:
Trên bảng chữ cái W = {if, then, else, a, b, c, d, e, f, +, −, , /, =, }, ta có
các từ  = if a+b=c then cd=e và  = else c/d=f, còn α là từ: if a+b=c then
cd=e else c/d=f.
Cho  = {a, b, c}, khi đó: Từ  = abcbcb chứa 2 vị trí của bcb, đó là
a*bcb*cb và abc*bcb*, φ = bcb là một từ con của . Từ  chứa một vị trí
của ký hiệu a, đó là *a*bcbcb.
Từ  = 010111001 trên bảng chữ cái {0, 1} có độ dài 9, trong đó 0101 là
tiền tố và 11001 là hậu tố của .
1.1.2.2. Phép lấy từ ngược
Theo tài liệu [5], tác giả: Nguyễn Văn Định, có viết “Giả sử có từ khác rỗng
 = a
1a
2 …a
m trên bảng chữ cái , khi đó từ a
m a
m-1… a
2a
1 được gọi là từ ngược
(hay từ soi gương) của từ , và được ký hiệu là 
R
, hay 
^
.
Khi  =  ta quy ước 
R

= .”
Từ đó ta có Định nghĩa I.5.
Định nghĩa I.5
Giả sử có từ khác rỗng  = a
1a
2 …a
m trên bảng chữ cái , khi đó từ a
m a
m-
1… a
2 a
1 được gọi là từ ngược (hay từ soi gương) của từ , và được ký hiệu là 
R
,

hay 
^
.
Khi  =  ta quy ước 
R

= .
Thí dụ 1.5:
Cho các từ α = 100110 và  = aabb trên bảng chữ cái {0,1,a,b}, theo định
nghĩa ta có:
α
R

= 011001 và (α
R
)
R

= (011001)
R

= 100110 = α.

R

= bbaa và (
R
)
R

= (bbaa)
R

= aabb = .
Cho các từ happy và oto trên bảng chữ cái  = {a, b, c, …x, y, z}, khi đó ta
có: (happy)
R

= yppah và (oto)
R

= oto. Ngoài ra ta có: | (happy)
R

| = | yppah| = | https://dethithptquocgia.com/

6


happy | = 3.
1.1.2.3. Phép chia từ
Là phép toán ngắt bỏ phần đầu hay phần cuối của một từ. Ta có các
định nghĩa sau:
Phép chia trái của từ α cho từ  (hay thương bên trái của α và ) cho
kết quả là phần còn lại của từ α sau khi ngắt bỏ phần đầu  trong từ α, và
được ký hiệu là \
Phép chia phải của từ α cho từ  (hay thương bên phải của α và )
cho kết quả là phần còn lại của từ α sau khi ngắt bỏ phần cuối  trong từ
α, và được ký hiệu là
α
/
Các phép toán trên ngôn ngữ.
Các họ ngôn ngữ cụ thể thường được đặc trưng một cách tiện lợi qua
các phép toán xác định trên ngôn ngữ, họ đó gồm các ngôn ngữ nhận được
bằng việc tổ hợp từ một số ngôn ngữ cho trước bởi một số phép toán nào
đó. Vì mỗi ngôn ngữ là một tập hợp nên ta có các phép toán đại số tập hợp
như là phép giao, phép hợp, phép hiệu, phép lấy bù trên các ngôn ngữ.
Chẳng hạn, với L1 và L2 là hai ngôn ngữ trên bảng chữ cái  thì ta cũng có
các ngôn ngữ mới sau đây trên bảng chữ cái : L1  L2, L1  L2, L1.L2,

*
\ L1.
1.1.3.1. Phép hợp
Theo tài liệu [9], tác giả:
Nguyễn Quốc Thắng – Nguyễn Lâm Tùng,
có viết “Tập các từ
{x | x  L
1 hoặc x  L
2 } được gọi là hợp của hai ngôn
ngữ L1 và L2
,
ký hiệu L
1 L
2.
”.
Từ đó ta có Định nghĩa I.6.
Định nghĩa I.6
Hợp của hai ngôn ngữ L1 và L2 trên bảng chữ cái , ký hiệu L1 L2,
là một ngôn ngữ trên bảng chũ cái , đó là tập từ:
L = {  * |   L1 hoặc   L2 }
Định nghĩa phép hợp có thể mở rộng cho một số hữu hạn các ngôn
ngữ, tức là hợp của các ngôn ngữ L1, L2, …, Ln trên bảng chữ cái , là tập
từ:


1
*|
n
i i
i
L L
 
=
= =
và 
2
L


https://dethithptquocgia.com/

7

1.1.3.2. Phép giao
Định nghĩa I.7
Giao của hai ngôn ngữ L1 và L2 trên bảng chữ cái , ký hiệu L1∩ L2, là
một ngôn ngữ trên bảng chữ cái , đó là tập từ:
L = {  * |   L1 và   L2 }
Định nghĩa phép giao có thể mở rộng cho một số hữu hạn các ngôn ngữ,
tức là giao của các ngôn ngữ L1, L2, …, Ln trên bảng chữ cái , là tập từ:

1
n
i
i
L
=
= {  * |   Li, với mọi i, 1 ≤ i ≤ n }
1.1.3.3. Phép lấy phần bù
Định nghĩa I.8
Ngôn ngữ phần bù của ngôn ngữ L trên bảng chữ cái , ký hiệu CL (hay
đơn giản là CL, nếu không gây nhầm lẫn), là một ngôn ngữ trên bảng chữ cái ,
đó là tập từ: CL = {  * |   L }.
Thí dụ 1.6:
Cho ngôn ngữ L1 = {, 0, 01}, L2 = {, 01, 10} trên bảng chữ cái  = {0,
1}, khi đó ta có: L1 L2 = {, 0, 01, 10}, L1 ∩ L2 = {, 01}.
Cho ngôn ngữ L = {  *, với |  | là một số chẵn }, khi đó ta có: CL =
{  
+,
với |  | là một số lẻ}.
1.1.3.4. Phép nhân ghép
Định nghĩa I.9
Cho hai ngôn ngữ L1 trên bảng chữ 1 và L2 trên bảng chữ 2. Nhân
ghép hay tích của hai ngôn ngữ L1 và L2 là một ngôn ngữ trên bảng chữ 1
 2, ký hiệu L1L2, đuợc xác định bởi: L1L2 = { | L1 và L2}.
Thí dụ 1.7:
Đây là một phản ví dụ để chỉ ra rằng phép nhân ghép không có tính phân
phối đối với phép giao. Phép hợp, phép giao không có tính phân phối đối với
phép nhân ghép. Xét các ngôn ngữ L1 = {0, 01}, L2 = {01, 10}, L3 = {0} trên
bảng chữ cái  = {0, 1}.
Có thể kiểm tra được rằng phép nhân ghép không có tính phân phối đối với
phép giao: Ta có: L2  L3 = , do đó: L1(L2  L3) = ,
Mặt khác, ta có L1L2 = {001, 010, 0101, 0110} và L1L3 = {00, 010}, do
đó: (L1L2)  (L1L3) = {010}. Vậy L1(L2  L3)  (L1L2)  (L1L3), tức là phép https://dethithptquocgia.com/

8

nhân ghép không có tính phân phối đối với phép giao.
Kiểm tra tính phân phối của phép hợp, phép giao đối với phép nhân ghép: Ta
có: L2L3 = {010, 100}, do đó: L1  (L2L3) = {0, 01, 010, 100},
Mặt khác ta cũng có L1  L2 = {0, 01, 10} và L1  L3 = {0, 01}, do
đó: (L1  L2)(L1  L3) = {00, 001, 010, 0101, 100, 1001}. Vậy L1
 (L2L3)  (L1  L2)(L1  L3), tức là phép hợp không có tính phân phối
đối với phép nhân ghép. Tương tự, đối với phép giao, ta có: L2L3 = {010,
100}, do đó: L1  (L2L3) = .
Mặt khác L1  L2 = {01}, L1  L3 = {0}, do đó: (L1  L2)(L1  L3)
= {010}. Vậy L1  (L2L3)  (L1  L2)(L1  L3). Tức là phép giao không
có tính phân phối đối với phép nhân ghép. Vì phép ghép ngôn ngữ có tính
kết hợp nên ký hiệu L
n
được dùng với mọi ngôn ngữ L và số tự nhiên n
theo nghĩa quen thuộc sau:


1
0,
1,
1.
n
n
khin
LLkhin
LLkhin

−
 =

= =



1.1.3.5. Phép lặp
Định nghĩa I.10
Cho ngôn ngữ L trên bảng chữ cái , khi đó:
Tập từ 
2
1
..... ....
n n
n
LL L L

=
= được gọi là ngôn ngữ lặp cắt
của ngôn ngữ L, ký hiệu là L
*
. Vậy ngôn ngữ lặp của L là tập hợp lũy thừa
của L:
L
*
=
1
n
n
L

=

Tập từ
2
1
... ...
n n
n
LL L L

=
= được gọi là ngôn ngữ lặp cắt của ngôn
ngữ L, ký hiệu là L
+
, Vậy ngôn ngữ lặp cắt của L là hợp của mọi lũy thừa
dương của L: L
+
=
1
n
n
L

=

Thí dụ 1.8:
+ Xét ngôn ngữ L = {0, 1} trên bảng chữ  = {0, 1}. Ta có:
L
2
= {00, 01, 10, 11}, tập hợp các xâu nhị phân độ dài 2;
L
3
= {000, 001, 010, 011, 100, 101, 110, 111}, tập hợp các xâu nhị https://dethithptquocgia.com/

9

phân độ dài 3. Tương tự, L
n
là tập hợp các xâu nhị phân độ dài n. Vì vậy, L
*
là
tập hợp tất cả các xâu nhị phân.
+ Xét hai ngôn ngữ trên bảng chữ  = {a}:
L1 = {a
2n
| n  1},
L2 = {a
5n+3
| n  0}.
Khi đó, ta có L1 = {a
2
}
+
, L2 = {a
5
}
*
{a
3
}.
1.1.3.6. Phép lấy ngôn ngữ ngược
Định nghĩa I.11
Cho ngôn ngữ L trên bảng chữ cái , khi đó ngôn ngữ ngược của L là một
ngôn ngữ trên bảng chữ cái , được ký hiệu là L
R
hay L
^
, là tập từ:
L
R
= {  * / 
R
 L}
Thí dụ 1.9:
Cho L = {, ab, abc, cbaa} là một ngôn ngữ trên bảng chữ cái  = {a, b, c},
khi đó L
R
= {, ba, cba, aabc} là ngôn ngữ ngược của L.
1.1.3.7. Phép chia ngôn ngữ
Định nghĩa I.12
Cho ngôn ngữ X và Y trên bảng chữ cái , khi đó thương bên trái của ngôn
ngữ X cho ngôn ngữ Y là một ngôn ngữ trên , được ký hiệu là Y \
X,
là tập từ:
Y \
X
= {z  * / x  X, y  Y mà x = yz}
Cho ngôn ngữ X và Y trên bảng chữ cái , khi đó thương bên phải của ngôn ngữ
X cho ngôn ngữ Y là một ngôn ngữ trên , được ký hiệu là
X
/Y, là tập từ:
X
/ Y = {z  * / x  X, y  Y mà x = zy}
1.2. Văn phạm và ngôn ngữ sinh bởi văn phạm
Ta có thể hình dung một văn phạm như một “thiết bị tự động” mà nó có khả
năng sinh ra một tập hợp các từ trên một bảng chữ cái cho trước. Mỗi từ được
sinh ra sau một số hữu hạn bước thực hiện các quy tắc của văn phạm.
Việc xác định một ngôn ngữ trên bảng chữ cái cho trước có thể được thực
hiện bằng một trong các cách thức sau:
Cách 1. Đối với mỗi từ thuộc ngôn ngữ đã cho, ta có thể chọn một quy
cách hoạt động của “thiết bị tự động” để sau một số hữu hạn bước làm việc nó
dừng và sinh ra chính từ đó. https://dethithptquocgia.com/

10

Cách 2. “Thiết bị tự động” có khả năng lần lượt sinh ra tất cả các từ
trong ngôn ngữ đã cho.
Cách 3. Với mỗi từ  cho trước, “thiết bị tự động” có thể cho biết từ
đó có thuộc ngôn ngữ đã cho hay không.
Trong lý thuyết văn phạm, người ta đã chứng minh được rằng ba
cách thức trên là tương đương nhau hay văn phạm làm việc theo các cách
trên là tương đương nhau. Vì vậy, ở đây ta quan tâm đến cách thứ nhất, tức
là ta xét văn phạm như là một “thiết bị tự động” sinh ra các từ. Vì lẽ đó mà
người ta còn gọi các “thiết bị tự động” đó là văn phạm sinh.
Định nghĩa văn phạm
Theo tài liệu [2], tác giả: Trần Văn Lộc, có viết: “Văn phạm G là 1 bộ
sắp thứ tự gồm 4 thành phần: G = < , , S, P >…”
Từ đó ta có Định nghĩa I.13.
Định nghĩa I.13
Văn phạm G là 1 bộ sắp thứ tự gồm 4 thành phần: G = < , , S, P >,
trong đó:
 là một bảng chữ cái, gọi là bảng chữ cái cơ bản (hay bảng chữ cái kết
thúc), mỗi phần tử của nó được gọi là một ký hiệu kết thúc hay ký hiệu cơ
bản;
 là một bảng chữ cái,    = , gọi là bảng ký hiệu phụ (hay
báng chữ cái không kết thúc), mỗi phần tử của nó được gọi là một ký hiệu
không kết thúc hay ký hiệu phụ.
S   được gọi là ký hiệu xuất phát hay tiên đề;
P là tập hợp các quy tắc sinh có dạng →,  được gọi là vế trái và
 được gọi là vế phải của quy tắc này, với ,   (  )
*
và trong
 chứa ít nhất một ký hiệu không kết thúc.
P = {→ |  = α’Aα’’, với A  Δ, α’, α’’,   (  )
*
}
Chẳng hạn, với  = {0,1},  = {S, A, B} thì các quy tắc S → 0S1A,
0AB → 1A1B, A → ,… là các quy tắc hợp lệ vì vế trái luôn chứa ít nhất
1 ký hiệu phụ thuộc . Nhưng các quy tắc dạng 0 → A, 01 → 0B,… là
các quy tắc không hợp lệ.
Thí dụ 1.10:
Các bộ bốn sau là các văn phạm:
• G1 = <{0,1},{S},S,{S→0S1,S→}>,
• G2 = <{a, b}, {S, A}, S, {S→Ab, A→aAb, A→}>,
• G3 = <{a, b, c}, {S, A, B, C}, S, {S→ABC, A→aA, B→bB, C→cC, https://dethithptquocgia.com/

11

A→a, B→b, C→c}>
Chú ý: Nếu các quy tắc có vế trái giống nhau có thể viết gọn lại: hai quy
tắc → , →  có thể được viết là →  | . Chẳng hạn, như trong văn phạm
G1 ở thí dụ 1.10, ta có thể viết hai quy tắc của nó dưới dạng S→0S1 | .
Ngôn ngữ sinh bởi văn phạm
Định nghĩa I.14
Cho văn phạm G = < , , S, P > và , (  )
*
. Ta nói  được suy
dẫn trực tiếp từ  trong G, ký hiệu ├
G
 hay ngắn gọn là ├  (nếu không
sợ nhầm lẫn), nếu tồn tại quy tắc →P và , (  )
*
sao cho  = ,
 = .
Điều này có nghĩa là nếu  nhận vế trái  của quy tắc → như là từ con thì
ta thay  bằng  để được từ mới .
Cho văn phạm G = < , , S, P > và , (  )
*
. Ta nói  được suy
dẫn từ  trong G, ký hiệu ╞
G
 hay ngắn gọn là ╞  (nếu không sợ nhầm
lẫn), nếu  =  hoặc tồn tại một dãy D = 0, 1,…, k(  )
*
sao cho 0 =
,  k =  và i-1├ i, với i = 1, 2,..., k.
Dãy D = 0, 1, …, k được gọi là một dẫn xuất của  từ  trong G và số
k được gọi là độ dài của dẫn xuất này. Nếu 0 = S và k  * thì dãy D gọi là
dẫn xuất đầy đủ.
Nếu i được suy dẫn trực tiếp từ i-1 bằng việc áp dụng một quy tắc p nào
đó trong G thì ta nói quy tắc p được áp dụng ở bước thứ i.
Cho văn phạm G = < , , S, P >. Từ * được gọi là sinh bởi văn
phạm G nếu tồn tại suy dẫn S╞ . Ngôn ngữ sinh bởi văn phạm G, ký hiệu L(G),
là tập hợp tất cả các từ sinh bởi văn phạm G:
L(G) = {
*
| S ╞
G
}.
Hai văn phạm G1 = < 1, 1, S1, P1 > và G2 = < 2, 2, S2,P2 >
được gọi là tương đương nếu L(G1) = L(G2).
Thí dụ 1.11:
Xét văn phạm G1 trong thí dụ 1.11 Từ  = 00001111 được suy dẫn từ S
bằng dãy dẫn xuất độ dài 5: S├ 0S1├ 00S11├ 000S111├ 0000S1111 ├
00001111 (có thể viết ngắn gọn là  = 0
4
1
4
). Bằng việc sử dụng n lần (n  0)
quy tắc 1 rồi quy tắc 2, ta có: S╞ 0
n
1
n
. Do đó L(G1) = {0
n
1
n
| n  0}.
Xét văn phạm G2 trong thí dụ 1.10 Sử dụng quy tắc 1, rồi n lần (n  0) quy https://dethithptquocgia.com/

12

tắc 2, sau đó quy tắc 3 để kết thúc, ta có: S├ Ab╞ a
n
Ab
n
b├ a
n
b
n+1
.
Do đó L(G2) = {a
n
b
n+1
| n  0}.
Dễ dàng thấy rằng: L(G4) = {tôi ăn cơm, anh ăn cơm, chị ăn cơm, tôi
ăn phở, anh ăn phở, chị ăn phở, tôi uống sữa, anh uống sữa, chị uống sữa,
tôi uống café, anh uống café, chị uống café}.
Ta có thể biểu diễn việc dẫn xuất từ <câu> đến một từ trong L(G4),
chẳng hạn “tôi ăn cơm” bằng một cây gọi là cây dẫn xuất hay cây phân
tích cú pháp như dưới đây. Tất nhiên, theo quan điểm phân tích cú pháp
thực tế, việc xem xét các quy tắc theo hướng ngược lại là từ phải qua trái.
Điều đó có nghĩa là cây dưới đây được xử lý từ dưới lên trên chứ không
phải là từ trên xuống dưới. (Hình 1.1).

Hình 1.1 Cây dẫn xuất cho ví dụ
Phân loại văn phạm theo Chomsky
Theo tài liệu [8], tác giả: Trần Văn Ban, có viết “Trong định nghĩa của
văn phạm G = (VN, , P, S); VN là tập các biến,  là tập chữ cái và S VN.
Để tiện lợi cho việc nghiên cứu và khảo sát các ngôn ngữ được sinh ra bởi
văn phạm, chúng ta tìm cách phân loại chúng. Muốn phân loại được các
ngôn ngữ, chúng ta phải dựa vào các dạng khác nhau của các qui tắc dẫn
xuất. Chomsky đã chia các qui tắc dẫn xuất của văn phạm G thành bốn loại
…”
Dựa vào đặc điểm của tập quy tắc mà người ta chia các văn phạm thành
các nhóm khác nhau. Noam Chomsky (Institute Professor, Massachusetts
Institute of Technology. Born December 7, 1928 Philadelphia,
Pennsylvania, USA) đã phân loại văn phạm thành bốn nhóm:
Nhóm 0: Văn phạm không hạn chế (hay văn phạm ngữ cấu, văn phạm
tổng quát),
Nhóm 1: Văn phạm cảm ngữ cảnh, https://dethithptquocgia.com/

13

Nhóm 2: Văn phạm phi ngữ cảnh,
Nhóm 3: Văn phạm chính quy.
Dưới đây là các định nghĩa cho các nhóm văn phạm nói trên.
Định nghĩa I.15
Văn phạm G = < ,  , S, P > mà không có một ràng buộc nào đối với
các quy tắc của nó được gọi là văn phạm tổng quát hay văn phạm không hạn chế.
Như vậy, các quy tắc trong văn phạm nhóm 0 có dạng: →, với  = α’Aα’’,
A  Δ, α’, α’’,   (   )
*
.Các quy tắc của văn phạm nhóm 0 được gọi là
quy tắc không hạn chế. Ngôn ngữ do văn phạm nhóm 0 sinh ra được gọi là ngôn
ngữ tổng quát.
Văn phạm G = < ,  , S, P > mà các quy tắc của nó đều có dạng: →,
với  = α’Aα’’, A  Δ, α’, α’’,   (   )
*
, và |  | ≤ |  |, được gọi là văn
phạm nhóm 1hay văn phạm cảm ngữ cảnh.
Các quy tắc trong văn phạm nhóm 1 được gọi là quy tắc cảm ngữ cảnh.
Ngôn ngữ do văn phạm cảm ngữ cảnh sinh ra được gọi là ngôn ngữ cảm ngữ
cảnh.
Các văn phạm mà các quy tắc của chúng có dạng trên, đồng thời chứa
thêm quy tắc rỗng S→, cũng được xếp vào lớp văn phạm nhóm 1.
Thí dụ 1.12:
Cho văn phạm: G1 = <{1}, {S, A, B}, S, P1 >, với P1 = {S→, S→1A,
A→1B, B→1A, A→1}. Khi đó, G1 là văn phạm chính quy và L(G1) = {1
2n
| n
 0}. Thật vậy, sử dụng quy tắc 1, ta có S├ 1
2n
, ( = 1
2n
, với n = 0), sử dụng
quy tắc 2, rồi n-1 lần (n  1) liên tiếp cặp quy tắc 3 và 4, cuối cùng là quy tắc 5,
ta có:
S├ 1A ├ 11B ├ 111A ├ … ╞ 1(1
2n-2
)A ├ 1(1
2n-2
)1 = 1
2n
.
https://dethithptquocgia.com/

14

1.3. Một số tính chất của ngôn ngữ
Một số tính chất của văn phạm và dẫn xuất
Định lý I.1
Với mọi văn phạm G = < , , S, P >, luôn tồn tại một văn phạm G’
= < ’, ’, S’, P’ > tương đương với văn phạm G, tức là L(G) = L(G’).
Chứng minh:
Giả sử có văn phạm G = < , , S, P >, ta xây dựng văn phạm G’ =
< ’, ’, S’, P’ >, trong đó:
• ’ = , và với mỗi a  , ta bổ xung một ký hiệu a     và
gọi là đối ngẫu của a, đặt Г = { a | a  }
• ’ =   Г
• S’ = S
P’ = P1  P2, với P1 = { a → a | a  }, P2 = { →  | →  P},
 và  là các xâu  và  đã được thay các ký hiệu thuộc  bằng các ký hiệu
đối ngẫu của nó. Dễ thấy rằng L(G) = L(G’), thật vậy ta sẽ chứng minh hai
bao hàm thức:
a./ Chứng minh L(G)  L(G’): Lấy bất kỳ   L(G), khi đó ta có
S╞
G
, tức là ta có một dãy suy dẫn trực tiếp trong G: S = 0├
G
1├
G
… ├
G
k = , với dãy suy dẫn này, ta thay mọi quy tắc trong các suy dẫn
i ├
G
i+1, ( 0 ≤ i ≤ k-1), bởi các quy tắc tương ứng trong P1 và P2, ta
nhận được dãy các suy dẫn trong G’: S = ’0├
G’
’1 ├
G’
… ├
G’
’m
= , do đó ta có S╞
G’
 , tức là   L(G’). Vậy L(G)  L(G’).
b./ Chứng minh L(G’)  L(G): Lấy bất kỳ   L(G’), khi đó ta có
S╞
G’
, tức là ta có một dãy suy dẫn trong G’: S = ’0├
G’
’1 ├
G’
…
├
G’
’k = , trong các suy dẫn i├
G’
i+1, ( 0 ≤ i ≤ k-1), ta thay mọi kí
hiệu a  Г bởi các ký hiệu tương ứng a  1, khi đó mọi quy tắc đều
thuộc P, ta nhận được dãy các suy dẫn trưc tiếp trong G: S = 0├
G
1├
G
… ├
G
k = , ta có S╞
G
, tức là   L(G). Vậy L(G’)  L(G).
Định lý I.2 (Hợp thành các suy dẫn)
Cho hệ viết lai W=(V, P) và cho u1,…, un, v1,…, vn là các xâu trong V*.
Bây giờ nếu u1⟹
*
v1,…, un⟹
*
vn, thì ta có u1…un ⟹
*
v1…vn.
Ta thừa nhận định lý trên (không cần chứng minh).
Tính đóng của lớp ngôn ngữ sinh bởi văn phạm https://dethithptquocgia.com/

15

Định lý I.3
Lớp ngôn ngữ sinh bởi văn phạm là đóng đối với phép hợp (), phép
giao (∩) và phép nhân ghép ngôn ngữ (.)
Chứng minh:
Trước hết, ta sẽ chứng minh lớp ngôn ngữ sinh bởi văn phạm là đóng đối
với phép hợp, việc chứng minh tính đóng của lớp ngôn ngữ sinh bởi văn phạm
đối với các phép giao và phép nhân ngôn ngữ là hoàn toàn tương tự.
Giả sử L1, L2 là các ngôn ngữ được sinh bởi văn phạm G1= <1,  1, S1,
P1>, G2 = <2,  2, S2, P2>, tức là L1 = L(G1), L2 = L(G2). Ta chứng minh
tồn tại văn phạm G sao cho L(G) = L1 L2.
Xây dựng văn phạm G sinh ra ngôn ngữ L1 L2 như sau: G = <,  , S,
P>, với:
 = 1 2
Δ = Δ1 2 {S}
P = P1 P2  {S→S1, S→S2}
Ta sẽ chứng minh L(G) = L1 L2 bằng cách chứng minh hai bao hàm thức:
a./ Chứng minh L(G)  L1 L2: Giả sử   L(G), khi đó tồn tại một suy
dẫn trong văn phạm G: S ╞
G
, trong đó   * = (1 2)*. Do cách xây
dựng tập quy tắc P, nên trong suy dẫn S╞ , có hai khả năng:
• hoặc S├
G
S1╞
G1
, vậy  là kết quả của suy dẫn S1╞  trong G1, do đó
  L(G1). (a)
• hoặc S├
G
S2╞
G2
, vậy  là kết quả của suy dẫn S2╞  trong G2, do đó
  L(G2). (b)
Từ (a) và (b), ta thấy   L1 L2, hay L(G)  L1 L2
b./ Chứng minh L1L2  L(G): Giả sử  L1L2, khi đó ta cũng có hai
khả năng:   L1 hoặc   L2 :
• Nếu   L1 = L(G1), khi đó ta có suy dẫn S1╞
G1
 trong G1, do đó ta
cũng có suy dẫn S ├
G
S1 ╞
G1
 là một suy dẫn trong G (vì theo cách xây dựng
G, mọi quy tắc và mọi ký hiệu trong G1 cũng đều thuộc G), như vậy   L(G).
• Nếu   L2 = L(G2), khi đó ta có suy dẫn S2╞
G2
 trong G2, do đó ta
cũng có suy dẫn S ├
G
S2 ╞
G2
 là một suy dẫn trong G (vì theo cách xây dựng
G, mọi quy tắc và mọi ký hiệu trong G2 cũng đều thuộc G), như vậy   L(G). https://dethithptquocgia.com/

16

Vậy ta luôn luôn có   L(G), do đó: L1L2  L(G). Tức là ta đã
chứng minh được rằng L(G) = L1 L2.
Tương tự, để chứng minh tính đóng của lớp ngôn ngữ sinh bởi văn
phạm đối với phép nhân ghép ngôn ngữ, ta xây dựng văn phạm G = <, 
, S, P> sao cho L(G) = L(G1). L(G2) như sau:
 = 1 2
Δ = Δ1 2 {S}
P = P1 P2 {S→S1S2}. Khi đó L(G) = L(G1).L(G2)
Để chứng minh tính đóng của lớp ngôn ngữ sinh bởi văn phạm đối với
phép giao, ta xây dựng văn phạm G = <,  , S, P> sao cho L(G) = L(G1)
 L(G2) như sau:
 = 1  2
Δ = Δ1 2  Г1  Г2 {S}
Trong đó: Г1 = {a | a  1} là tập các ký hiệu đối ngẫu của các ký
hiệu trong 1
 , còn Г2= { b | b 2
 } là tập các ký hiệu đối ngẫu của 2
 .
P = 12
pp { S → 12
SS } '"
PP

Trong đó 1
p là tập hợp các quy tắc nhận được từ 1
P , mà mọi ký hiệu a1

đều được thay đổi bởi ký hiệu đối ngẫu tương ứng của nó 12
,aP
https://dethithptquocgia.com/

17

CHƯƠNG 2. VĂN PHẠM PHI NGỮ CẢNH
2.1. Suy dẫn phi ngữ cảnh
Các thí dụ về văn phạm phi ngữ cảnh
Theo tài liệu [4], tác giả: Nguyễn Thị Trúc Viên, có viết:
“Một văn phạm G = (V, T, S, P) được gọi là phi ngữ cảnh (context free) nếu
mọi luật sinh trong P có dạng
A → x,
trong đó A
∈ V còn x ∈ (V ∪T)*.”
Từ đó ta có Định nghĩa II.1.
Định nghĩa II.1
Văn phạm phi ngữ cảnh là một văn phạm G = (∑, ∆, P, S) mà mọi sản xuất
(hay quy tắc) của nó đều có dạng:
A→α, trong đó A∈∆ và α∈(∑∪∆)*
Trước hết ta hãy xem một số thí dụ về văn phạm phi ngữ cảnh.
Thí dụ 2.1:
Trong các sách văn phạm tiếng Việt ta gặp một số các quy tắc thành lập câu
như sau:
Một câu (có thể) có dạng chủ ngữ vị ngữ
Một chủ ngữ (có thể) là một danh từ
Một chủ ngữ (có thể) là một đại từ
Một vị ngữ (có thể) là một động từ
Một danh từ (có thể) là mèo
Một danh từ (có thể) là bò
Một đại từ (có thể) là tôi
Một đại từ (có thể) là nó
Một động từ (có thể) là ăn
Một động từ (có thể) là nằm
Một động từ (có thể) là uống
Từ các quy tắc còn rất ít ỏi trên, ta có thể đã thành lập một số câu như sau:
Tôi nằm
Nó ăn
Bò uống https://dethithptquocgia.com/

18

Mèo nằm
Trong các quy luật trên thì các từ gạch dưới đơn như chủ ngữ, động từ... là
các phạm trù cú pháp biểu diễn cho một cấu trúc con của một câu. Còn các từ
gạch dưới kép như tôi, mèo... là các từ Việt (hay ký hiệu) trực tiếp có mặt trong
các câu. Nếu ta biểu diễn một cách ngắn gọn các phạm trù cú pháp câu, chủ
ngữ, vị ngữ, danh từ, đại từ, động từ lần lượt là U, C, V, D, Đ, G thì ta có thể
trình bày lại các quy tắc trên một cách súc tích hơn như sau:
U→ CV
C→ Đ
V→ G
D→ mèo
D→ bò
Đ→ tôi
Đ→ nó
G→ ăn
G→ nằm
G→ uống
Và đó chính là các sản xuất trong văn phạm phi ngữ cảnh, trong đó U,
C, V, D, Đ, G là các ký hiệu không kết thúc, còn “mèo”, “bò”, “tôi”, “nó”,
“ăn”, “nằm”, “uống” là các ký hiệu kết thúc.
Thí dụ 2.2:
Trong các ngôn ngữ lập trình, với ký pháp BNF (backus-nuaur form),
ta có thể định nghĩa một định danh sau:
<định danh> ::= <chữ cái> │<định danh> <chữ cái>│<định danh>
<con số>
<chữ cái>::= A │B│C│...│Z
<con số>::=0│1│2│3│4│5│6│7│8│9
Đó cũng chính là các quy tắc phi ngữ cảnh, trong đó ::= có nghĩa như
→, các kí hiệu không kết thúc là <định danh>, <chữ cái>, <con số> và các
kí hiệu kết thúc là A,B,C,... Z,1,2,...,9.
Thí dụ 2.3:
Trong Chương II ta đã chứng minh rằng ngôn ngữ L = {a
n
b
n
│n≥0} là
không chính quy. Ngôn ngữ đó có thể được sản sinh bởi một văn phạm phi
ngữ cảnh G=(∑, ∆, P, S) trong đó:
∑={a,b}, ∆={S} và https://dethithptquocgia.com/

19

P gồm các quy tắc: S→aSb│ε
Như vậy ngôn ngữ đó là ngôn ngữ phi ngữ cảnh (loại 2).
Thí dụ 2.4:
Ngôn ngữ L={ww
R
│w∈{a,b}*} được sản sinh bởi văn phạm mà các quy
tắc là:
S→aSa│bSb│ε
Vậy ngôn ngữ này cũng là ngôn ngữ phi ngữ cảnh.
Tính chất cơ bản (phân rã các suy dẫn phi ngữ cảnh)
Định lý I.2 ở chương I nói rằng ta có thể hợp thành các suy dẫn của một hệ
viết lại thành một suy dẫn. Ph dẫn phát biểu ngược lại là không đúng với mọi hệ
viết lại nói chung, song lại đúng với các văn phạm phi ngữ cảnh: ta có thể phân
rã một suy dẫn phi ngữ cảnh thành các suy dẫn con độc lập với nhau. Tính chất
cơ bản này của các suy dẫn phi ngữ cảnh là rất hay được vẫn dụng trong các chứng
minh sau này.
Theo tài liệu [1], tác giả: nguyễn Văn Ba, có viết:
“Cho G=(∑,∆,P,S) là một văn phạm phi ngữ cảnh và đặc V= ∑∪∆. Cho một
suy dẫn trong G u1...un 
k
v, trong đó u1 ∈ V* với mọi i=1,...,n và v∈V*. thế thì
với mọi i=1,...,n tồn tại vi ∈V* và ki∈N sao cho:
Với mọi i=1,...,n: ui 
k
i vi, ∑&#3627408472;
??????
??????=1i=k, và v1…vn=v.”
Từ đó ta có Định lý II.1.
Định lý II.1
Cho G=(∑,∆,P,S) là một văn phạm phi ngữ cảnh và đặc V= ∑∪∆. Cho một
suy dẫn trong G u1...un 
k
v, trong đó u1 ∈ V* với mọi i=1,...,n và v∈V*. thế thì
với mọi i=1,...,n tồn tại vi ∈V* và ki∈N sao cho:
Với mọi i=1,...,n: ui 
k
i vi, ∑k
??????
??????=1i=k, và v1…vn=v.
Chứng minh
Trường hợp n=2. Ta chứng minh định lý bằng quy nạp trên k.
• Nếu k=0: hiển nhiên.
• Nếu k=1: u1u2
1
v. Bởi định nghĩa của suy dẫn trực tiếp ta có
u1u2=u’Au”, v=u’βu’’ và A→β∈P.
Hai trường hợp có thể là:
+ Trường hợp │u’│ │u1│ta có u’=u1t và u2=tAu’’
Đặt v1=u1 và v2 = tβu’’
Quả nhiên ta có: https://dethithptquocgia.com/

20

u1
0
v1 và u2
1
v2; v=v1v2 và 0+1=1.
+Trường hợp │u’│< │u1│ta có, một cách đối xứng, u1

=u’At và u’’=tu2.
Đặt v1=u’βt và v2=u2
Quả nhiên ta có:
u1
1
v1 và u2
0
v2; v=v1v2 và 1+0=1.
• Nếu k>1: Giả sử phát biểu của định lý là đúng với mọi suy dẫn có độ
dài nhỏ thua k và ta chứng minh nó cũng dúng với độ dài k.
Vì: u1u2
k
v, và k>1, vậy u1u2
k-1
w
1
v.
Bởi giả thiết quy nạp, ta có:
w=w1w2 với u1
k
1w, u2
k
2w2, k1+k2=k-1, và w1w2 v.
Bởi chứng minh đã thực hiện cho độ dài 1 (cơ sở quy nạp), vậy thì:
v=v1v2 với w1
h
1v1, w2
h
2v2, h1+h2=1.
Như thế ta có: u1
k
1
+h
1v1, u2
k
2
+h
2v2, k1+h1+k2+h2=k.
Trường hợp n>2: Việc tổng quát hóa cho trường hợp n>2 là dễ dàng
(bằng quy nạp trên n).
Tính chất cơ bản nêu trên được phát biểu đối với quan hệ 
k
. Chúng
ta cũng có thể phát biểu nó theo quan hệ 
*
như sau.
Hệ quả II.1
Nếu u1...un
*
v trong một văn phạm phi ngữ cảnh, thì tồn tại v1,...,vn để
cho v=v1..vn và u1
*
v1,...,un
*
vn.
Cây suy dẫn
Theo tài liệu [4], tác giả Nguyễn Thị Trúc Viên, có viết “Cho G =
(V, T, S, P) là một VPPNC. Một cây có thứ tự là một cây dẫn xuất cho G
nếu và chỉ nếu…”
Từ đó ta có Định nghĩa II.2.
Định nghĩa II.2
Một cây suy dẫn trong một văn phạm phi ngữ cảnh G=(∑,∆,P,S) là một
cây mà mỗi đỉnh được gắn một nhãn là một phần tử thuộc tập ∑∪∆∪{ε} và
thoản mãn các điều kiện sau:
• Nhãn của gốc là ký kiệu đầu S.
• Nhãn của mỗi đỉnh trong là một ký hiệu không kết thúc (một phần tử
của ∆). Nhãn của mỗi lá là một ký hiệu kết thúc (một phần tử của ∑) hoặc là
ε (xâu rỗng). https://dethithptquocgia.com/

21

• Với mỗi đỉnh trong, nếu nó có nhãn là A và các con của nó là các đỉnh
n1,n2...,nk lần lượt có nhãn là X1,X2,...,Xk, thì A→X1X2...Xk phải làmột sản xuất
của G.
• Nếu một lá có nhãn là ε, thì lá đó phải là con duy nhất của cha nó (điều
này chỉ nhằm để hạn chế ciệc tùy tiện đưa thêm nhiều ε vô ích vào cây suy
dẫn).
Cho một suy dẫn, ta gọi cây con là một cây tạo thành bởi một đỉnh và mọi
hậu duệ của nó, cùng với các nhãn và các cung liên kết chúng. Nếu gốc của cây
con có nhãn là A, thì cây con đó được gọi là một A-cây.
Ta gọi biến (hay kết quả) của một cây các suy dẫn hay của một A-cây là xâu
tạo thành bằng cách ghép tiếp các lá của cây theo trật tự từ trái qua phải.
Thí dụ 2.7:
Cho G=({a,b},{S,A},P,S) là một văn phạm phi ngữ cảnh, trong đó P gồm
các quy tắc sau:
S→aAS│a
A→SbA│SS│ba
Một cây suy dẫn có biên là xâu aabbaa được cho trong Hình 2.1, trong đó ta
chỉ ra cách đi (men theo các cành) từ trái qua phải, cho phép nhặt lần lượt các lá
để thành lập ra xâu đó.

Hình 2.1 Một cây suy dẫn
Hình 2.2 cho một cây con của cây suy dẫn trên.

Hình 2.2 Một A-cây
https://dethithptquocgia.com/

22

Định lý II.2
Cho một văn phạm phi ngữ cảnh G, một xâu w là được sản sinh bởi
G (S
*
G w) khi và chỉ khi có một cây suy dẫn của văn phạm đó mà biên
của nó là w.
Chứng minh
Định lý II.2 được khẳng định khi ta chứng minh một tính chất tổng quát
hơn một chút là:
Với mọi ký hiệu không kết thúc A, A
*
G u khi và chỉ khi tồn tại một
A-cây có biên u.
Phép chứng minh được thực hiện theo hai chiều (khi,chỉ khi).
• Trước hết ta giả thiết u là biên của một A-cây và ta chứng minh
rằng A
*
Gu, bằng quy nạp trên số m các đỉnh trong của cây.
+ m=1: Cây có dạng như trong Hình 2.3.

Hình 2.3 Một A-cây có một đỉnh trong
Như thế thì u=X1X2...Xk và A→u∈P. Vậy A
*
u.
+ m>1: Giả thiết rằng kết luận là đúng với mọi cây có không quá m-1
đỉnh trong và xét một A-cây có m đỉnh trong. Giả sử X1,X2,...,Xk là các hậu
duệ trực tiếp (con) của gốc A. Chúng đều là gốc của các Xi-cây,1≤i≤k, mà số
các đỉnh trong là ít hơn m. Bởi giả thiết quy nạp, ta có Xi
*
ui, trong đó ui là
biên của Xi-cây (ui=Xi nếu Xi∈∑). Từ Định lý I.2 (hợp thành các suy dẫn ) ta
có: A=GX1X2...Xk G
*
u1u2...uk (Hình 2.4). Mặt khác, nếu i<j thì Xi và mọi
hậu duệ của nó luôn luôn ở bên trái Xj cùng với các hậu duệ của nó. Vậy
u=u1u2...uk là biên của A-cây, cho nên ta có A
*
Gu. https://dethithptquocgia.com/

23

Hình 2.4 Một A-cây và các cây con của nó
• Bây giờ ta giả thiết A
*
Gu và ta sẽ chứng minh, bằng quy nạp trên độ dài
n của dây dẫn, rằng tồn tại một A-cây có biên là u.
• n=1: Bấy giờ A→u∈P và ta có một A-cây như trên Hình 2.3 với biên là
u=X1X2...Xk.
• n>1: Giả thiết rằng với mọi ký hiệu không kết thúc A, nếu ta có một suy
dẫn A
*
u mà độ dài là nhỏ thua n, thì ta có môt A-cây có biên giới là u. Hãy xét
một suy dẫn A
*
u có độ dài n. Giả sử A→ X1X2...Xk là sản xuất được dùng trong
bước thứ nhất của suy dẫn, nghĩa là AG X1X2...XkG*u. Từ Định lý II.1 (Phân
rã các suy dẫn phi ngữ cảnh) ta có u= u1u2...uk và XiG*ui, 1≤i≤k. Vì rằng độ dài
của mỗi suy dẫn XiG*ui, 1≤i≤k là nhỏ thua n, cho nên tồn tại một Xi-cây, 1≤i≤k
có biên là ui. Từ đó ta có thể thành lập một A-cây như trong Hình 2.4 bằng cách
nối gốc A với gốc của mỗi một Xi-cây, 1≤i≤k. A-cây đó có biên là xâu u= u1u2...uk.
Suy dẫn trái, suy dẫn phải và tính nhập nhằng
Như đã thấy ở trên, một cây suy dẫn mà kết qủa là u tương ứng với nhiều
suy dẫn S
*
u. Trong số các suy dẫn này, ta chú ý đặc biệt tới hai suy dẫn sau:
Suy dẫn trái, đó là suy dẫn mà trong đó, ở mỗi bước, ký hiệu được thay thế
luôn luôn là ký hiệu không kết thúc nằm bên trái nhất trong dạng câu.
Suy dẫn phải, đó là suy dẫn mà trong đó, ở mỗi bước, ký hiệu được thay thế
luôn luôn là ký hiệu không kết thúc nằm bên phải nhất trong dạng câu.
Dễ dàng chứng tỏ rằng có một song ánh giữa các cây suy dẫn của một văn
phạm G với các suy dẫn trái(hay phải).
Một văn phạm phi ngữ cảnh G = (∑, ∆, P, S) là nhập nhằng nếu tồn tại một
xâu w∈(∑∪∆)
*
cùng là kết quả của hai cây suy dẫn khác nhau.
Cùng một ngôn ngữ có thế được sinh ra từ vô hạn các văn phạm khác nhau,
trong đó có văn phạm là nhập nhằng, có văn phạm là không nhập nhằng. Một
ngôn ngữ phi ngữ cảnh được nói là nhập nhằng cố hữu, hay nói gọn là nhập nhằng, https://dethithptquocgia.com/

24

nếu tất cả các văn phạm sinh ra nó đều nhập nhằng. Người ta chứng minh
rằng tồn tại những ngôn ngữ như vậy.
Thí dụ 2.8:
Cho G0 là văn phạm phi ngữ cảnh gồm các quy tắc sau:
E→E+E│E*E│(E)│a
Văn phạm này sản sinh các biểu thức số học trong đó các toán tử là +
và * và các hạng toán đều là a.

Hình 2.5 Một cây suy dẫn trong G0
Các câu suy dẫn cho trên Hình 2.5 có kết quả là a+a*a.
Suy trái tương ứng với cây đó là:
EE*EE+E*Ea+E*Ea+a*Ea+a*a
Suy dẫn phải tương ứng với cây đó là:
EE*EE*aE+E*aE+a*aa+a*a
Tuy nhiên ta lại còn có một cây khác có cùng kết quả là a+a*a, như
trên Hình 2.6. https://dethithptquocgia.com/

25

Hình 2.6 Một cây suy dẫn khác của G0
Như vậy văn phạm G0 là nhập nhằng. Điều đó có nghĩa là trong văn phạm
G0 biểu thức a+a*a được hiểu theo hai cách: cộng trước hay nhân trước.
Để loại trừ nhập nhằng ta đưa thêm một quy ước phù trợ:
• Hoặc là ta luôn luôn thực hiện các phép toán (cộng và nhân) theo thứ tự từ
trái qua phải khi các phép toán đó không bị ngăn cách bởi vòng đơn. Yêu cầu này
dẫn tới một văn phạm G1, tương đương với văn phạm G0, nhưng không nhập
nhằng, và có các quy tắc sau:
E→E+T│E*T│T
T→(E)│a
• Hoặc là ta luôn luôn thực hiện phép nhân trước phép cộng khi chúng không
bị ngăn cách bởi vòng đơn (ưu tiên phép nhân so với phép cộng). Yêu cầu này
dẫn tới một văn phạm khác G2, tương đương với G0, cũng không nhập nhằng, và
có các quy tắc sau:
E→E+T│T
T→T*F│F
F→(E)│a
Trong G2 các phép toán cùng mức ưu tiên mà đứng cạnh nhau thì được thực
hiện theo thứ tự từ trái qua phải.
Các cây suy dẫn cho xâu a+a*a trong các văn phạm G1+G2 được cho lần
lượt trên các Hình 2.7 và 2.8. https://dethithptquocgia.com/

26

Hình 2.7 Một cây suy dẫn của G1

Hình 2.8 Một cây suy dẫn của G1
2.2. Biến đổi các văn phạm phi ngữ cảnh
Thông thường thì một văn phạm còn chứa đựng nhiều yếu tố vô ích,
chẳng hạn các ký hiệu không tham gia vào suy dẫn ra các xâu của ngôn ngữ,
hay là các sản xuất có dạng A→B(A,B∈∆) làm kéo dài cac suy dẫn một cách
không thực sự là cần thiết. Bởi vậy nhiều khi ta cần biến đổi các văn phạm
thành các văn phạm tương đương mà không còn các yếu tố vô ích nữa.
Loại bỏ các ký hiệu vô ích https://dethithptquocgia.com/

27

Cho một văn phạm phi ngữ cảnh G = (∑, ∆, P, S) và đặt V=∑∪∆. Một ký
hiệu X∈V là có ích nếu tồn tại một suy dẫn S
*
αXβ
*
w, trong đó α,β∈V
*
và
w∈∑
*
, nếu không nó là vô ích.
Như vậy một ký hiệu có ích X phải là:
1) một ký hiệu hữu sinh, nghĩa là tồn xâu x∈∑
*
mà X
*
x.
2) một ký hiệu đến được, nghĩa là tồn tại hai xâu α,β∈V
*
để cho S
*
αXβ.
Bổ đề II.1 (Loại bỏ các ký hiệu vô sinh)
Tồn tại mọt thuật toán cho phép, với mọi văn phạm phi ngữ cảnh G mà L(G)≠
, thành lập một văn phạm phi ngữ cảnh tương đương G’ chỉ có các ký hiệu hữu
sinh.
Chứng minh
• Thành lập tập hợp các ký hiệu hữu sinh
Trước hết ta đặt: W0=∑,
với i>0, Wi=Wi-1∪{A∈∆│∃α∈Wi-1
*
:A→α∈P}
và cuối cùng đặt: W
Các tập Wi lớn dần (Wi Wi+1) nhưng lại luôn phải nằm trong tập hữu hạn V.
Vậy dãy các Wi sẽ phải dừng. Vì thế ta chỉ cần tính các Wi liên tiếp khi chúng còn
thực sự tăng trưởng, và ngừng lại khi chúng ngừng tăng, nghĩa là khi có Wk=Wk+1.
Bấy giờ ta cũng sẽ có Wk+1=Wk+2,v.v... và như thế thì W=Wk. Ta sẽ chứng minh
rằng W∩∆ chính là tập hợp các ký hiệu không kết thúc hữu sinh.
a) Cho A∈∆ là một ký hiệu không kết thúc hữu sinh, nghĩa là tồn tại một suy
dẫn:
A=α0 α1 ... αk=u trong đó u∈∑
*
, k≥1
Ta có u ∈ ∑
*
= W0
*
, và bước tiếp bước, căn cứ vào định nghĩa của các Wi ta
chứng tỏ được rằng với mọi i, αk-i∈Wt
*
, và cuối cùng thì A ∈ Wt
*
. Vậy thì A∈W∩∆.
b) Cho A ∈ W ∩ ∆. Thế thì tồn tại một số nguyên i để cho A ∈ Wi ∩ ∆.Ta sẽ
chứng minh bằng quy nạp trên i rằng A là hữu sinh.
+ Nếu i = 1, bởi định nghĩa của W1, ∃u∈W0
*
để cho A→u∈P, vậy ta có A
*
u và A là hữu sinh.
+ Giả sử với mọi số nguyên k<i, nếu A∈Wk∩∆ thì A là hữu sinh.
Ta có A∈Wi ∩ ∆ = (Wi-1∩∆) ∪ {A∈∆│∃α∈Wi-1
*
:A→α∈P}.
Nếu A∈Wi-1 thì nó là hữu sinh bởi giả thiết quy nạp. Nếu không ta có A→α∈P
với α∈Wi-1
*
. Bởi giả thiết quy nạp thì mỗi ký hiệu không kết thúc trong α, đều suy
dẫn được một xâu trên ∑. Cho nên suy ra A cũng vậy, nói cách khác A là hữu
sinh. https://dethithptquocgia.com/

28

• Thành lập văn phạm G’
Cuối cùng ta có thể thành lập van phạm G’=(∑,∆’,P’,S’) như sau và lưu ý
rằng L(G)≠  S∈W∩∆.
Ta đặt ∆’=W∩∆
và P’={A→u∈P│A∈∆’, u∈(∑∪∆’)
*
}
• Chứng minh L(G)=L(G’)
Rõ ràng L(G’) L(G), vì rằng tất cả các suy dẫn trong G’ đều là suy
dẫn trong G
Ngược lại, giả sử rằng x∈L(G) và x L(G’). Như mọi suy dẫn của x
trong G có sử dụng ít nhất một ký hiệu không kết thúc trong ∆-∆’ hoặc một
sản xuất trong P-P’ (và như vậy vẫn phải sử dụng một ký hiệu không kết
thúc trong ∆-∆’). Như thế thì đã có một ký hiệu không kết thúc trong ∆-∆’ là
hữu sinh. Mâu thuẫn này cho phép ta kết luận rằng L(G) L(G’). Từ đó
L(G)=L(G’).
Thí dụ 2.9:
Cho G=(∑,∆,P,S) trong đó
∑={a,b}, ∆={S,A,B,C}
P={S→aA│bAB│abA
A→aB│bA│a
B→aB│bB
C→aA│bS│a}
Vậy thì: W0 = {a,b}
W1=W0∪{A,C} (bởi các quy tắc A→a và C→a)
W2=W1∪{S} (bởi quy tắc S→aA)
W3=W2∪
Từ đó: W={a,b,S,A,C}, ∆’={S,A,C}
và G’=(∑,{S,A,C}, P’,S)
với P’={S→aA│abAS, A→bA│a, C→aA│bS│a}.
Hệ quả II.2
Cho một văn phạm phi ngữ cảnh G. Bài toán L(G)=  là giải được.
Quả vậy, L(G)=  khi và chỉ khi S W, và ta đã có cách để tính tập
W.
Bổ đề II.2 (Loại bỏ các ký hiệu không đến được) https://dethithptquocgia.com/

29

Tồn tại một thuật toán cho phép với mọi văn phạm phi ngữ cảnh G thành lập
một văn phạm phi ngữ cảnh tương đương G’ chỉ có các ký hiệu đến được.
Chứng minh
• Thành lập tập hợp các ký hiệu đến được
Ta đặt: W0={S}, U0=
Với i>0: Wi=Wi-1∪{A∈∆│∃B∈Wi-1, ∃u1u2∈(∑∪∆)*: B→ u1Au2∈P}
Ui=Ui-1∪{a∈∑│∃BWi-1,∃u1,u2∈(∑∪∆)*: B→u1au2∈P}
Và cuối cùng đặt: W=⋃??????
⬚
??????≥0i, U=⋃??????
⬚
??????≥0i
Tiếp theo ta chứng minh rằng:
+ Có thể tính các tập W và U một cách hữu hiệu ; điều này được suy ra từ sự
kiện nếu Wi+1=Wi thì  k>1 : Wi+k=Wi+1=W và Ui+k=Ui+1=U.
+ W là tập các ký hiệu không kết thúc đến được, và U là tập các ký hiệu kết
thúc đến được. Điều này được chứng minh tương tự như ở Bổ đề II.1, xin chuyển
đến độc giả như là một bài tập.
• Thành lập văn phạm G’
Tiếp đến ta thành lập văn phạm G’=(U,W,P’,S)
trong đó: P’={A→u∈P│A∈W và u∈(U∪W)*}
• Dễ dàng kiểm chứng rằng L(G)=L(G’).
Thí dụ 2.10:
Tiếp tục thí dụ ở trên, từ văn phạm i, ta có:
W0={S}, U0=
W1=W0∪{A}, U1=U0∪{a,b}
W2=W1, U2=U1
Vậy: W={S,A}, U={a,b}
và văn phạm tương đương với G’ chỉ gồm các ký hiệu đến được là:
G”=({a,b},{S,A},P”,S)
trong đó: P’’={S→aA│abAS, A→bA│a}.
https://dethithptquocgia.com/

30

Định lý II.3
Mỗi ngôn ngữ phi ngữ cảnh đều có thể được sản sinh từ một văn phạm
phi ngữ cảnh chỉ có các ký hiệu có ích.
Chứng minh
Cho một ngô ngữ phi ngữ cảnh L=L(G) và L≠ . Áp dụng lên G cách
thành lập ở Bổ đề II.1 ta thu được một văn phạm G’ chỉ có các ký hiệu hữu
sinh. Tiếp tục áp dụng lên G’ cách thành lập ở Bổ đề II.2 ta thu được một
văn phạm G” chỉ có các ký hiệu đến được.
Rõ ràng rằng L(G’’)=L(G’)=L(G)=L
Ta hãy chứng minh rằng G” chỉ có các ký hiệu có ích.
Giả sử trong G” có một ký hiệu vô ích X. Từ bổ đề II.2, X là đến được,
nghĩa là:
∃α,β : S G”*αXβ
Vì G’ bao gồm tất cả các ký hiệu và tất cả các sản xuất G”, và G’ chỉ
có các ký hiệu hữu sinh, vậy ta có:
S G”*αXβ G’*u, u∈∑*
Suy dẫn trong G’ này cho ta thấy rằng mọi ký hiệu dùng trong phần suy
dẫn αXβ G’
*
u đều là đến được (từ S). Vậy các ký hiệu đó không bị loại bỏ
bởi Bổ đề II.2 và chúng còn lưu lại trong văn phạm G”. Từ đó ta có:
S G”*αXβ G”*u
Điều đó có nghĩa là X là một ký hiệu có ích trong G”. Điều mâu thuẫn
này cho ta kết luận là: trong G” không có ký hiệu vô ích.
Chú thích
Trật tự áp dụng Bổ đề II.1 (loại bỏ vô sinh) rồi Bổ đề II.2 (loại bỏ không
đến được) như trên là cần thiết. Đảo lại có thể dẫn tới kết quả sai như trong
thí dụ sau đây:
Thí dụ 2.11:
Xét văn phạm:
S→AB│a
A→a
Áp dụng Bổ đề II.1, B bị loại cùng với sản xuất S→AB, và văn phạm
thu được là:
S→a
A→a
Áp dụng Bổ đề II.2, A bị loại vì không đến được, và ta chỉ còn: https://dethithptquocgia.com/

31

S→a
Nếu tiến hành theo thứ tự ngược lạ, áp dụng Bổ đề II.2 trước, ta không
loại được ký hiệu và sản xuất nào. Tiếp đó áp dụng Bổ đề II.1, ta loại B cùng với
sản xuất S→AB. Vậy văn phạm còn lại là:
S→a
A→a
vẫn còn có ký hiệu vô ích là A.
Loại bỏ các ε-sản xuất
Các ε-sản xuất (tức là sản xuất có dạng A→ε) không phải là vô ích hoàn
toàn, bởi vì khi xâu ε là thuộc ngôn ngữ, thì nhất thiết văn phạm phải chứa ít nhất
một ε-sản xuất (thường là S→ε). Nhưng ngoại trừ trường hợp đó thì các ε-sản
xuất là thừa, và có thể loại bỏ.
Định lý II.4
Cho G=(∑,∆,P,S) là một văn phạm phi ngữ cảnh. Ta có thể thành lập một
văn phạm phi ngữ cảnh G’=(∑,∆,P’,S’) không có sản xuất mà:
L(G’)=L(G)-{ε}.
Chứng minh
• Thành lập tập hợp các ký hiệu không kết thúc sinh ra xâu rỗng
Ta đặt: E0={A│A→ε∈P}
với i>0: Ei=Ei-1∪{A│∃u∈Ei-1* : A→u∈P}
và E = ⋃&#3627408440;
⬚
??????≥0i
Thế thì:
+ Ta có thể tính tập E một cách hữu hiệu, nghãi là ta sẽ thu được E sau một
số hữu hạn phép toán.
+ E chính là tập hợp các ký hiệu không kết thúc sinh ra (nói riêng) xâu rỗng:
E={A∈∆│A*ε}
Việc chứng minh cho các điều khẳng định này một lần nữa lại được thực
hiện tương tự như trong Bổ đề II.1. Xin dành cho độc giả như một bài tập.
• Thành lập tập các sản xuất P’
Ta thành lập P’ căn cứ trên P theo hai bước:
+ Với mỗi sản xuất A→X1X2...Xn∈P ta đưa vào P’ tất cả các sản xuất có dạng
A→α1α2...αn trong đó:
1) Nếu Xi E thì αi=Xi
2) Nếu Xi∈E thì αi=Xi hoặc αi=ε https://dethithptquocgia.com/

32

+ Loại bỏ tất cả các ε-sản xuất.
• Cuối cùng chứng minh L(G’)=L(G)-{ε}
+ L(G’) L(G)- {ε}
Vì G’ không có ε-sản xuất, ε không thuộc L(G’). Vậy thì còn phải chứng
minh tính chất sau:
Với mọi A∈∆ và mọi x∈∑*, nếu A
i
G’x thì A *Gx (2-1)
- Tính chất này đúng với i=0.
- Ta chứng minh nó cũng đúng với i+1 với giả thiết rằng nó đã đúng
với mọi suy dẫn có độ dài cho tới i.
Cho A G’Y1...YP
i
G’x, với Y1,...,YP ∈V∈∑∪∆.
Bởi tính chất cơ bản của văn phạm phi ngữ cảnh (Hệ quả II.1) và giả
thiết quy nạp, ta có:
Yj G*xj đối với j=1,...,p và x=x1...xp (2-2)
Do định nghĩa của P’, có các xâu α1,...,αp,αp+1 của E* sao cho:
A→α1Y1...αpYpαp+1 là một sản xuất trong văn phạm G (2-3)
Bởi định nghĩa của E ta có:
αj *Gε với j=1,...,p (2-4)
Từ các tính chất (2-2), (2-3), (2-4) ta có A *G x và như thế tính (2-1)
đã được chứng minh với i+1.
+ L(G’) L(G)-{ε}
Chỉ cần chứng minhh rằng:
Với mọi A∈∆ và với mọi x∈∑
+
, nếu A
i
Gx thì A *G’x (2-5)
- Tính chất là đúng với i=0.
- Ta chứng minh nó cũng đúng với i+1 với giả thiết rằng nó đã đúng
với mọi suy dẫn có độ dài cho tới i
Cho A GX1...Xp
i
Gx với X1,...,Xp∈V
Theo tính chất cơ bản của văn phạm phi ngữ cảnh, ta có:
Xj
n
jGxj với j=1,...,p trong đó nj<i và x=x1...xp (2-6)
Cho k1,...,kq là dãy tăng của các chỉ số của các xâu xj không rỗng, tức
là:
Với j từ 1 đến q, xkj là không rỗng và x=xk1...xkq (2-7)
Bởi định nghĩa của P’ và của dãy kj, ta có:
A→Xk1...Xkq là một sản xuất của P’ (2-8) https://dethithptquocgia.com/

33

Từ (2-6),(2-7) và gỉa thiết quy nạp ta có:
Xkj*G’xkj (2-9)
Từ các tính chất (2-7),(2-8) và (2-9) ta có: A*G’x và như thế tính chất
(2-5) được chứng minh với i+1.
Thí dụ 2.12:
Cho văn phạm:
S→ABC, A→BB│ε, B→CC│a, C→AA│b
Ta có: E={A,C,B,S}
Văn phạm tương đương không có ε-sản xuất lập theo cách trên là:
S→ABC│BC│AC│AB│A│B│C
A→BB│B
B→CC│C│a
C→AA│A│b
Hệ quả II.3
Cho một văn phạm phi ngữ cảnh G. Bài toán ε∈L(G) là giải được.
Quả vậy, ε∈L(G) khi và chỉ khi S∈E={A│A*ε} mà tập E là có thể tính
được như trên.
Định lý II.5
Cho một văn phạm phi ngữ cảnh G=(∑,∆,P,S). Nếu L(G) không rỗng, ta có
thể thành lập một văn phạm phi ngữ cảnh G’=(∑,∆’,P’,S) không có ký hiệu vô
ích, và không có ε-sản xuất sao cho L(G’)=L(G)-{ε}.
Chứng minh
Đầu tiên ta loại bỏ các ε-sản xuất. ta được một văn phạm H không có ε-sản
xuất mà L(H)=L(G)-{ε}. Tiếp đến ta loại bỏ các ký hiệu vô sinh rồi các ký hiệu
không đến được. Làm vậy ta không đưa thêm sản xuất mới nào vào văn phạm H,
cho đến văn phạm G’ thu được là không có ε-sản xuất.
Loại bỏ các sản xuất đơn
Sản xuất đơn là một sản xuất có dạng A→B trong đó B là một ký hiệu không
kết thúc. Trên phương diện là cú pháp thuần túy, thì sản xuất đơn thường làm kéo
dài các suy dẫn, cho nên cũng có khi ta đặt vấn đề loại bỏ chúng. Tuy nhiên trên
phương diện ngữ nghĩa, thì sản xuất đơn có khi cũng có ích. Chẳng hạn trong thí
dụ đưa ra ở Mục 1.4 ở trên, văn phạm G2 có chứa các sản xuất đơn E→T và T→F,
với ý nghĩa là: một biểu thức có thể chỉ là một hạng thức, và một hạng thức có thể
chỉ là một nhân thức. Có thể loại bỏ các sản xuất đó ra khỏi văn phạm mà không
làm thay đổi ngôn ngữ, song các ý nghĩa trên thì không còn biểu hiện nữa. https://dethithptquocgia.com/

34

Theo tài liệu [12], ta có Định lý II.6.
Định lý II.6
Cho một văn phạm phi ngữ cảnh G=(∑,∆,P,S). Ta có thể thành lập một văn
phạm tương đương G’=(∑,∆,P’,S) không có các sản xuất đơn.
Chứng minh
• Thành lập G’
Cho R là quan hệ trên ∆ được định nghĩa là:
ARB khi và chỉ khi A→B∈P
Bấy giờ ta đặt:
P’={A→α│∃B→α∈P, với α ∆ và AR*B}
Lưu ý rằng ta có thể tính P’ từ văn phạm G. Vậy lập được G’ từ văn
phạm G đã cho.
• L(G’) L(G)
Suy ra điều đó từ sự kiện:
Nếu A→α∈P’ thì A *Gα
• L(G) L(G’)
Điều này được xã định ngay sau khi ta chứng minh bằng quy nạp trên i
rằng:
Nếu A∈∆ và x∈∑* mà A
i
Gx thì A *G’x (2-10)
- Mệnh đề này đúng với i=0.
- Ta chứng tỏ rằng nó vẫn đúng với i+1 nếu giả thiết rằng nó đã đúng
với mọi suy dẫn có độn dài cho tới i.
Cho α0 G...  Gαi Gαi+1 là một suy dẫn của văn phạm G có độ dài
i+1, trong đó α0 thuộc vào ∆ và αi+1là một xâu các ký hiệu kết thúc. Tồn tại
j, 0 ≤ j ≤ i sao cho α0,...,αj∈∆ và αj+1 ∆. Từ định nghĩa của P’, α0→αj+1 là
một sản xuất trong P’. Mặt khác ta có αj+1
*
Gαi+1, bởi tính chất cơ bản của
văn phạm phi ngữ cảnh và giả thiết quy nạp. từ đó có kết luận α0
*
Gαj+1.
Tính chất (2-10) được chứng minh cho i+1.
Thí dụ 2.13:
Trở lại văn phạm G2: E→E+T│T
T→T*T│F
F→(E)│a
Ta có: R={(E,T),(T,F)}
R*={(E,E),(T,T),(F,F),(E,T),(T,F),(E,F)} https://dethithptquocgia.com/

35

Văn phạm tương đương không có sản xuất đơn thành lập theo cách trên là:
E→E+T│T*F│(E)│a
T→T*F│(E)│a
F→(E)│a
Định lý II.7
Cho văn phạm phi ngữ cảnh G=(∑,∆,P,S). Nếu L(G) là không rỗng, ta có thể
thành lập một văn phạm phi ngữ cảnh G’=(∑,∆’,P’,S’) không có ký hiệu vô ích,
không có ε-sản xuất và không có sản xuất đơn sao choL(G’)=L(G)-{ε}.
Văn phạm phi ngữ cảnh có các tính chất trên được gọi là một văn phạm sạch.
Chứng minh
Chỉ cần áp dụng các biến đổi theo thứ tự sau: loại bỏ các ε-sản xuất, loại bỏ
các sản xuất đơn, loại bỏ các ký hiệu vô sinh, loại bỏ các ký hiệu không đến được.
Quả vậy, loại bỏ các sản xuất đơn tạo ra những sản xuất mới, song không tạo ra
các vế phải mới của sản xuất, cho nên văn phạm tạo ra ở bước hai vẫn không có
các ε-sản xuất.
Định lý II.8
Cho một văn phạm phi ngữ cảnh G, và xâu x trên bộ chữ kết thúc của G. Bài
toán x∈L(G) là giải được.
Chứng minh
• Nếu x=ε, thì bởi Bổ đề II.3, ta có thể quyết định phải chăng ε∈L(G).
• Nếu x≠ε, x là thuộc L(G) khi và chỉ khi x thuộc L(G’), trong đó G’ là văn
phạm không có ε-sản xuất, không có sản xuất đơn, được thành lập như tron g
chứng minh của Định lý II.7. Trong văn phạm đó mọi suy dẫn của xâu x nhất thiết
phải có độ dài nhỏ thua hoặc bằng │x│. Vậy chỉ cần liệt kê các suy dẫn từ S có
độ dài nhiều nhất tới │x│ (số các suy dẫn đó là hữu hạn) để kiểm định phải chăng
x∈L(G).
Dạng chuẩn Chomsky
Theo tài liệu [10], tác giả: Trần Văn Cảnh, có viết “Một ngôn ngữ phi
ngữ cảnh bất kỳ không chứa ε đều được sinh ra bằng một văn phạm nào đó
mà các luật sinh có dạng A → BC hoặc A → a, với A, B, C là biến và a là ký
hiệu kết thúc.”.
Từ đó ta có Định nghĩa II.3.
https://dethithptquocgia.com/

36

Định nghĩa II.3
Một văn phạm phi ngữ cảnh G=(∑,∆,P,S) là ở dạng chuẩn Chomsky
nếu các sản xuất của nó chỉ có thể có hai dạng sau:
A→BC với A,B,C ∈ ∆,
A→a với A∈ ∆ và a∈ ∑.
Các văn phạm phi ngữ cảnh ở dạng chuẩn Chomsky đều là các văn
phạm phi ngữ cảnh không có ε-sản xuất. Cho nên các ngôn ngữ do chúng
sinh ra đều không chứa xâu rỗng.
Định lý II.9
Cho một ngôn ngữ phi ngữ cảnh G. Ta có thể thành lập một văn phạm
G’ ở dạng chuẩn Chomsky sao cho L(G’)=L(G)-{ε}.
Chứng minh
Đối với mọi văn phạm phi ngữ cảnh, ta có thể thành lập một văn phạm
tương đương, sai kém xâu rỗng ε, không có ε-sản xuất và không có sản xuất
đơn. Vậy ta có thể giả thiết ngay là văn phạm G không có ε-sản xuất và
không có sản xuất đơn.
Đặt G=(∑,∆,P,S), ta thành lập G’=(∑,∆’,P’,S) theo hai bước:
1) Nếu còn một sản xuất A→Y1Y2...Yk với k>2,ta loại bỏ sản xuất đó và
thêm hai sản xuất A→Y1A’ và A’→Y2Y3...Yk trong đó A’ là một ký hiệu không
kết thúc mới. Lặp lại quá trình cho đến khi văn phạm chỉ còn chứa các sản
xuất mà vế phải có độ dài thua hoặc bằng 2.
2) Trong văn phạm thu được như vậy, ta lưu ý mọi ký hiệu kết thúc có
mặt trong các vế phải có độ dài 2 của các sản xuất và thực hiện biến đổi sau:
Cứ mỗi ký hiệu kết thúc a đó, ta đưa thêm một ký hiệu không kết thúc mới
Ca, thay mọi xuất hiện của a trong các vế phải độ dài 2 bởi Ca, đồng thời đưa
thêm một sản xuất mới là Ca→a. Văn phạm nhận được là đã ở dạng chuẩn
Chomsky.
Dễ dàng chứng minh L(G’)=L(G)-{ε}.
https://dethithptquocgia.com/

37

CHƯƠNG 3. Ô TÔ MÁT ĐẨY XUỐNG
3.1. Ô tô mát đẩy xuống không tiền định
Khái niệm và định nghĩa
Định nghĩa III.1
Một ô tô mát đẩy xuống không tiền định (hay không đơn định), gọi là ô tô
mát đẩy xuống, là một bộ -7 M=(∑, &#3627408452;,Γ, &#3627409151;, q0, Z0, F)
Trong đó:
• ∑ là bộ chữ vào;
• ?????? là một tập hữu hạn các trạng thái với &#3627408452;∩Γ=∅;
• q0∈Q là trạng thái ban đầu;
• Z0 ∈ Γ là ký hiệu đầu trên stack (hay đáy stack);
• F⊆Q là tập các trạng thái thừa nhận (hay trạng thái cuối);
• &#3627409151;: Γ×Q×(∑∪{ε})→??????(Γ∗Q) là hàm dịch chuyển, trong đó ký hiệu
??????(X) là tập các tập con hữu hạn của X.
Quy ước về cách viết: Sau đây để dễ nắm bắt ta thường dùng:
a,b,c… để biểu diễn các ký hiệu vào,
u, v,w, x, y… để biểu diễn các xâu vào,
A, B, C để biểu diễn các ký hiệu trên stack,
α, β,&#3627409150;,… để biểu diễn các xâu ký hiệu trên stack,
Ta gọi tình trạng của các ô tô mát đẩy xuống là mọi xâu có dạng &#3627409150;qw trong
đó &#3627409150;∈ Γ
*
, q∈Q, w∈∑
*
.
Một hình trạng có dạng Z0q0x được gọi là một hình trạng đầu.
Ta gọi hệ viết lại ngầm định của ô tô mát đẩy xuống M là hệ viết lại WM=(V,
P), trong đó:
• V=Q∪∑∪ Γ,
• P gồm các quy tắc thành lập từ &#3627409151; theo các cách sau:
Với p,q∈Q, α∈ Γ
*
, a∈∑∪{&#3627409152;} và Z∈ Γ
Nếu (α,p) ∈ &#3627409151;(Z, q, a) → αp là một quy tắc trong P.
Một xâu x ∈∑
*
là được thừa nhận theo trạng thái cuối bởi ô tô mát M, nếu
tồn tại một suy dẫn trong hệ viết lại ngầm định WM dưới dạng:
Z0q0x⇒
*
WM &#3627409150;p trong đó &#3627409150;∈ Γ
*
và p ∈ F
Một xâu x ∈∑
*
là được thừa nhận theo stack rỗng bởi ô tô mát M, nếu tồn
tại một suy dẫn trong hệ viết lại ngầm định WM dưới dạng:
Z0q0x⇒
*
WM &#3627409150;p trong đó p ∈ Q https://dethithptquocgia.com/

38

Một suy dẫn WM xuất phát từ một hiện trạng được gọi là quá trình dịch
chuyển ô tô mát của M.
Cuối cùng ta gọi
• Ngôn ngữ được thừa nhận theo trạng thái cuối bởi ô tô mát đẩy xuống
M là ngôn ngữ:
L(M)={w∈∑
*
| Z0q0w ⇒
*
M &#3627409150;p, &#3627409150;∈ Γ
*
và p∈&#3627408441;}
• Ngôn ngữ thừa nhận theo stack rỗng bởi ô tô mát đẩy xuống M là ngôn
ngữ:
N(M)={w∈∑
*
| Z0q0w ⇒
*
M &#3627409150;p, p∈&#3627408452;}
Trong trường hợp thừa nhận xâu theo stack rỗng thì tạp các trạng thái
thừa nhận F là không dùng đến M, vậy lúc đó ta thường lấy F=∅
Các tính chất cơ bản của ô tô mát đẩy xuống
Cho M=(∑, &#3627408452;,Γ, &#3627409151;, q0, Z0, F)là ô to mát đẩy xuống mà ta sẽ dùng trong
mọi phát biểu về tính chất được đề cập trong mục này.
Tất cả các tính chất đều bắt nguồn từ đặc điểm của các quy tắc trong
các hệ viết lại ngầm định của ô tô mát đẩy xuống, là đều có dạng Zpa→&#3627409150;&#3627408478;
trong đó p,q∈&#3627408452;, Z∈ Γ, a∈∑∪{&#3627409152;} và &#3627409150; ∈Γ
*
. Vì vậy |Z|=1, |a|≤1 và |&#3627409150;|≥
0. Một quy tắc như vậy khi được vận dụng, có thể dẫn tới các trường hợp:
• Nếu |a|=1 (nghĩa lá a ∈∑) thì độ dài của phần tử xâu vào chưa đươc
đọc đến sẽ giảm một;
• Nếu |&#3627409150;|=0 (nghĩa là &#3627409150;=&#3627409152;) thì độ dài của stack sẽ giảm đi một.
Đáng chú ý là độ dài của phần xâu vào chưa đọc đến cũng như độ dài
cảu stack không bao giờ có thể giảm nhiều hơn một trong một bước dịch
chuyển.
Định lý III.1
Cho p,q∈&#3627408452;; &#3627409148;, β∈ Γ
*
; w, v∈∑
*
. Nếu αpw⇒
i
βqv, thì:
• ∃ u∈∑
*
: w=uv (nghĩa là v là một hậu tố của w) và
• αpu ⇒
I
βq.
Một cách trực quan, thì tính chất này có nghĩa là các ký hiệu chưa được
đọc đến (nghĩa là xâu v) không can dự gì vào tính toán cho đến lúc đó.
Chứng minh
Ta chứng minh định lý bằng quy nạp theo i.
• Với i=0 tính chất là tầm thường (α=β, w=v, u=&#3627409152;)
• Giả thiết rằng nó đã được nghiệm đúng đến i. Cho αpw⇒
i+1
&#3627409149;qv

và giả
sử Zra→&#3627409150;q là quy tắc được dùng trong bước suy dẫn cối cùng. Vậy: https://dethithptquocgia.com/

39

αpw⇒
i
&#3627409149;
’
Zrav ⇒&#3627409149;
’
&#3627409150;qv, trong đó &#3627409149;
’
&#3627409150;=β
Bởi giả thiết quy nạp, av là một hậu tố của w (w = u’av) và αpu’⇒
i
β’Zr.
Twf ddos v là một hậu tố của w; mặt khác từ tính chất về hợp thành của của
các suy dẫn trong hệ viết lại ta cũng có:
αpu’a⇒
i
β’Zra,
Tiếp tục áp dụng chính quy tắc Zra→ &#3627409150;q, ta thu được:
αpu’a⇒
i
β’Zra⇒ β’&#3627409150;q
Thay u’a=u và β’&#3627409150; = β, ta có
αpu⇒
i+1
βq
Như thế tính chất đó cũng được nghiệm đúng với i+1, và vì thế nó luôn đúng.
Hệ quả III.1
Cho p,q ∈&#3627408452;; α,β∈Γ
*
và w,v∈∑
*
.
Nếu αpw ⇒
*
thì ∃&#3627408482;∈∑
*
: w=uv và αpu⇒
*
βq.
Định lý III.2
Cho một quá trình dịch chuyển αpw⇒
i
βqv
Nếu α=??????α’, trong đó |α’|≥1 (nghĩa là nếu ?????? là một tiền tố chặt của α) và trong
suốt quá trình dịch chuyển, không kể trong hinh trạng cuối cùng, độ dài của stack
vẫn luôn luôn lớn hơn|??????|, thì:
• β=??????β’ với |β’|≥0 (nghĩa là ?????? là một tiền tố của β) và
• α’pw ⟹
i
βqv
Một cách trực quan, tính chất này có nghĩa là trong quá trình dịch chuyển thì
các ký hiệu trong stack mà không có lần nào dâng lên đỉnh stack thì sẽ không thay
đổi gì và không can dự gì vào sự tính toán.
Chứng minh
Ta chứng minh định lý trên bằng quy nạp i.
• Với i=0, tính chất là tầm thường (αpw=βqv).
• Giả thiết rằng nó đã được nghiên cứu đúng đến i. Cho αpw⟹
i+1
βqv và giả
sử Zra⟶&#3627409150;q là quy tắc được sử dụng trong bước suy dẫn cuối cùng. Vậy:
αpw⟹
i
β1Zrav⟹β1&#3627409150;qv, trong đó β1&#3627409150;=β (3-1)
Bởi vì giả thiết của định lý: |β1Z|> |??????| như vậy |β1|=|??????| (3-2)
Bởi giả thiết quy nạp, ta có:
?????? là một tiền tố của β1Z, do đó bởi (3-2) nó là một tiền tố của β1:
β1=??????β’1, |β’1|≥0 https://dethithptquocgia.com/

40

α’pw⟹
i
β’1Zra (3-3)
Áp dụng chính quy tắc Zra⟶&#3627409150;p lên hình trạng cuối cùng, ta có:
Α’pw⟹
i
β’1Zrav ⟹β’1&#3627409150;qv (3-4)
Đối chiếu (3-1), (3-3) và (3-4) ta có:
β=β1&#3627409150;= ??????β’1&#3627409150;, vậy ?????? là một tiền tố của β, nghĩa là β= ??????β’
trong đó β’= β’1&#3627409150;. Từ đó (3-4) trở thành:
α’pw⟹
i+1
β’qv
Như thế tính chất được nghiệm đúng với i+1, và từ đó nó luôn đúng.
Hệ quả III.2
Cho một quá trình dịch chuyển αpw⟹
*
βqv.
Nếu α = ??????α’ trong đó |α’|≥1 và suốt quá trình dịch chuyển, trừ trong
hình trạng cuối cùng, độ dài của stack vẫn luôn lớn hơn | ?????? |, thì:
• β = ??????β’ với |β’|≥0
• α’pw ⟹
*
β’pv
Định lý III.3 (phân rã các quá trình dịch chuyển)
Cho ??????, α∈Γ
*
và w∈∑
*
Nếu ??????αpw ⟹
*
q thì tồn tại hai xâu x,y ∈∑
*
, hai số nguyên k, l và một
trạng thái r sao cho:
w=xy, i = k+l, αpx ⟹
k
r và ??????ry ⟹
l
q.
Chứng minh
Bởi định nghĩa các ôt ô mát đẩy xuống, độ dài stack nhiều nhất là giảm
một trong các bước dịch chuyển. Như thế, trong quá trình dịch chuyển đã
cho, độ dài stack ít nhất một lần đạt giá trị |??????|. Giả sử &#3627409150;ry là hình trạng đầu
tiên đã gặp mà |&#3627409150;|=|??????| và giả sử k là độ dài của suy dẫn kể từ tình trạng đầu
tiên ??????αpw đến hình trạng &#3627409150;&#3627408479;&#3627408486; đó. Đặt l=j-k. Vậy thì suy dẫn đã cho
??????αpw⟹
i
q có thể viết thành:
??????αpw ⟹
k
&#3627409150;&#3627408479;&#3627408486;⟹
l
q
• Nếu k=0 thì ??????αpw=&#3627409150;&#3627408479;&#3627408486;, từ đó ta dễ dễ dàng suy ra: ??????=&#3627409150;, α=0, p=r,
w=y và như vậy tính chất trên được thỏa mãn một cách tầm thường.
• Nếu k≠0, bởi Định lý III.2 áp dụng cho phần đầu của suy dẫn, ta có:
- ?????? là một tiền tố của &#3627409150;. Nhưng |&#3627409150;|=|??????, vì vậy &#3627409150;|=??????
- αpw ⟹
k
ry
Theo Định lý III.1 y là một hậu tố của w, nghĩa là ∃x: w=xy, và αpx⟹
k

ry. Phần thứ hai của suy dẫn có thể viết khác đi là: ??????ry⟹
i
q. https://dethithptquocgia.com/

41

Vậy định lý đã được chứng minh.
Hệ quả III.3
Cho một số nguyên không âm n và α1, α2,…, αn∈Γ
*

Nếu αn αn-1… α1pw⟹
i
thì tồn tại các xâu trong ∑
*
, x1, x2,…, xn các số nguyên
k1, k2,…, kn và các trạng thia q1, q2,…, qn+1 sao cho
w = x1, x2,…, xn,
i = k1, k2,…, kn,
q = q1, q2,…, qn+1
và với I từ 1 đến n ta có: αiqixi⟹
k
q+1.
Chứng minh
Kết quả trực tiếp của Định lý III.3
Tương đương giữa hai loại ô tô mát đẩy xuống thừa nhận theo stack
rỗng và thừa nhận theo trạng thái cuối
Theo tài liệu [13], ta có Định lý III.4.
Định lý III.4
Cho L=L(M) trong đó M là một ô tô mát đẩy xuống. Tồn tại một ô tô mát
đẩy xuống M’ sao cho L=N(M’).
Chứng minh
Giả sử M=(∑, Q, Γ,&#3627409150;, q0, Z0, F).
Ô tô mát M’ có thêm hai trạng thái mới q’0và qe, cũng như một ký hiệu đáy
stack mới X0, nghĩa là
M’=(∑, Q ∪ {q’0, qe},&#3627409150;’,q’0, X0, ∅)
Ô tô mát M’ ban đầu đặt ký hiệu đáy stack Z0 của M lên trên ký hiệu đáy
stack của nó X0, đồng thời chuyển sang trạng thái ddaaud q0 của M:
(3-5) &#3627409150;’(X0, q0, &#3627409152;)={(X0Z0q0)}
Sau đó ô tô mát M’ rập theo sự hoạt động của ô tô mát M cho đến khi gặp
một trạng thái cuối:
(3-6) Với mọi q∈&#3627408452;−&#3627408441;, a∈∑∪{ &#3627409152; } và Z∈ Γ: &#3627409151;’(Z,q,a)= &#3627409151;(Z,q,a)
Lưu ý rằng ta dùng ký hiệu X0 làm đáy stack cho M’ (thay vì Z0) để đề phòng
một trường hợp tế nhị là khi M đọc xong một xâu và dừng lại ở một trạng thái
không thừa nhận, nhưng lại với stack rỗng. Như thế thì khi M’ rập theo quá trình
ấy nó sẽ dừng lại với stack còn có X0 và vì stack không rỗng, nó sẽ không thừa
nhận xâu đó đúng như M đã không thừa nhận xâu đó. https://dethithptquocgia.com/

42

Khi ô tô mát M gặp một trạng thái cuối, ô tô mát M’ có hai lựa chọn là
tiếp tục bắt chước M hoặc chuyển sang trạng thái qe, để từ đó bắt đầu các
thao tác dốc sạch stack:
(3-7) Với mọi q∈&#3627408441;, α∈∑ và Z∈Γ:
&#3627409151;’(Z,q,a)= &#3627409151;(Z,q,a)
&#3627409151;’(Z,q,&#3627409152;)= &#3627409151;(Z,q, &#3627409152;)∪{(&#3627409152;,qe)}
(3-8) Với mọi q∈&#3627408441;:
&#3627409151;′(X0,q, &#3627409152;)={(&#3627409152;,qe)}
Khi ô tô mát M’ ở trạng thái qe, nó dỡ hết mọi ký hiệu còn lại trong
stack:
(3-9)Với mọi Z∈Γ∪{X0}:
&#3627409151;′(Z,q, &#3627409152;)={(&#3627409152;,qe)}
Các quy tắc (3-5), (3-6), (3-7), (3-8) và (3-9) đinh nghĩa một cách đầy
đủ hàm dịch chuyển &#3627409151;′.
Giả sử x∈&#3627408447;(&#3627408448;), thế thì Z0q0x⟹
*
M &#3627409150;&#3627408478; với q∈&#3627408441; và &#3627409150;∈ Γ
*
.
Ô tô mát M’ làm việc trên xâu x như sau:
Bởi quy tắc (3-5): X0q’0x⟹
*
M’X0Z0q0x
Bởi quy tắc (3-6), M’ bắt chước hoạt động của M và cho:
X0q’0x⟹
*
M’X0Z0&#3627409150;&#3627408478;
Bởi các quy tắc (3-7) và (3-8) còn tiếp tục làm việc và cho:
X0&#3627409150;q⟹
*
M’qe
Vậy thì X0q’0x⟹
*
M’qe nghĩa là x∈&#3627408449;(&#3627408448;′).
Ngược lại, cũng bằng cách tương tự, ta có thể chứng minh rằng nếu x
∈&#3627408449;(&#3627408448;′) thì:
x∈&#3627408447;(&#3627408448;).
Định lý III.5
Cho L=N(M) trong đó M là ô tô mát đẩy xuống. Tồn tại một ô tô mát
đẩy xuống M’ sao cho L=L(M’).
Chứng minh
Giả sử M=(∑, Q, Γ,&#3627409151;, q0, Z0, ∅)
Ô tô mát M’ có thêm hai trạng thái mới là q’0 và qf, cũng như một ký
hiệu đáy stack mới X0.
M’=(∑, Q ∪ {q’0, qf},Γ∪{X0}, &#3627409151;
′
, q’0, X0, {qf}) https://dethithptquocgia.com/

43

Ô tô mát M’ đầu tiên đặt ký hiệu đáy stack Z0 của M lên trên ký hiệu đáy
stack X0 của nó, đồng thời chuyển qua trạng thái q0:
(3-10) &#3627409151;′(X0, q’0,&#3627409152;)={(X0, Z0,q0)}
Tiếp đó ô tô mát M’ rập theo hoạt động của M:
(3-11) Với mọi q∈Q: &#3627409151;′(X0, q’0,&#3627409152;)={(&#3627409152;,qf)}
Các quy tắc (3-10), (3-11) đã định nghĩa đầy đủ &#3627409151;′.
Việc chứng minh L(M’)=N(M) được thực hiện tương tự như ở Định lý III.4
https://dethithptquocgia.com/

44

3.2. Tương đương giữa ô tô mát đẩy xuống và văn phạm phi ngữ cảnh
Chúng ta sẽ chứng minh rằng lớp các ngôn ngữ phi ngữ cảnh là trùng
với lớp các ngôn ngữ được các ô tô mát đẩy xuống thừa nhận.
Từ văn phạm phi ngữ cảnh đến ô tô mát đẩy xuống
Theo tài liệu [7], tác giả Phan Huy Khánh, có viết “Một ngôn ngữ là phi
ngữ cảnh nếu và chỉ nếu ngôn ngữ đó đước thừa nhận bởi một ôtômat đẩy
xuống.”.
Từ đó ta có Định lý III.6.
Định lý III.6
Nếu L là một ngôn ngữ phi ngữ cảnh, thì tồn tại một ô tô mát đẩy xuống
M mà L=N(M)
Chứng minh
Giả sử G=(∑, ∆,??????,&#3627408451;) là căn phạm phi ngữ cảnh sản sinh L. Ô tô mát M
mà L=N(M) chỉ có một trạng thái q:
M=(∑,{&#3627408477;},∑∪∆,&#3627409151;,&#3627408478;,??????,∅)
Vậy M bắt đầu quá trình đoán nhận với duy nhất một ký hiệu đầu S của
văn phạm ở trong stack.
Nếu đỉnh là một ký hiệu không thể kết thúc A, ô tô mát M mô phỏng sự
viết lại bởi một quy tắc A→&#3627409148; của văn phạm G, bằng cách này thay A bởi &#3627409148;
nhưng theo trật tự đảo ngược (&#3627409148;
R
) để cho ký hiệu đầu tiên của &#3627409148; trở thành
đỉnh stack mới:
(3-12) Với mọi A∈∆: &#3627409151;(??????,&#3627408478;,&#3627409152;)={(&#3627409148;
R
, q) | A→&#3627409148;∈&#3627408451;}
Nếu đỉnh stack là một ký hiệu kết thúc a, thì ô tô mát đọ nó với ký hiệu
đọc được ở xâu vào, và nếu bằng nhau thì dỡ a khỏi stack:
(3-13) Với mọi a∈∑: &#3627409151;(&#3627408462;,&#3627408478;,&#3627408462;)= {(&#3627409152;,&#3627408478;)}
Các quy tắc (3-12) và (3-13) đã định nghĩa đầy đủ ở hàm dịch
chuyển
&#3627409151;.
Các quy tắc đó cho phép ô tô mát Mmoo phỏng một suy dẫn trái S⟹
*
x
đối với xâu vào x. Trong một suy dẫn như vậy thì mỗi dạng câu ?????? (tức là
một xâu trung gian trong suy dẫn) luôn có dạng ??????=ư&#3627409150; với u∈∑
*
, &#3627409150;∈
∆.(∑∪∆)
*
∪{&#3627409152;} và u là một tiền tố của xâu x, nghĩa là ∃&#3627408486;:&#3627408485;=&#3627408482;&#3627408486;. Giả sử
&#3627409150;=??????&#3627409150;’, A sẽ được thay thế bởi nhờ áp dụng một quy tắc A→&#3627409148;. Bây giờ
các ký hiệu kết thúc đứng đầu xâu &#3627409148;&#3627409150;’ chắc chắn phải là các ký hiệu đứng
đầu y. Lưu ý rằng ô tô mát M ghi nhớ phần &#3627409150; của dạng câu ?????? trong stack của
nó, nhưng theo chiều ngược, bởi vì stack (trong xâu hình trạng) luôn luôn
hướng sang phải, trong khi xâu &#3627409150; tiến theo chiều LIFO lại từ bên trái https://dethithptquocgia.com/

45

1) Hãy chứng minh L⊆&#3627408449;(&#3627408448;)
Trước hết ta chứng minh bằng quy nạp I trên mệnh đề sau đây:
Nếu S⟹
i
Gu&#3627409150; với u∈∑
*
và &#3627409150;∈∆∪(∑∪∆)
*
∪{&#3627409152;}, thì Squ⟹
*
M&#3627409150;
R
q
• Với i=0, mệnh đề đúng (với u=&#3627409152;,&#3627409150;=S).
• Giả thiết là mệnh đề đã nghiệm đúng cho đến i và xét suy dẫn có độ dài
i+1:
S⟹
i
GuAβ⟹G uvαβ,
Trong đó A→&#3627408483;&#3627409148;∈&#3627408451; và u,v∈∑
*
, &#3627409149;∈(∑∪∆)
*
, &#3627409148;∈(∑∪∆)
*
∪{&#3627409152;}.
Từ giả thiết quy nạp ta có:
Squ⟹
*
Mβ
R
Aq
Bởi tính chất hợp thành các suy dẫn ta có:
Squv⟹
*
Mβ
R
Aqv
Vì rằng A→&#3627408483;&#3627409148;∈&#3627408451;, cho nên (α
R
v
R
,q)∈&#3627409151;(??????,&#3627408478;,&#3627409152;).
Từ đó: Squv⟹
*
Mβ
R
α
R
v
R
qv⟹
*
Mβ
R
α
R
q,
Là điều cho phép kết thúc quy nạp.
Áp dụng mệnh đề vừa chứng minh vào trường hợp riêng ta có:
Nếu S⟹
*
Gx với x∈∑
*
, thì Sqx⟹
*
Mq
Vậy L(G)⊆N(M).
2) Bây giờ ta chứng minh &#3627408449;(&#3627408448;)⊆&#3627408447;
Trước hết ta chứng minh quy nạp trên i mệnh đề sau:
Nếu Squ⟹
i
M&#3627409150;
R
q với u∈∑
*
và &#3627409150;∈(∆∪&#3627409152;)
*
thì S⟹
*
G u&#3627409150;
• Với i=0, mệnh đề là đúng (&#3627408482;=&#3627409152;,&#3627409150;=??????).
• Giả thiết mệnh đề đã nghiệm đúng đối với mọi quá trình dịch chuyển của
M có chiều dài cho đến i.
Giả sử Squ⟹
i
M&#3627409150;
R
q là một quá trình dịch chuyển có độ dài là i+1.
Hai trường hợp có thể là:
Trường hợp một: Dịch chuyển cuối cùng thuộc loại (3-13):
Squ⟹
i
M&#3627409150;
R
aqa⟹M&#3627409150;
R
q, trong đó a∈∑
Bởi định lý III.1 ta có:
u=u’a và
Squ’⟹
i
M&#3627409150;
R
aq
Do giả thiết quy nạp, bấy giờ ta có giả thiết trong G: https://dethithptquocgia.com/

46

S⟹
*
G u′&#3627408462;&#3627409150;=u&#3627409150;
- Trường hợp hai: Dịch chuyển cuối cùng thuộc loại (3-12):
Squ⟹
i
M&#3627409150;
R
Aq⟹M&#3627409150;
R
α
R
q = &#3627409150;
R
q, trong đó &#3627409150;=&#3627409148;&#3627409149; và ??????→&#3627409148;∈&#3627408451;.
Do giả thiết quy nạp, ta có trong G:
S⟹
*
G&#3627408482;??????&#3627409149;.
Sử dụng tiếp quy tắc ??????→&#3627409148;, ta thu được:
S⟹
*
G&#3627408482;??????&#3627409149;⟹&#3627408482;??????&#3627409149;⟹&#3627408482;&#3627409150;,
là điều cho phép kết thúc quy nạp.
Áp dụng mệnh đề vừa chứng minh vào trường hợp riêng, ta có:
Nếu Sqx⟹
*
Mq thì S⟹
*
G x
Vậy &#3627408449;(&#3627408448;)⊆&#3627408447;(&#3627408442;).
Từ ô tô mát đẩy xuống đến văn phạm phi ngữ cảnh
Theo tài liệu [11], ta có Định lý III.7.
Định lý III.7
Cho một L=N(M) với M là một ô tô mát đẩy xuống, thế thì L là một
ngôn ngữ phi ngữ cảnh.
Chứng minh
Giả sử &#3627408448;=(∑,&#3627408452;,Γ,&#3627409151;,&#3627408478;0,&#3627408461;0,∅) là ô tô mát đẩy xuống thừa nhận L theo
stack rỗng.
Ta lập một văn phạm phi ngữ cảnh &#3627408442;=(∑,∆,&#3627408451;,??????) sao cho các suy dẫn
trái của nó mô phỏng sự hoạt động của M.
Đặt &#3627408440;={[&#3627408461;,&#3627408477;,&#3627408478;]|&#3627408461;∈Γ và p,q∈&#3627408452;} và ∆=&#3627408440;∪{??????} trong đó ??????∉&#3627408440;.
Tập các quy tắc P được thành lập như sau:
(3-14) Với mọi &#3627408478;∈&#3627408452;, ??????→[Z0, q0, q] là một quy tắc,
(3-15) Nếu (Xk…X2X1,p)∈&#3627409151;(&#3627408461;,&#3627408478;,&#3627408462;) trong đó k≥1 và X1,X2,…,Xk∈
Γ thì với mọi s1, s2,…,sk∈&#3627408452;
[Z,q,sk] →&#3627408462;[X1,p,s1] [X2,s1,s2]…[ Xk, sk-1,sk] là một quy tắc.
(3-16) Nếu (&#3627409152;,&#3627408479;)∈&#3627409151;(&#3627408461;,&#3627408478;,&#3627408462;) thì [Z,q,a] →&#3627408462; là một quy tắc
Văn phạm G được thành lập như trên là nhằm tới tính chất sau:
Mỗi suy dẫn trái sinh ra một xâu&#3627408485;∈∑
*
trong G mô phỏng một quá trình
dịch chuyển của ô tô mát M thừa nhận xâu x. Mỗi dạng câu trong suy dẫn đó
có dạng &#3627408482;&#3627409150;, trong đó &#3627408482;∈∑
*
, &#3627409150;∈∆
*
; dạng câu đó phản ánh một tình huống
của ô tô mát M: u là phần đã đọc của xâu x và xâu &#3627409150;
R
là nội dung stack. https://dethithptquocgia.com/

47

Để chứng minh rằng &#3627408447;(&#3627408442;)⊆&#3627408449;(&#3627408448;), trước hết ta chứng minh bằng quy nạp
trên I mệnh đề sau đây:
(a) Nếu [Z,q,r] ⟹
i
G w∈∑
*
thì Zqw⟹
*
M r
▪ Với i=0 mệnh đề đúng, vì [Z,q,r]→w là một quy tắc (với w∑∈∪{&#3627409152;}), từ đó
bởi các thành phần lập (3-16), (&#3627409152;,&#3627408479;)∈&#3627409151;(&#3627408461;,&#3627408478;,&#3627408484;), vậy Zqw⟹
*
M r
▪ Giả sử mệnh đề đã nghiệm đúng với mọi suy dẫn có độ dài cho đến I, ta
chứng minh nó cũng đúng với một suy dẫn có độ dài i+1, trong đó i≥1.
Dựa vào định nghĩa của các quy tắc, thì một số suy dẫn có độ dài i+1 với (i≥
1) có thể được viết thành như sau:
[Z,q,r] ⟹Ga[X1,s0,s1] [X2,s1,s2]…[ Xk, sk-1,sk] ⟹
i
Gw
Trong đó a∈∑∪{&#3627409152;}, k≥1, sk=r và (Xk…X2X1,s0)∈&#3627409151;(&#3627408461;,&#3627408478;,&#3627408462;)
Theo tính chất phân rã các suy dẫn phi ngữ cảnh (Định lý III.1) tồn tại các
số nguyên n1,…,nk và các xâu w1,…,wk sao cho w=aw1…wn, i=n1+…+nk và với j
từ 1 tới k:
[xj,sj-1,sj] ⟹
n
j Gwj.
Vì nj≤&#3627408470;, ta có thể vận dụng giả thiết quy nạp cho các suy dẫn cho các suy
dẫn có độ dài nj và bởi thế:
(b) Với j từ 1 tới k: Xjsj-1wj⟹
*
Msj
Lại vì có (Xk…X2X1,s0)∈&#3627409151;(&#3627408461;,&#3627408478;,&#3627408462;) ta có:
(c) Zqaw1…wk⟹MXk…X2X1s0w1w2…wk
Tổ hợp (b) và (c), nhờ cào tính chất hợp thành các suy dẫn trong hệ viết lại,
ta thu được Zqw⟹
*
Mr
Vậy tính chất (a) là đúng với mọi số nguyên i.
Cho w∈&#3627408447;(&#3627408442;). Bởi định nghĩa của các quy tắc trong G, tồn tại một trạng thái
q và một số nguyên i sao cho: S⟹G[Z0, q0, q] ⟹
i
w
Bởi tính chất (a) ta có: Z0q0w⟹
*
Mq
Vậy w∈&#3627408449;(&#3627408448;).
N(M)⊆&#3627408447;(&#3627408442;): Chứng minh xin được chuyển thành bài tập. Để thực hiện
chứng minh rằng, ta cần sử dụng tính chất phân rã các quá trình dịch chuyển.
https://dethithptquocgia.com/

48

Thí dụ 3.2:
Cho M=({a,b},{q0, q1},{a,Z},&#3627409151;,q0,Z,∅). Hàm dịch chuyển &#3627409151; cho như
sau:
&#3627409151;(Z,q0,a)={(Za,q0)} &#3627409151;(a,q1,b)={(&#3627409152;,q1)}
&#3627409151;(a,q0,a)={(aa,q0)} &#3627409151;(a,q1,&#3627409152;)={(&#3627409152;,q1)}
&#3627409151;(a,q0,b)={(&#3627409152;,q1)} &#3627409151;(Z,q1,&#3627409152;)={(&#3627409152;,q1)}

Dễ thấy rằng N(M)={a
i
b
j
| 1≤&#3627408471;≤&#3627408470;}
Ta thành lập văn phạm tương đương với ô tô mát theo phương pháp đưa
ra trong định lý III.7.
Ta chỉ cần lập các quy tắc cho các ký hiệu là đến được từ S.
S→[Z,q0,q0] | [Z,q0,q1]
Từ (Za, q0)∈&#3627409151;(&#3627408461;,q0,a) ta thu được:
[Z,q0,q0]→ a[a, q0, q0] [Z,q0,q0] | a[a, q0, q1] [Z,q1,q0]
[Z,q0,q1]→ a[a, q0, q0] [Z,q0,q1] | a[a, q0, q1] [Z,q1,q1]
Từ (aa,q0)∈&#3627409151;(&#3627408462;,q0,a) ta thu được:
[a,q0,q0]→ a[a, q0, q0] [a,q0,q0] | a[a, q0, q1] [a,q1,q0]
[a,q0,q1]→ a[a, q0, q0] [a,q0,q1] | a[a, q0, q1] [a,q1,q1]
Ta còn nhận được:
[a,q0,q1]→ b Vì (&#3627409152;,q1)∈&#3627409151;(a,q0,b)
[a,q1,q1]→ b|&#3627409152; Vì (&#3627409152;,q1)∈&#3627409151;(a,q1,b)∩&#3627409151;(a,q1,&#3627409152;)
[Z,q1,q1]→ &#3627409152; Vì (&#3627409152;,q1)∈&#3627409151;(Z,q1,&#3627409152;)
Nếu loại bỏ các ký hiệu vô sinh ta được văn phạm:
S→[Z,q0,q1]
[Z,q0,q1]→ a[a, q0, q1] [Z,q1,q1]
[a,q0,q1]→ a[a, q0, q1] [a,q1,q1]
[a,q0,q1]→ b
[a,q1,q1]→ b|&#3627409152;
[Z,q1,q1]→ &#3627409152;
https://dethithptquocgia.com/

49

CHƯƠNG 4. TỔNG QUAN VỀ TRÌNH BIÊN DỊCH
4.1. Ngôn ngữ lập trình
Mở đầu
Từ ngàn xưa con người muốn giao tiếp với nhau phải dùng ngôn ngữ. Vậy
người 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 (programming). Ngôn
ngữ dùng để lập trình được gọi là ngôn ngữ lập trình (programming language).
Viết chương trình để giải quyết vấn đề sẽ dễ dàng và tự nhiên hơn nếu ngôn
ngữ lập trình gần với vấn đề cần giải quyết. Có nghĩa là ngôn ngữ phải chứa đựng
các cấu trúc thuật ngữ, phần tử dùng để miêu tả vấn đề và không phụ thuộc
vào máy tính cụ thể.
Các ngôn ngữ lập trình có tính chất như trên được gọi là ngôn ngữ cấp cao.
Nhưng máy tính chỉ hiểu, chỉ chấp nhận ngôn ngữ cấp thấp riêng của mình, đó là
chuỗi các số 0 và 1, chuỗi số đó lại không gần gũi chút nào đối với con người.
Việc phân cấp ngôn ngữ lập trình được dựa trên cơ sở của tính không phụ
thuộc với máy tính ngày càng cao của các ngôn ngữ.
Phân loại
Ngôn ngữ máy (machine language),
Hợp ngữ (assembly language),
Ngôn ngữ cấp cao (higher-level language).
Bởi vì máy tính chỉ có thể hiểu ngôn ngữ máy cho nên một chương trình viết

trong ngôn ngữ cấp cao cuối cùng rồi cũng được dịch sang ngôn ngữ máy. Công
cụ
thực hiện việc dịch đó được gọi là chương trình dịch (translator).
Chương trình dịch được chia làm hai loại: trình biên dịch (compiler) và trình

thông dịch (interpreter).
Trình biên dịch: chuyển một chương trình viết trong ngôn ngữ cấp cao
chương trình nguồn sang chương trình trong ngôn ngữ cấp cao khác hoặc ngôn
ngữ máy − chương trình đích.
Thời gian chuyển một chương trình nguồn sang chương trình đích được

gọi là thời gian dịch (compile time).
Thời gian mà chương trình đích được thực thi được gọi là thời gian thực

thi (run time).
https://dethithptquocgia.com/

50

Hình 4.1 Sơ đồ trình biên dịch
Như vậy, đối với trình biên dịch, chương trình nguồn và dữ liệu được
xử lý
trong thời gian khác nhau, đó là thời gian dịch và thời gian thực thi.
Trình thông dịch: quá trình xử lý dạng bên trong của chương trình
nguồn và dữ liệu cùng một thời gian.

Hình 4.2 Sơ đồ trình thông dịch
Một số trình thông dịch làm việc như sau: phân tích từng phát biểu và
thực
thi luôn.
Hiện nay trình thông dịch đa phần áp dụng kỹ thuật của trình biên
dịch là
biên dịch chương trình nguồn sang dạng mã trung gian. Từ mã trung
gian sẽ được
thực thi bằng trình thông dịch.
Cú pháp và ngữ nghĩa
Để tiện lợi hơn trong đặc tả và hiện thực sự biên dịch, ta coi sự biên dịch
bao
gồm hai phép chiếu đơn giản hơn.
Thứ nhất là phép ánh xạ cú pháp (syntactic mapping), nó ánh xạ một
chương trình viết trong ngôn ngữ nguồn sang cấu trúc là đối số của phép
ánh xạ tiếp theo, đó là phép ánh xạ ngữ nghĩa (semantic mapping).
Cấu trúc của phép ánh xạ cú pháp là cây cú pháp (syntactic tree). Sau
đây là thí dụ cây cú pháp được xây dựng như thế nào trên chuỗi nhập
vào là một câu tiếng Anh. Mỗi câu tiếng Anh được bẻ ra thành những ký
hiệu cú pháp nhờ vào các luật văn phạm.
https://dethithptquocgia.com/

51

Thí dụ 4.1:
Chuỗi ký tự a + b  c có cây cú pháp A sau:

Hình 4.3 Cây cú pháp A
Qua thí dụ trên ta thấy rằng với mỗi câu của ngôn ngữ đêu tồn tại cây cú

pháp
của nó. Quá trình tìm ra cây cú pháp của một câu, được gọi là quá trình
phân
tích cú pháp câu đó (syntactic analysis parsing). Quá trình phân tích cú
pháp được
thực hiện dựa trên cơ sở các luật cú pháp của ngôn ngữ (đó chính là
các quy tắc
hay luật sinh). Cú pháp của ngôn ngữ là tập luật sinh, nó cung cấp
cho ta mối quan
hệ giữa mỗi câu của ngôn ngữ với cấu trúc cú pháp.
4.2. Trình biên dịch
Định nghĩa
Theo tài liệu [6], tác giả: Nguyễn Gia Định, có viết “Trình biên dịch là
chương trình dùng để đọc một chương trình được viết trong một ngôn ngữ lập
trình được gọi là ngôn ngữ nguồn (source language) và dịch chương trình đó
sang chương trình tương ứng trong ngôn ngữ khác, ngôn ngữ đích …”
Từ đó ta có Định nghĩa IV.1.
Định nghĩa IV.1
Trình biên dịch là chương trình dùng để đọc một chương trình được viết

trong một ngôn ngữ lập trình được gọi là ngôn ngữ nguồn (source language)
và
dịch chương trình đó sang chương trình tương ứng trong ngôn ngữ khác, ngôn
ngữ
đích (target language).
Như vậy ta sẽ có rất nhiều trình biên dịch, vì ta có hàng ngàn các ngôn
ngữ nguồn từ những ngôn ngữ lập trình họ cổ điển (Fortran, Pascal) đến các
b https://dethithptquocgia.com/

52

ngôn ngữ đặc biệt đã xuất hiện rất nhiều trong lĩnh vực ứng dụng máy
tính.
Các phần của trình biên dịch
Chương trình nguồn trong ngôn ngữ lập trình không gì khác là chuỗi
các ký
tự. Trình biên dịch có nhiệm vụ chuyển chuỗi ký tự này sang chuỗi
ký tự khác - đó
là mã đối tượng. Quá trình này bao gồm các quá trình nhỏ
hơn và được đặt tên như
sau:
Phân tích từ vựng.
Bảng danh biểu và thông báo lỗi.
Phân tích cú pháp.
Phân tích ngữ nghĩa.
Sinh mã trung gian.
Tối ưu mã trung gian.
Sinh mã đối tượng.
Đối với một trình biên dịch tồn tại trong thực tế, thứ tự các quá trình
nhỏ có
thể hơi khác so với thứ tự ở trên. Có thể một số quá trình nhỏ kết
hợp lại với nhau
thành một quá trình duy nhất. Trình biên dịch phải có
khả năng nhận biết chuỗi
nhập vào có phải là một chương trình hợp lệ cú
pháp không. Nếu không, trình biên
dịch phải thông báo lỗi.
4.2.2.1. Phân tích từ vựng (lexical analysis)
Giai đoạn phân tích từ vựng là giai đoạn đầu của quá trình biên dịch.
Dòng nhập vào trình biên dịch là chuỗi các ký tự cho phép của một ngôn ngữ
lập trình, cũng là chuỗi nhập vào bộ phân tích từ vựng.
Chẳng hạn, đối với ngôn ngữ Pascal, các ký tự alphabet là các ký tự sau:
A…Z, a…z, $ @ 0 1 2…9 dấu trống − + = := /  ( ), & >=…
Trong chương trình nguồn, sự kết hợp một số ký tự alphabet sẽ tạo nên
một thực thể của ngôn ngữ. Chẳng hạn, BEGIN là sự kết hợp 5 ký tự B, E,
G, I, N tạo nên thực thể là từ khoá BEGIN.
Các thực thể:
Ký hiệu trống, dấu tab, dấu xuống hàng,
Từ khoá: begin, end, goto, while, do, integer…,
Chuỗi các ký tự số tượng trưng cho hằng số,
Danh biểu, dùng để đặt tên cho các biến, hàm thủ tục, nhãn,
Các ký hiệu đặc biệt: +, −, /, , :=, ;, =, >, >=, <, <=, được gọi là các
token. https://dethithptquocgia.com/

53

Nhiệm vụ của bộ phân tích từ vựng là khi tiếp nhận chuỗi ký tự nhập phải
biết nhóm các ký tự thành các thực thể cú pháp token. Token là ký hiệu kết thúc,
mỗi token sẽ có một cấu trúc từ vựng. Cấu trúc từ vựng này là một cặp (loại token,
dữ liệu), gồm hai thành phần:
Thành phần thứ nhất là phạm trù cú pháp: hằng, biến.
Thành phần thứ hai là con trỏ, chỉ đến thông tin của token, được cất giữ
trong bảng, được gọi là bảng danh biểu (symbol table).
Với ngôn ngữ lập trình cho trước, số lượng loại token là hữu hạn. Tóm lại bộ
phân tích từ vựng là bộ dịch (translator) mà đầu nhập của nó là chuỗi các ký
tự, tượng trưng cho chương trình nguồn, đầu ra là các token. Dạng đầu ra này
là đầu nhập của bộ phân tích cú pháp.
Thí dụ 4.2:
Chương trình nguồn là phát biểu gán trong ngôn ngữ Pascal:
COST:=(PRICE+TAX)65
Bộ phân tích từ vựng có nhiệm vụ nhận biết: COST, PRICE, TAX là nhóm
token thuộc loại danh biểu, 65 là token thuộc loại hằng. Các ký tự :=, (, ), +,  tự
bản thân là token.
Giả sử tất cả các hằng, danh biểu là các token có loại <num> và <id>. Thành
phần thứ hai là dữ liệu, ở đây chính là con trỏ chỉ đến vị trí của các token đó trong
bảng danh biểu, chứa đựng trị từ vựng (lexeme) của token và các thuộc tính khác
của token. Thành phần thứ nhất của token sẽ được dùng trong giai đoạn phân
tích cú pháp. Thành phần thứ hai của token được dùng trong giai đoạn xử lý ngữ
nghĩa và sinh mã đối tượng.
4.2.2.2. Bảng danh biểu và thông báo lỗi
Các token được bộ phân tích từ vựng nhận biết và các thông tin của từng
token sẽ được lưu chứa trong bảng danh biểu. Xét phát biểu trong Thí dụ 4.2. Sau
hi phát biểu được đi qua bộ phân tích từ vựng, bảng danh biểu sẽ chứa các thông
tin sau:
https://dethithptquocgia.com/

54

Bảng IV.1 Bảng danh biểu 1
Nếu bộ phân tích từ vựng nhận tiếp các chuỗi ký tự của chương trình
nhập, để nhận dạng token, thì bảng danh biểu cũng thường xuyên được truy
xuất. Hành vi truy xuất nhằm hai mục đích: nếu danh biểu vừa được nhận
dạng đã được lưu chứa trong bảng danh biểu thì phần thứ hai của token là
dữ liệu sẽ được cập nhật bằng chỉ số của danh biểu đó trong bảng danh biểu.
Thí dụ 4.3:
COST có chỉ số là 1 trong bảng danh biểu, COST lại xuất hiện trong
chuỗi nhập sau:
y:=COST2.0
Chuỗi xuất ra của bộ phân tích từ vựng là:
id5:=id1num6 (id, 5):=(id, 1)(num, 6)
Trong trường hợp này COST không cất vào bảng danh biểu nữa,
nhưng bộ phân tích từ vựng sẽ đẩy ra token (id, 1), 1 là vị trí COST đã
được cất trong bảng danh biểu trước đó.
Bảng danh biểu thường xuyên được truy xuất để thêm hoặc truy xuất
các token, do đó phải thoả mãn hai điều kiện:
• Thực hiện nhanh các thao tác thêm token, hoặc các thông tin của token.
• Có khả năng truy xuất nhanh các thông tin của một token.
Phát hiện và thông báo lỗi
Ở mỗi giai đoạn của quá trình biên dịch một chương trình nguồn đều
có thể có lỗi. Như vậy sau khi phát hiện một lỗi, trình biên dịch xem xét
lỗi đó xem có tiếp tục quá trình dịch hay không. Tất nhiên, nếu một trình
biên dịch mà ngay khi phát hiện lỗi đầu tiên đã dừng chương trình thì không
hữu hiệu.
Trong giai đoạn phân tích từ vựng và cú pháp thường xuất hiện nhiều
lỗi do trình biên dịch phát hiện. Trong lúc phân tích từ vựng, lỗi được phát
hiện khi phần còn lại trên băng nhập không thể tạo nên token. Lỗi xảy ra khi
Chỉ số Token Lexeme Các thông tin khác
1 id COST Biến thực
2 id PRICE Biến thực
3 id TAX Biến thực
4 num 65 Hằng số nguyên https://dethithptquocgia.com/

55

bộ phân tích cú pháp không thể xây dựng cấu trúc cú pháp cho chuỗi token cho
trước. Lỗi cũng có thể được phát hiện trong quá trình phân tích ngữ nghĩa, khi
trình biên dịch kiểm tra kiểu dữ liệu của hai toán hạng thuộc một phép toán
không phù hợp. Chẳng hạn, một toán hạng thuộc kiểu dãy, cộng với một toán
hạng là tên của chương trình con.
4.2.2.3. Phân tích cú pháp (Syntactic analysis parsing)
Chuỗi xuất ra từ bộ phân tích từ vựng là các token có dạng (loại token, dữ
liệu), sẽ là chuỗi nhập vào bộ phân tích cú pháp. Bộ phân tích cú pháp chỉ
xét thành phần thứ nhất của token là loại token.
Sự phân tích cú pháp là một quá trình, trong quá trình này chuỗi các token sẽ
được kiểm tra xem có thể được biểu diễn bằng cấu trúc cú pháp của ngôn ngữ
lập trình cho trước hay không, Nếu tồn tại một cấu trúc cú pháp cho chuỗi nhập
thì cấu trúc được sinh ra đó chính là kết quả của quá trình phân tích cú pháp. Ở
giai đoạn sinh mã, cấu trúc cú pháp sẽ được xem xét để từ đó sinh ra mã cho chuỗi
ký tự của chương trình nguồn.
4.2.2.4. Phân tích ngữ nghĩa
Sau giai đoạn phân tích cú pháp, cấu trúc cú pháp của chuỗi nhập sẽ được bộ
phân tích ngữ nghĩa xử lý. Bộ phân tích ngữ nghĩa sẽ kiểm tra lỗi về ngữ nghĩa..
Một nhiệm vụ quan trọng mà bộ phân tích ngữ nghĩa thực hiện là kiểm tra loại
dữ liệu. Dựa trên cây cú pháp, bộ phân tích ngữ nghĩa sẽ xử lý từng phép toán.
Với mỗi phép toán, nó sẽ xét các toán hạng xem loại dữ liệu của chúng có cho
phép để tham gia vào phép tính đó không (nói cách khác loại dữ liệu của các
toán hạng trong phép toán cụ thể, có được ngôn ngữ lập trình định nghĩa không).
Thí dụ 4.4:
a + 1 với a là biến thuộc loại dữ liệu số thực, 1 là thuộc loại luận lý. Vậy phép
cộng không thể thực hiện với hai toán hạng loại số thực và loại luận lý.
Hoặc: a + n với a là số thực và n là số nguyên
Khi kiểm tra thấy hai toán hạng của phép cộng một có trị thực, một có trị
nguyên thì hầu hết các trình biên dịch sẽ chuyển trị của toán hạng n sang biểu
thức số thực, cụ thể nếu n có trị là 10 thì trị 10 sẽ được chuyển sang trị thuộc loại
thực 10.0 để cộng với trị của a. https://dethithptquocgia.com/

56

Hình 4.4 Cây cú pháp B
Trị 65 sẽ được chuyển sang số thực. Cây cú pháp khi xử lý ngữ nghĩa
sẽ có dạng như trên.
4.2.2.5. Sinh mã trung gian
Sau giai đoạn phân tích cú pháp và ngữ nghĩa, một số trình biên dịch
đã tạo ra sự biểu diễn trung gian của chương trình nguồn. Sự biểu diễn
trung gian của chương trình nguồn được hiểu như là chương trình của
máy tính trừu tượng (abstract machine).
Ngôn ngữ được dùng cho máy trừu tượng là mã trung gian. Mã trung
gian có hai đặc điểm quan trọng: dễ được sinh ra và dễ chuyển sang mã
đối tượng của chương trình đích. Với Thí dụ 4.4, kết quả của giai đoạn sinh
mã trung gian có dạng:
temp p1 := intoreal (trị số bằng 65)
temp p2 := id2 + id3 (4-1)
temp p3 := temp p2  temp p1
id1 := temp p3
4.2.2.6. Tối ưu mã trung gian
Giai đoạn này sẽ thu giảm một số bước trong mã trung gian nhằm làm
cho khi sinh ra mã đối tượng thì thời gian thực thi mã đối tượng sẽ ngắn hơn.
Bước sinh mã sẽ dùng cây cú pháp đã được xử lý ngữ nghĩa (đã qua
bước phân tích ngữ nghĩa) để sinh mã trung gian.
Cách làm thông thường như sau:cứ ứng với nút là toán tử sẽ sinh ra mã
trung gian như ở (4-1). Tuy vậy, có cách tốt hơn là với (4-1) chỉ cần hai
mã trung gian mà thôi.
temp p1 := id2 + id3 (4-2) https://dethithptquocgia.com/

57

id1 := temp p1 + 65.0
Việc thu giảm như trên sẽ được thực hiện ở bước tối ưu mã. Bước
chuyển số nguyên sang số thực sẽ được thực hiện ngay trong thời gian dịch, do
đó phép toán intoreal sẽ được bỏ đi. Xem lại (4-1), ta thấy ở mã thứ tư id1 :=
temp p3, với temp p3 chỉ dùng có một lần là gán trị vào id1, do đó có thể ghép
mã thứ 3 và thứ 4 thành mã thứ 2 của (4-2).
Còn rất nhiều trường hợp khác mà trình biên dịch thực hiện tối ưu mã. Ở đây
một vấn đề nảy sinh là thực hiện tối ưu mã trong thời gian biên dịch sẽ làm
thời gian dịch tăng lên trong giai đoạn này. Tuy nhiên một số trường hợp tối ưu
mã cho phép nếu thời gian thực thi của chương trình đích được rút ngắn mà
không làm sự biên dịch quá lâu.
4.2.2.7. Sinh mã đối tượng
Giai đoạn cuối của trình biên dịch là sinh mã đối tượng. Mã đối tượng có thể
là mã máy định vị lại địa chỉ hoặc mã hợp ngữ.
Thí dụ 4.5:
Ta sử dụng hai thanh ghi 1 và 2, để dịch mã trung gian (4-2) sang mã
hợp ngữ:
movF id2, R1 movF id3, R2
addF R2, R1 (4-3)
mulF # 65.0, R1
movF R1, id1
Lưu ý rằng movF, addF, mulF là phép tính với số thực. Chỉ thị đầu thực hiện

chuyển trị từ vị trí nhớ có tên PRICE, thuộc loại token id2 vào thanh ghi R1. Chỉ
thị
thứ hai thực hiện chuyển trị ở vị trí nhớ có tên TAX thuộc loại token id3 vào
thanh
ghi R2. Chỉ thị thứ ba thực hiện phép cộng nội dung hai thanh ghi R1 và
R2, kết quả
phép toán được cất trong R1. Chỉ thị thứ tư thực hiện phép nhân hằng
có trị số thực 65.0 với trị nằm trong thanh ghi R1. Chỉ thị cuối cùng chuyển nội
dung trong thanh
ghi R1 vào vị trí nhớ có tên COST thuộc loại token id1.
4.3. Ứng dụng của ngôn ngữ hình thức và ôtômat với trình biên dịch
Các phần trước của chương này ta có nói chuỗi ký tự nhập vào trình
biên dịch là văn bản của chương trình nguồn. Đúng vậy, song văn bản đó lại
có thể là sản phẩm đầu ra của một hoặc nhiều bộ tiền xử lý (preprocessor) và
sản phẩm đầu ra của trình biên dịch có thể lại tiếp tục được xử lý trước khi trở
thành mã máy của máy tính thật. Trong phần này ta sẽ nói tới các mối liên quan
đó.
Bộ tiền xử lý https://dethithptquocgia.com/

58

Bộ tiền xử lý sẽ tạo ra chuỗi nhập vào trình biên dịch. Bộ tiền xử lý
thực hiện các chức năng sau:
Xử lý macro (macro processing). Bộ tiền xử lý có thể cho phép người sử
dụng định nghĩa các macro. Macro được hiểu là cách viết ngắn gọn cho cấu
trúc dài hơn.
Chêm tập tin (file inclusion). Bộ tiền xử lý có thể “nhét” các tập tin vào
chương trình văn bản. Chẳng hạn, tiền xử lý ngôn ngữ C sẽ “nhét” nội
dung của tập tin <global.h> vào thay thế cho phát biểu # include <global.h>
khi nó xử lý một tập tin có chứa phát biểu trên.
Bộ xử lý hoà hợp (Rational processor). Bộ tiền xử lý loại này sẽ tạo
nên sự hoà hợp giữa ngôn ngữ cổ điển với những cấu trúc điều khiển, cấu
trúc dữ liệu hiện đại hơn.. Chẳng hạn, bộ tiền xử lý giúp cho người sư dụng
có thể dùng các phát biểu có cấu trúc như while, if trong ngôn ngữ lập
trình, mà tự bản thân ngôn ngữ đó không có các phát biểu trên. Thực tế các
phát biểu while, if chính là các macro, khi người sử dụng viết một chương
trình trong ngôn ngữ cổ điển có dùng tới hai loại phát biểu có cấu trúc trên
và cần biên dịch ra ngôn ngữ máy thì bộ tiền xử lý sẽ làm việc trước. Tất cả
nơi nào có hai phát biểu while, if sẽ được thay thế bởi chuỗi các phát biểu
mà ngôn ngữ lập trình cổ điển có.
Mở rộng ngôn ngữ (language extension). Bộ tiền xử lý tăng khả năng
cho ngôn ngữ bằng một số các macro nội tại của nó. Thí dụ ngôn ngữ Equel
là ngôn ngữ hỏi đáp với cơ sở dữ liệu được nhúng vào ngôn ngữ C. Các
phát biểu được bắt đầu bằng hai dấu # # ở trong C được bộ tiền xử lý, xử
lý, là các phát biểu truy xuất cơ sở dữ liệu, không liên quan đến C, được dịch
thành các phát biểu gọi thủ tục, sẽ gọi các trình con đặc nhiệm trong mã máy
để thực hiện việc truy xuất cơ sở dữ liệu.
Bây giờ ta sẽ nói kỹ hơn về bộ xử lý macro. Bộ xử lý này thường làm
việc với hai loại phát biểu: định nghĩa macro và sử dụng macro.
Định nghĩa macro bao gồm: từ khoá define hoặc macro, tiếp theo
là tên macro. Theo sau là thân (body) của macro. Chẳng hạn, \define
<macroname> {<body>}.
Thông thường bộ xử lý macro cho phép các thông số hình thức
(formal parameter) trong định nghĩa, chúng là các ký hiệu sẽ bị thay thế bởi
các trị (chuỗi các ký tự) sau này khi macro được dùng.
Phát biểu dùng macro bao gồm: tên macro và các thông số thực
(actual parameter), là trị của các thông số hình thức trong thân của macro.
https://dethithptquocgia.com/

59

Thí dụ 4.5:
Hệ thóng đánh máy typesetting có phương tiện macro với phát biểu định

nghĩa macro như sau:
\define <macro name><template> {<body>}
<macrro name>: tên macro
<template> : danh sách thông số hình thức
<body> : thân macro
Macro định nghĩa ve sự trích dẫn của tạp chí ACM như sau:
\define\JACM #1; #2; #3
{{\S1 J.ACM}{\bf #1}: #2, pp. #3}
Tên macro là \JACM. Các thông số hình thức là #1, #2, #3 được ngăn cách

nhau bởi dấu ‘;’ và được kết thúc bằng dấu ‘.’.
Khi dùng macro, người sử dụng sẽ viết như sau: \JACM 17; 4; 715 – 728 sẽ

được hiểu như sau: J.ACM 17: 4, pp. 715 – 728.
Trình biên dịch hợp ngữ
Một số trình biên dịch cho sản phẩm ở đầu ra là mã hợp ngữ, chuỗi mã hợp

ngữ này sẽ được đưa sang trình biên dịch hợp ngữ xử lý tiếp. Một số trình
biên
dịch khác thực hiện luôn công việc của assembler, nghĩa là nó dịch ra luôn
mã máy
khả định vị (relocatable machine code), mã máy sẽ được chuyển trực
tiếp đến bộ
phận “loader/link editor.
Mã hợp ngữ là phiên bản gợi nhớ của mã máy, trong đó các tên sẽ được

dùng thay thế cho các mã nhị phân của các tác vụ và tên cũng được đại diện
cho
các địa chỉ của vị trí nhớ. Chẳng hạn, chuỗi chỉ thị trong mã hợp ngữ của phát
biểu
gán b := a+2.
mov a, R1
add #2, R1 (4-4)
mov R1, b
Ba chỉ thị thực hiện việc chuyển nội dung ở địa chỉ a vào thanh ghi R1, sau

đó cộng hằng số 2 với nội dung của R1 và kết quả được giữ lại trong thanh ghi
R1,
cuối cùng là chuyển nội dung của R1 vào địa chỉ b. Sau khi thực hiện ba chỉ
thị thì
máy thực sự đã thực hiện phát biểu gán b:=a+2. Thông thường hợp ngữ
cũng có
các phương tiện macro và bộ tiền xử lý macro.
Trình biên dịch hợp ngữ hai chuyến (two pass assembler)
Trình biên dịch hợp ngữ đơn giản nhất là biên dịch hai chuyến trên dữ liệu
nhập vào. Chuyến ở đây được coi là lần đọc tập tin nhập trọn vẹn. Ở chuyến https://dethithptquocgia.com/

60

đầu, toàn bộ danh biểu, đại diện cho vị trí nhớ sẽ được nhặt ra, cất vào bảng
danh biểu.
Bảng IV.2 Bảng danh biểu 2
Danh biểu Địa chỉ tương đối
a

b
0
4
Theo bảng bên, ta giả sử địa chỉ được đánh cho từng từ (một từ là
4 byte). a là danh biểu đại diện cho địa chỉ bắt đầu ở byte 0. b ở thứ 4. Ở
chuyến thứ hai, trình biên dịch hợp ngữ sẽ rà lại tập tin nhập một lần nữa.
Lần này nó sẽ dịch mã gợi nhớ (được đặt bằng tên) của tác vụ sang chuỗi mã
máy – mã nhị phân và phần tên danh biểu đại diện cho vị trí nhớ sẽ được
thay thế bằng địa chỉ tương đối của danh biểu đó trong bảng danh biểu.
Thí dụ 4.6:
Đoạn chỉ thị (4-4) được dịch sang mã máy là:
0001 010000000000*
0011 011000000010* (4-5)
0100 010000000100*
4 bit đầu là mã tác vụ 0001, 0011, 0100 là mã load, add, store. Hai
bit tiếp theo 01 ở ba chỉ thị là mã của thanh ghi 1. 2 bit tiếp theo là mã
thông báo cho biết 8 bit theo sau là địa chỉ hay toán hạng. Hai bit này
được gọi là mode địa chỉ nếu là 00 và mode trực tiếp – toán hạng nếu là
10. Vì vậy 8 bit của chỉ thị 1 và 3 là địa chỉ, ngược lại ở chỉ thị 2,
00000010 là toán hạng, hằng nguyên có trị 2.
Đầu ra chuyến thứ hai của trình biên dịch hợp ngữ là mã máy khả
định vị, nghĩa là chương trình trong dạng này có thể được chứa vào bộ nhớ
ở bất kỳ vị trí L nào. Như vậy địa chỉ tương đối trong bảng danh biểu sẽ được
tính lại, trở thành địa chỉ tuyệt đối, bằng cách lấy L cộng với địa chỉ tương
đối, việc này được thực hiện
cho tất cả các danh biểu trong bảng danh biểu. Quay lại (4-5), ta thấy ở
chỉ thị 1 và 3 thì 8 bit sau cùng là địa chỉ tương đối của danh biểu a, b. Giả
sử L=00001111, địa chỉ tuyệt đối của a, b là 00001111, 00010011. Ba chỉ thị
(4-5) được viết lại dưới dạng mã máy tuyệt đối:
0001010000001111
0011011000000010 (4-6)
0010010000010011
Bộ cất liên kết soạn thảo (loader/link editor) https://dethithptquocgia.com/

61

Loader là chương trình, thực hiện hai nhiệm vụ sau: cất và soạn thảo liên
kết. Quá trình cất bao gồm lấy mã máy khả định vị tính lại địa chỉ thành địa
chỉ tuyệt đối như ở thí dụ trên. Sau đó ta đem cất tất cả chỉ thị với các địa chỉ
tuyệt đối của danh biểu và dữ liệu vào trong bộ nhớ tại vị trí tương ứng như ở
(4-6).
Link editor cho phép ta tạo một chương trình duy nhất từ nhiều tập tin ở

dạng mã máy khả định vị của những lần biên dịch riêng biệt và từ những tập tin
thư
viện, do hệ thống cung cấp. Sự liên kết này tạo điều kiện thuận lợi cho
bất kỳ
chương trình nào cần tới chúng khi thực thi. Nếu có một số tập tin được
chương
trình khác tham chiếu, chúng sẽ được tham chiếu ngoài (external
reference). Trong
đó mã của tập tin này có thể tham chiếu đến một vị trí nhớ
trong tập tin khác. Có
nghĩa là vị trí nhớ chứa dữ liệu được khai báo trong một
tập tin lại có thể được truy
xuất ở tập tin khác. Hoặc thủ tục được khai báo trong
tập tin này lại được gọi trong tập tin khác.

Hình 4.5 Sơ đồ hoạt động loader
Mã khả định vị phải lưu giữ thông tin trong bảng danh biểu và tên các thủ
tục. Vì ta không thể biết được toàn bộ chương trình trong dạng mã khả
định vị
sẽ được chứa ở đâu trong bộ nhớ trong khi nó còn ở bộ nhớ ngoài, do đó
toàn https://dethithptquocgia.com/

62

bộ bảng danh biểu phải được lưu giũ đầy đủ như là một phần của chương
trình trong mã khả định vị.

https://dethithptquocgia.com/

63

CHƯƠNG 5. DEMO MỘT BÀI TOÁN
5.1. Cơ sở lý thuyết
Bài toán chuyển từ BTCQ sang NFAε
Nếu r là BTCQ thì tồn tại một NFA với ε-dịch chuyển chấp nhận L(r). Tức
là, khi đưa ra một BTCQ, sẽ có bộ năm biểu diễn được BTCQ đó.
Bộ năm đó là:
M=(S, ∑,,s0,F)
Trong đó:
S là tập hữu hạn các trạng thái, S={s0,s1,….sn}
∑ là bảng chữ vào
s0  S là trạng thái đầu
F  S là tập các trạng thái thừa nhận hay trạng thái cuối
hàm dịch chuyển  :S x {∑  ε→tập con của S
Việc của chúng ta bây giờ là đi tìm ra NFAε.
Phương hướng giải quyết
Chúng ta giả quyết bài toán theo quy nạp theo số phép toán.
 Xét r không có phép toán nào

Start Start a

r=ε r= r=a
 Xét r có I phép toán: r = r1 + r2, r = r1r2 hoặc r = r
*

• Xây dựng NFAε M1 = (S1, Σ1, δ1, s1, {f1}) và M2 = (S2, Σ2, δ2, s2, {f2}) sao
cho L(M1) = L(r1) và L(M2) = L(r2).

S0
S1 S0 St https://dethithptquocgia.com/

64

• Xây dựng NFAε M như sau:
+ Trường hợp 1: r = r1 + r2

+ Trường hợp 2: r = r1r2

+ Trường hợp 3: r = r
*

https://dethithptquocgia.com/

65

5.2. Demo ví dụ về sự tương đương giữa BTCQ và NFAε
Giao diện ban đầu
Sau khi khởi động, ta sẽ vào giao diện làm việc chính của phần mềm.

Hình 5.1 Giao diện làm việc của Demo
https://dethithptquocgia.com/

66

Tại giao diện này, ta sẽ tiến hành nhập BTCQ cần chuyển vào ô textbox.
Chú ý cần nhập theo chú thích hiện trên giao diện.
Trên giao diện đã nhập BTCQ: r = 01
*
|1 (ký hiệu “|” tương đương
với “+”).

Hình 5.2 Nhập BTCQ cần chuyển
Sau khi nhập BTCQ, click vào button “Chuyển sang NFAε” để chuyển
BTCQ sang NFAε.
Giao diện kết quả
Kết quả khi chuyển sang NFAε hiển thị ở dạng bảng trạng thái. https://dethithptquocgia.com/

67

Hình 5.3 Kết quả là bảng biểu diễn một NFAε
https://dethithptquocgia.com/

68

Bảng trạng thái trên giao diên kết quả thể hiện một NFAε khi chuyên
BTCQ:
r = 01
*
|1 (hay r = 01
*
+ 1). NFA ε trên cũng có thể biểu diễn bằng hình
vẽ như hình 5.4 dưới đây.

Hình 5.4 Một cách biểu diễn khác của NFAε
https://dethithptquocgia.com/

69

KẾT LUẬN
Kết quả đạt được:
Hoàn thành tìm hiểu tổng quan về văn phạm hình thức và các Automata,
trong đó đi sâu tìm hiểu văn phạm phi ngữ cảnh và Automata đẩy xuống.
Hoàn thành tìm hiểu và giới thiệu sơ lược về Trình biên dịch, một phần quan
trọng của học phần Chương trình dịch gắn bó chặt chẽ với Lý thuyết ngôn ngữ
hình thức và Automata.
Xây dựng được bản báo cáo chuyên đề hoàn chỉnh, và chương trình Demo
cơ bản thể hiện sự tương đương giữa DFA và NFA, là một dạng bài toán của
Automata đẩy xuống.
Hạn chế:
Do chuyên đề khá rộng, tài liệu về phần này còn khá ít, và trình độ còn hạn
chế nên chưa tìm hiểu được kỹ về lý thuyết ngôn ngữ hình thức.
Chương trình Demo còn sơ sài, đơn giản, chỉ thể hiện một dạng bài toán
trong số rất nhiều bài toán của chuyên đề này.
Phương hướng phát triển:
Tiếp tục nghiên cứu và tìm hiểu về ngôn ngữ hình thức và lý thuyết
Automata, mà chủ yếu là văn phạm phi ngữ cảnh và Automata đẩy xuống. Tìm
hiểu thêm về ứng dụng của ngôn ngữ hình thức và Automata đối với trình biên
dịch và một số lĩnh vực khác.
Xây dựng được chương trình Demo giải quyết nhiều bài toán của lĩnh vực
nghiên cứu này.
https://dethithptquocgia.com/

70

TÀI LIỆU THAM KHẢO
Tài liệu:
[1] PGs. Ts. Nguyễn Văn Ba, Lý thuyết ngôn ngữ và tính toán(2007), NXB
Đại học Quốc gia, Hà Nội.
[2] ThS. Trần Văn Lộc, Bài giảng Automat hữu hạn(2007), Tài liệu ngành
CNTT.
[3] Phan Đình Diệu, Bài giảng Ngôn ngữ hình thức và Ôtômat (2008), Đại
học Duy Tân, Hải Phòng
[4] Nguyễn Thị Trúc Viên, Bài giảng Lý thuyết Ôtômát và ngôn ngữ hình
thức (2006), Đại học Bách khoa, Tp.HCM.
[5] Ts. Nguyễn Văn Định, Otomat và Ngôn ngữ hình thức (2008), Tài liệu
ngành CNTT.
[6] Nguyễn Gia Định, Lý thuyết Ngôn ngữ hình thức và Ôtômát (2006), Đại
học Khoa học, Đại học Huế.
[7] PGs. Ts. Phan Huy Khánh, Giáo trình Ngôn ngữ hình thức và
Ôtômat(2008), Đại học Đà Nẵng.
[8] PGs. Ts. Đoàn Văn Ban, ThS.Nguyễn Hiền Trinh, Giáo trình Ngôn ngữ
hình thức và Ôtômát (2010), NXB Đại học Thái Nguyên.
[9] Nguyễn Quốc Thắng – Nguyễn Lâm Tùng, Giáo trình Lý thuyết văn
phạm, ngôn ngữ và ôtômat(2009), Đại học Thăng long.
[10] Trần Văn Cảnh, Bài giảng Lý thuyết Ngôn ngữ và Automat(2010), Đại
học Vinh.
Website tham khảo:
[11] Tailieu.vn
[12] Ebook.edu.vn
[13] Wordpress.com
https://dethithptquocgia.com/

71

NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN

.........................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................
.................................................................................................................................

GV HƯỚNG DẪN

Thiếu úy Cao Xuân Trường
SINH VIÊN THỰC HIỆN

Hoàng Văn Thao
https://dethithptquocgia.com/

Nghiên cứu Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata đẩy xuống

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Nghiên cứu Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata đẩy xuống

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77