Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8
ĐẠI HỌC ĐÀ NẴNG
ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA
TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA CÔNG NGHỆ THÔNG TIN
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO LIỂU LUẬN
BÁO CÁO LIỂU LUẬN
MÔN : LÝ THUYẾT TÍNH TOÁN
Giảng viên
Giảng viên
:
: GS. TS. Phan Huy Khánh
GS. TS. Phan Huy Khánh
Nhóm thực hiện:
Nhóm thực hiện:
Huỳnh Kim Tân
Huỳnh Kim Tân
Nguyễn Thị Hồng Thuý
Nguyễn Thị Hồng Thuý
Vũ Thị Diệu Thư
Vũ Thị Diệu Thư
Lớp:
Lớp:
KHMT K12
KHMT K12


tổng quát khác mà chúng ta sẽ học tạo thành các công cụ mạnh mẽ hỗ trợ mô tả và
phân tích các ngôn ngữ.
Ví dụ 1: Sử dụng các qui tắc văn phạm để mô tả ngôn ngữ.
Cho rằng ngôn ngữ L = {a,b}* của tất cả các chuỗi trên bảng chữ cái {a, b}.
Trong ví dụ 2.15, chúng ta đã thấy định nghĩa đệ quy của L được biễu diễn như sau:
1. A ∈ L
2. Cho bất cứ S ∈ L, Sa ∈ L.
3. Cho bất cứ S ∈ L, Sb ∈ L.
4. Không có các chuỗi khác thuộc L.
Cho rằng S ở đây là một biến, biễu diễn cho 1 phần tử bất kỳ của L, mà giá trị
của phần tử tồn tại bởi một vài kết nối của các qui tắc từ 1 đến 3. Qui tắc 1có dạng
khi chúng ta ghi S → A, chỉ định cách cho S một giá trị để A thay thế. Qui tắc 2 và 3
có thể được viết S → Sa và S → Sb. Điều này có nghĩa S cũng có thể được thay thể
bởi Sa hoặc Sb; ngoài ra phải tồn tại giá trị cuối bằng cách tiếp tục sử dụng các qui
tắc gán giá trị cho S mới.
Biểu tượng → được sử dụng cho từng qui tắc khi một biến được thay thế bởi
một chuỗi. Cho 2 chuỗi α và β, khi ký hiệu α ⇒ β có nghĩa là β có thể tồn tại bằng
cách cung cấp một trong những qui tắc đến một biến đơn trong xâu chuỗi α. Sử dụng
ký hiệu này trong ví dụ, chúng ta có thể viết:
S ⇒ Sa ⇒ Sba ⇒ Sbba ⇒ Abba = bba.
để mô tả thứ tự từng bước (ứng dụng của các qui tắc 2,3,3, và 1) được dùng để tồn tại
hoặc chuyển hóa, xâu chuỗi bba. Sự chuyển hóa kết thúc tại điểm thay thế S bằng
một xâu chuỗi thực của các ký hiệu bảng chữ cái (trong trường hợp A này); mỗi bước
tương tự trước khi gọi qui nạp, kể từu khi thay thế xâu chuỗi S bằng 1 xâu chuỗi vẫn
còn chứa 1 biến.
Thậm chí, có thể chú thích một cách đơn giản cho các ký hiệu | nghĩa là
“hoặc” và ghi 3 qui tắc đầu tiên như:
S → A | Sa | Sb
KHMTK12 - Nhóm 7 3
Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8

Các qui tắc văn phạm
S → aSb | A
Là một cách khác để mô tả ngôn ngữ L được định nghĩa như sau:
1. A ∈ L.
2. Cho mỗi x ∈ L, axb ∈ L.
3. Không có gì nữa trong L.
Ngôn ngữ L đơn giản được xem là ngôn ngữ bất qui tắc {a
n
b
n
| n ≥ 0}. Các qui
tắc văn phạm trong phần đầu của ví dụ 6.1, cho ngôn ngữ {a,b}*, cho phép a’s và b’s
được thêm vào một cách độc lập lẫn nhau. Ở đây, theo hướng xử lý khác, mỗi lần
một ký hiệu được thêm vào cuối mỗi xâu chuỗi bởi ứng dụng của qui tắc văn phạm S
KHMTK12 - Nhóm 7 4
Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8
→ aSb, ký hiệu ngược lại đồng thời được thêm vào cuối xâu chuỗi khác. Như vậy,
ràng buộc không chỉ một mà còn có thể sư dụng bởi bất cứ biểu thức qui tắc.
Ví dụ 6.3: Tính đối xứng.
Xem xét cả 2 ngôn ngữ pal của tính chất đối xứng trên bảng chữ cái {a, b} và
phần bổ sung N, tập hợp các thành phần không đối xúng trên {a, b}. Từ ví dụ 2.16,
chúng ta có định nghĩa qui nạp của pal :
1. A, a, b ∈ pal
2. Cho bất cứ S ∈ pal, aSa và bSb tồn tại trong pal.
3. Không có các xâu chuỗi khác trong pal.
Vì vậy, có thể mô tả pal trong văn phạm phi ngữ cảnh với các qui tắc văn
phạm:
S → A| a | b | aSa | bSb
Ngôn ngữ N cũng tuân theo qui tắc 2: Cho bất cứ x không đối xứng, cả hai axa
và bxb sẽ không đối xứng. Tuy nhiên, định nghĩa qui nạp của N không thể đơn giản

ý trong L, và thông thường để chứng tỏ một chuỗi S (biến bắt đầu). Sau đó, các biến
khác có thể xem như các chuỗi đặc trưng trong các ngôn ngữ hỗ trợ chắc chắn bao
hàm trong định nghĩa của L. (Chúng ta có thể vẫn giải thích văn phạm như định
nghĩa qui nạp của L, nếu mở rộng khái niệm qui nạp một cách không đáng kể bao
hàm cả ý tưởng của qui nạp lẫn nhau: đúng hơn một đối tượng được định nghĩa trong
các thời kỳ của chính nó, một vài đối tượng được định nghĩa trong các thời kỳ lẫn
nhau.)
Một định nghĩa tổng quát đưa ra từ các ví dụ này:
Giả sử G = (V, ∑, P, S) là một CFG. Như trong 3 ví dụ đầu, chúng ta sẽ duy trì
ký hiệu → cho các dẫn xuất riêng biệt trong P. Sử dụng ký hiệu ⇒ cho các bước
trong một dẫn xuất như trong ví dụ 6.1 và 6.3. Trong 1 vài trường hợp, nó hữu ích để
chỉ định rõ ràng dẫn xuất chi tiết tới văn phạm G, và trong trường hợp này, ghi là ⇒
G
.
α ⇒
G
β
nghĩa là xâu chuỗi β có thể chứa trong xâu chuỗi α bằng cách thay thế một vài biến
xuất hiện trên phần bên trái của một dẫn xuất trong G bởi phần bên phải tương ứng,
hoặc là:
α = α
1
Aα
2
β = α
1
ϒα
2
Và một trong các dẫn xuất trong G là A → ϒ. (Bây giờ có thể hiểu rõ hơn về
phần phi ngữ cảnh. Nếu tại một vài điểm trong một dẫn xuất, chúng ta đã duy trì một

,

α
1
, …, α
k
, với α
0
= α và α
k
= β, đến nỗi α
i
⇒
G
α
i+1
cho mỗi i với
0 ≤ i ≤ k -1.
Ví dụ 6.4: Ngôn ngữ của các biểu thức đại số.
Một ngôn ngữ quan trọng trong khoa học máy tính là ngôn ngữ của các biểu
thức đại số hợp lệ. Đơn giản, chúng ta hạn chế một vài biểu thức đơn mà có thể định
dạng cho 4 toán tử hai ngôi +, -, *, /, dấu ngoặc đơn trái và phải, và định danh đơn a.
Một vài tính năng bỏ quên, vì vậy các toán tử một ngôi, bất cứ các toán tử hai ngôi
khác ngoài 4 toán tử trên, số nguyên mẫu như là 3.0 hoặc …, các biểu thức bao gồm
chú thích mang tính chức năng, và nhiều định danh chung hơn. Hầu hết các chức
năng có thể được xử lý đủ đơn giản; ví dụ như, ngôn ngữ của các định danh bất kỳ có
thể được “thêm vào” các chức năng này bằng cách sử dụng biến A mặc dù ký hiệu
kết thúc a và mô tả dẫn xuất cho phép bất cứ định danh được dẫn xuất từ A (Xem ví
dụ 3.5 và 3.6.)
Một định nghĩa qui nạp của ngôn ngữ được dựa trên sự theo dõi mà các biểu

3. Đánh giá a + B, và gọi nó có giá trị C.
4. Đánh giá C – a.
Biểu thức “là” khác với biểu thức con với giá trị C và biểu thức con a. Dẫn
xuất thứ 2, trái ngược hoàn toàn, làm sáng tỏ biểu thức như kết quả phép chia. Mặc
dù không cò gì trong văn phạm ảnh hưởng đến dẫn xuất này, nó không phản ánh cách
nhìn nhận về cấu trúc đúng của biểu thức.
Phần kết thúc có thể tồn tại trong văn phạm phi ngữ cảnh dành cho ngôn ngữ
có lẽ không là thích hợp nhất. Nó không kết hợp chặt chẽ theo bất cứ cách qui ước
chuẩn, phải thực hiện với quyền ưu tiên của các toán tử và theo thứ tự tính toán từ
trái qua phải, được áp dụng tính toán biểu thức.(Quyền ưu tiên của các toán tử được
áp dụng trong biểu thức a + b * c, phép nhân được thực hiện trước phép cộng; và biểu
thức a – b + c có nghĩa (a - b) + c), không phải a- (b + c). Tuy nhiên, việc chọn giữa
hai dẫn xuất của một xâu chuỗi, nó thường mong đợi chọn lựa, nếu có thể, một CFG
cho một xâu chuỗi có thể chỉ có một dẫn xuất (ngoại trừ sự khác nhau không đáng kể
giữa thứ tự hai biến trong một vài chuỗi trung gian được chọn để thay thế). Chúng ta
sẽ gặp lại câu hỏi này trong phần 6.4, khi thảo luận về sự nhập nhằng trong văn phạm
phi ngữ cảnh.
Ví dụ 6.5: Cú pháp của ngôn ngữ lập trình
Ngôn ngữ trong các ví dụ trước và ngôn ngữ giống như ví dụ 3.5 và 3.6 là các
thành phần đơn giản có liên quan với nhau của ngôn ngữ lập trình như C và Pascal.
Để mở rộng hơn, văn phạm phi ngữ cảnh có thể được dùng đê mô tả cú pháp tổng thể
của ngôn ngữ.
Trong C, việc thử định dạng các qui tắc văn phạm để chỉ rõ cú pháp của câu
lệnh hợp lệ. (Như ngoại lệ, một chỉ định hoàn thành cũng bao gồm.). Hai kiểu của câu
lệnh trong C là câu lện if và câu lệnh for; nếu biễu diễn câu lệnh bất kỳ với các biến
(câu lệnh), kết quả câu lện giống như:
(câu lệnh) → … | (câu lệnh if) | (câu lệnh for ) |
Cú pháp của 2 kiểu câu lệnh này có thể được mô tả bởi các qui tắc:
(câu lệnh if) → if ({biểu thức}) {câu lệnh}
(câu lệnh for) → for({biểu thức}; (biểu thức)) {câu lệnh}

{chủ ngữ} → {danh từ thích hợp}
{danh từ thích hợp} → John | Jane
{động từ} → nhớ
{bổ ngữ} → {danh từ thích hợp} | {đại từ phản thân}
{đại từ phản thân} → himself | herself
Nhiều hơn một câu lệnh tuân theo văn phạm này không hoàn toàn làm việc, ví
dụ: “John nhớ chính cô ấy” và “Jane nhớ chính cậu ấy”. Điều này có thể được lọa
KHMTK12 - Nhóm 7 9
Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8
trừ trong cách thức dễ hiểu (bao gồm sự phức tạp của văn phạm ) bằng cách đưa ra
dẫn xuất giống như:
{câu tường thuật} → {danh từ giống đực}{động từ}{đại từ phản thân giống
đực}
Rõ ràng hơn nhiều vấn đề tinh tế là “Jane nhớ Jane”. Bình thường, chúng ta
không nói như vậy, trừ khi có 2 người khác nhau nhưng trùng tên, nhưng không có
cách rành mạch để ngăn cấm điều đó và cũng không ngăn cấm “Jane nhớ John”. (Ít
nhất, không có cách rõ ràng thật sự cần thiết sử dụng một dẫn xuất khác nhau cho
mỗi câu). Tùy chọn không đáng kể này có sẵn, kể từ khi ngôn ngữ có ngôi. Để phân
biệt “Jane nhớ John,” là một câu tiếng Anh tốt một cách hoàn hảo, từ “Jane nhớ
Jane” yêu cầu sử dụng ngữ cảnh và một cách chính xác điều này văn phạm phi ngữ
cảnh không cho phép.
6.2 Các ví dụ mở rộng.
Nói chung, để trình bày một ngôn ngũ CFG tổng quát, chúng ta phải trình bày
hai điều: thứ nhất mỗi xâu chuỗi trong ngôn ngữ có thể được dẫn xuất từ văn phạm,
và thứ hai, không xâu chuỗi nào khác có thể. Trong một vài ví dụ trong phần này, ít
nhất một trong hai câu này ít rõ ràng hơn.
Ví dụ 6.7: Một CFG cho {x | n
0
(x) = n
1

Sẽ hỗ trợ khi giới thiệu :
d(x) = n
0
(x) – n
1
(x)
Vì vậy, cho bất cứ xâu chuỗi x với d(x) = 0, x ∈ L(G). Chứng minh tính toán học trên
|x|.
Trong bước cơ bản của chứng minh, chúng ta phải trình bày rằng nếu |x| = 0 và
d(x) = 0 (tất nhiên, giả thuyết thứ 2 là thừa), sau đó x ∈ L(G). Điều nầy đúng bởi vì
một trong các dẫn xuất trong G là S → A.
Theo giả thuyết ban đầu, k ≥ 0 và cho bất cứ y với |y| ≤ k và d(y) = 0, y ∈
L(G). Nếu |x| = k + 1 và d(x) = 0, thì x ∈ L(G).
Nếu x bắt đầu 0 và kết thúc 1, thì x = 0y1 cho vài xâu chuỗi y thỏa mãn d(y) =
0. Theo giả thuyết ban đầu, y ∈ L(G). Vậy, khi S ⇒
*
G
y, dẫn xuất x từ S bắt đầu với
dẫn xuất S → 1S0 và tiếp tục dẫn xuất y từ S thứ hai. Khi x bắt đầu 1 kết thúc 0 thì
được xử lý cùng cách, ngoại trừ S → 1S0 thường bắt đầu dẫn xuất.
Trường hợp còn lại x bắt đầu và kết thúc cùng ký hiệu . Khi d(x) = 0 có chiều
dài ít nhất 2; giả định x = 0y0 cho vài xâu chuỗi y. Chúng ta nên trình bày x là một
dẫn xuất trong G. Một dẫn xuất phải bắt đầu với sản phẩm S → SS; để trình bày đó
là một dẫn xuất thì phải x = wz, trong đó w và z là các xâu chuỗi ngắn có thể được
dẫn xuất từ S (có thể cho phép dẫn xuất với S → SS, sau đó tiếp tục dẫn xuất w từ S
ban đầu và z từ S tiếp theo.). Cách khác để nhấn mạnh điều kiện này thì cho rằng x là
tiền tố của w sao cho 0 < |w| < |x| và d(w) = 0.
Cho d(w) có tiền tố w của x. Tiền tố ngắn nhất không rỗng là 0, và d(0) = 1;
tiền tố dài nhất ngắn hơn x là 0y, và d(0y) = -1 (bởi ký hiệu cuối cùng của x là 0, và
d(x) =0). Hơn nữa, giá trị d- của tiền tố thay đổi bằng 1, một ký hiệu mở rộng được

(x) + 1} = {x ∈ {0,1}* | d(x) = 1}
L
1
= {x ∈ {0,1}* | n
0
(x) = n
1
(x) + 1} = {x ∈ {0,1}* | d(x) = -1}
trong đó: d là hàm trong ví dụ 6.7 được định nghĩa d(x) = n
0
(x) – n
1
(x). Thật dễ dàng
để tính toán kết quả cần bắt đầu với S:
S → 0B | 1A | A
KHMTK12 - Nhóm 7 11
Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8
Cũng dễ dàng để tìm thấy kết quả cho mỗi biến A và B. Nếu một xâu chuỗi trong L
0
bắt đầu với 0, hoặc nếu một xâu chuỗi trong L
1
bắt đầu với 1, thì đó là một phần tử
của L. Do vậy, kết quả thích hợp là:
A → 0S B → 1S
Nếu một xâu chuỗi trong L
0
bắt đầu với 1, hoặc nếu một xâu chuỗi trong L
1
bắt đầu
với 0

, S
1
, P
1
) và G
2
= (V
2
, ∑
2
, S
2
, P
2
)
phát sinh L
1
và L
2
, một cách riêng biệt, và cách xây dựng một CFG mới cho ba trương
hợp cụ thể.
Văn phạm G
u
= (V
u
, ∑
u
, S
u
, P

. Sau đó:
P
u
= P
1
∪

P
2
∪ {S
u
→ S
1
| S
2
}
Nếu x có trong L
1
hoặc trong L
2,
thì S
u
⇒
*
x trong văn phạm G
u
, bởi có thể bắt đầu dẫn
xuất với S
u
→ S

L = L
1
∪

L
2
⊆ L(G
u
)
Mặt khác, nếu x là dẫn xuất từ S
u
trong G
n,
bước đầu tiên trong bất cứ dẫn xuất phải là
S
u
⇒ S
1
hoặc S
u
⇒ S
2
Trong trường hợp đầu, tất cả các kết quả xảy ra thường phải là kết quả trong G
1
, bởi
không có biến trong V
2
được xét, và x ∈ L
1
; trong trường hợp 2, x ∈ L

V
c
= V
1
∪

V
2
∪ {S
c
}
Lần này, ta có
P
c
= P
1
∪

P
2
∪ {S
c
→ S
1
S
2
}
Nếu x ∈ L
1
L

2
= x
Bước thứ 2 là dẫn xuất của x
1
trong G
1
và bước thứ 3 là dẫn xuất của x
2
trong
G
2
. Ngược lại, nếu x có thể được dẫn xuất từ S
c
, thì ở bước 1, trong dẫn xuất phải là
S
c
⇒ S
1
S
2,
x phải được dẫn xuất từ S
1
S
2
. Do đó, x = x
1
x
2
, trong đó ứng với mỗi i, x
i

1
∪

{S}
trong đó S ∉ V
1
. Ngôn ngữ L
1
*
chứa các xâu chuỗi có dạng x = x
1
x
2
…x
k
, trong đó mỗi
x
i
∈ L
1
. Khi mỗi x
i
có thể được dẫn xuất từ S
1
, thì dẫn xuất x từ S đủ khả năng dẫn
xuất một xâu chuỗi của k S
1
’
s. Có thể thực hiện như đưa ra kết quả
S → S

, bao gồm cả
x ∈ L(G
1
)
k
⊆ L(G
1
)
*
Chú ý: Thật sự cần thiết cho 2 phần đầu của chứng minh đảm bảo V
1
∩ V
2
= ∅. Cho
CFG có các kết quả:
S
1
→ XA X → c A → a
và
KHMTK12 - Nhóm 7 13
Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8
S
1
→ XB X → d B → b
riêng biệt. Nếu chúng ta cung cấp cấu trúc cho phần đầu của chứng minh không đặt
nhãn lại cho biến, kết quả văn phạm cho phép dẫn xuất
S ⇒ S
1
⇒


A → 011 | 1
với B như ký hiệu bắt đầu để phát sinh {011, 1}*. Tương tự
C → DC | A
D → 01
Dẫn xuất {01}
*
từ ký hiệu bắt đầu C. Cuối cùng, chúng ta phát sinh ghép nối 2 ngôn
ngữ bằng cách thêm dẫn xuất S → BC. Văn phạm cuối có ký hiệu bắt đầu S, biến phụ
trợ A, B, C và D, và các dẫn xuất:
S → BC
B → AB | A
A → 011 | 1
C → DC | A
D → 01
KHMTK12 - Nhóm 7 14
Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8
Bắt đầu với bất cứ biểu thức qui tắc, chúng ta có thể bao hàm tương đương CFG sử
dụng kỹ thuật minh họa trong ví dụ này. Trong phần kế tiếp, bất cứ ngôn ngữ qui tắc
L cũng có thể được mô tả bởi một CFG, mà tất cả các dẫn xuất có dạng rất đơn giản,
và như một CFG có thể được bao hàm dễ dàng từ 1 FA chấp nhận L.
Ví dụ 6.10: Một CFG cho {x | n
0
(x) ≠ n
1
(x)}
Cho ngôn ngữ L = {x ∈ {0,1}
*
| n
0
(x) ≠ n

0
phát sinh L
0
. Rõ ràng 0 ∈ L
0
, và cho bất cứ x
∈ L
0
sẽ luôn luôn giới thiệu một phần tử x0 và 0x trong L
0
. Điều này gợi ý dẫn xuất
S → 0 | S0 | 0S
Cũng cần thêm 1’s vào các xâu chuỗi. Và không thể ngoại trừ thêm 1 vào một phần
tử của L
0
, luôn luôn đưa ra một phần tử L
0
; tuy nhiên, nếu có 2 xâu chuỗi trong L
0
,
ghép nối chúng thành chuỗi có ít nhất 2 chuỗi nhiều 0’s hơn 1’s và sau đó thêm 1 đơn
sẽ vẫn là một phần tử của L
0
. Chúng ta có thể thêm ở bên trái, bên phải hoặc ở giữa
hai chuỗi. Kết quả tương ứng
S → 1SS | SS1 | S1S
Không khó để nhìn thấy bất cứ xâu chuỗi nào được dẫn xuất từ kết quả trên
S → 0| S0 | 0S | 1SS | SS1 | S1S
là một phần tử của L
0

x với dẫn xuất ban đầu:
S → S1S
Biễu diễn x có định dạng trên, x chứa n xâu chuỗi 1, với n ≥ 1. Cho mỗi i với 1 ≤ i ≤
n, cho w
1
là tiền tố của x nhưng không bao hàm chuỗi 1 thứ i, và z
i
là hậu tố của x
cho phép chuỗi 1. Trường hợp khác, với mỗi i,
x = w
i
1z
i
trong đó 1 là xâu thứ I trong x. Nếu d(w
n
) > 0, thì w = w
n
và z = z
n
. Xâu chuỗi z
n
là 0
j
với j > 0 bởi x kết thúc với 0, và cho kết quả cần. Ngoài ra, d(w
n
) ≤ 0. Trong trường
hợp này, chọn i đầu tiên với d(w
n
) ≤ 0, khi đó i = m. Khi x bắt đầu với 0, d(w
1

0
và B như ký hiệu bắt
đầu cho văn phạm tương ứng phát sinh L
1
. Văn phạm G có các dẫn xuất:
S → A | B
A → 0 | 0A | 1AA | AA1 | A1A
B → 1 | 1B | 0BB | BB0 | B0B
Ví dụ 6.11: Ứng dụng khác của Định lý 6.1
Cho L = {0
i
1
j
0
k
| j > i + k}. Giả định xem L như ghép nối của các ngôn ngữ phi
ngữ cảnh, mặc dầu hiển nhiên như vậy – viết L như 1 ghép nối L
1
L
2
L
3
, trong đó 3
ngôn ngữ này chứa các xâu chuỗi của 0, các xâu chuỗi của 1 riêng biệt – được cho
là không có khả năng. L chứa cả hai xâu 0
1
1
3
0
1

, và xâu chuỗi này
không là phần tử của L.
Nhận xét:
0
i
1
i+k
0
k
= 0
i
1
i
1
k
0
k
Chỉ khác nhau giữa xâu chuỗi này với xâu chuỗi x trong L là: x có ít nhất một xâu
1 mở rộng ở giữa:
x = 0
i
1
i
1
m
1
k
0
k
(với mọi m > 0)

L
1
ngôn ngữ cơ bản trong ví dụ 6.2, L
3
cùng với các ký hiệu 0 và 1 được
nghịch đảo, và L
2
có thể được phát sinh bởi các dẫn xuất
B → 1B | 1
(Dẫn xuất thứ 2 là B → 1, không phải B → A, chỉ với các xâu chuỗi không rỗng.)
CFG cuối cùng G = (V, ∑, S, P) kết hợp chặt chẽ các phần này biễu diễn như
sau:
V = {S, A, B, C} ∑ = {0,1}
P = { S → ABC
A → 0A1 | A
B → 1B | 1
C → 1C0 | A }
Cho ví dụ, dẫn xuất của 01
4
0
2
= (01)(1)(1
2
0
2
) là:
S ⇒ ABC ⇒ 0A1BC ⇒ 0A1BC ⇒ 011C
⇒ 0111C0 ⇒ 01111C00 ⇒ 01111A00 = 0111100
KHMTK12 - Nhóm 7 17
Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8

read 3 đọc c vào R3
load 1 ACC  <R1> ; ACC=a
jgtz B nếu <ACC> >= 0 nhảy đến B ; a>=0
jmp NO ngược lại thì nhảy đến NO
B: load 2 ACC  <R2> ; ACC=b
jgtz C nếu <ACC> >= 0 nhảy đến C ; b>=0
jmp NO ngược lại thì nhảy đến NO
C: load 3 ACC  <R3> ; ACC=c
KHMTK12 - Nhóm 7 18
Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8
jgtz T nếu <ACC> >= 0 nhảy đến T ; c>=0
jmp NO
T: load 1 ACC  <R1> ; ACC=a
mul 1 ACC  <ACC> * <R1> ; ACC=a*a
store 1 R1  <ACC> ; R1=a*a
load 2 ACC  <R2> ; ACC=b
mul 2 ACC  <ACC> * <R2> ; ACC=b*b
store 2 R2  <ACC> ; R2=a*a
load 3 ACC  <R3> ; ACC=c
mul 3 ACC  <ACC> * <R3> ; ACC=c*c
sub 1 ACC  <ACC> - <R1> ;ACC=c*c-a*a
sub 2 ACC  <ACC> -<R2> ;ACC=c*c-a*a-b*b
jzero OK nếu <ACC>=0 thì nhảy đến OK
NO: write A:0 ACC  ; là tam giác thường
jump KT nhảy tới KT
OK: write A:1 ACC  1 ; là tam giác vuông
KT: halt dừng chương trình
3. Chương trình RAM thô sơ
;===========================================================
; CHUONG TRINH RAM THÔ SƠ

14: J <7> (10,10) nếu R7=0 thì nháy đến 10, ngược lại nhảy đến 10
15: S <1,7> sau khi hoán đổi thì R1=a, R7=0
16: D <8> giảm R8 đi 1 ;R8=a - số lầnđã lặp
17: J <8> (18,10) nếu R8=0 thì nhảy đến 18, ngược lại thì nhảy đến 10
18: Z <5> đã tính a*a, tiếp tục tính b*b, R5 chứa kết quả, R7, R8 làm biến đếm
19: Z <7> R7 :=0
20: Z <8> R8 :=0
21: J <2> (26,22)nếu R2=0 thì nhảy đến 26, ngược lại nhảy đến 22
22: D <2> giảm R2 đi 1
23: I <5> tăng R5 lên 1
24: I <8> tăng R8 lên 1
25: J <8> (21,21) nếu R8 =0 thì nhảy đến nhãn 21 còn ko thì nhảy đến 21
26: S <2,5> sau khi hoán đổi R2=b,R5=0, R7=R8=b
27: J <2> (32,28) nếu R2 =0 thì nhảy đến 32, ngược lại nhảy đến 28
28: D <2> giảm R2 đi 1
29: I <5> tăng R5 lên 1
30: I <7> tăng R7 lên 1
31: J <7> (27,27) nếu R7=0 thì nhảy đến 27, ngược lại nhảy đến 27
32: S <2,7> sau khi đổi thì R2=b, R7=0
33: D <8> R8 =b – số lần đã lặp
34: J <8> (35,27) nếu R8=0 thì nhảy đến 35, ngược lại là 27
35: Z <6> đã tính b*b, giờ tính c*c, R6 chứa kết quả, R7, R8 làm biến đếm
36: Z <7> R7:=0
37: Z <8> R8:=0
38: J <3> (43,39)nếu R3=0 thì nhảy đến 43, ngược lại nhảy đến 39
39: D <3> giảm R3 đi 1
40: I <6> tăng R6 lên 1
41: I <8> tăng R8 lên 1
42: J <8> (38,38)nếu R8=0 thì nhảy đến nhãn 38, ngược lại nhảy đến nhãn 38
43: S <3,6> sau khi hoán đổi R3=c,R6=0, R7=R8=c

3 5
4 2
5 B
B 3
C
C 4 T
T 2
4 ACC*R1
4 R1=ACC
3
9 ACC*R2
9 R2=ACC
5
25 ACC*R3
21 ACC-R1
12 ACC-R2
NO
NO 0 ACC=0
KT
KT dừng CT
5. Kết quả test chương trình RAM thô sơ
Dòng R1 R2 R3 R4 R5 R6 R7 R8
Nhảy
tới
input 3 4 5
KHMTK12 - Nhóm 7 21
Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8
Dòng R1 R2 R3 R4 R5 R6 R7 R8
Nhảy
tới

10 11
11 0
12 3
13 3
14 10
10 15
15 3 0
16 2
17 10
10 11
11 2
12 4
13 1
14 10
10 11
11 1
12 5
KHMTK12 - Nhóm 7 22
Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8
Dòng R1 R2 R3 R4 R5 R6 R7 R8
Nhảy
tới
13 2
14 10
10 11
11 0
12 6
13 3
14 10
10 15

22 2 23
23 2 24
24 2 25
25 21
21 22
22 1 23
23 3 24
24 3 25
25 21
KHMTK12 - Nhóm 7 23
Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8
Dòng R1 R2 R3 R4 R5 R6 R7 R8
Nhảy
tới
21 22
22 0 23
23 4 24
24 4 25
25 21
21 4 0 26
27 28
28 3 29
29 1 30
30 1 31
31 27
27 28
28 2 29
29 2 30
30 2 31
31 27

29 8 30
KHMTK12 - Nhóm 7 24
Báo cáo tiểu luận môn Lý thuyết tính toán Lý thuyết: câu 2 + Bài tập: câu 8
Dòng R1 R2 R3 R4 R5 R6 R7 R8
Nhảy
tới
30 4 31
27 32
32 4 0 33
33 2 34
34 27
27 28
28 3 29
29 9 30
30 1 31
31 27
27 28
28 2 29
29 10 30
30 2 31
31 27
27 28
28 1 29
29 11 30
30 3 31
31 27
27 28
28 0 29
29 12 30
30 4 31