ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA
BÁO CÁO MÔN HỌC
LÝ THUYẾT TÍNH TOÁN
ĐỀ TÀI:
TÌM HIỂU MỘT SỐ VĂN PHẠM
VÀ BÀI TẬP RAM THÔ SƠ
Giáo viên giảng dạy:
PGS TS. PHAN HUY KHÁNH
Học viên thực hiện:
Lê Ngọc Quang
Thái Duy Quý
Ngô Thị Hiền Trang
Đà Nẵng, 5/2010
Báo cáo lý thuyết tính toán Nhóm 12
MỤC LỤC
MỤC LỤC 2
LỜI MỞ ĐẦU 3
PHẤN MỘT: LÝ THUYẾT 5
!"#$%&"'%!!%(
)*+"#,-!./$%01 !
23$!4$ 5
!. "65
7893'9,:;,,<=>'?
789,@A=<2
789,B'C,B;33=<:@'D?
:=E
PHẦN HAI: BÀI TẬP 23
hướng dẫn tận tình và cung cấp tài liệu tham khảo quý báu để chúng tôi hoàn thành đề
tài này.
Mặc dù nhóm đã nhiệt tình tìm hiểu, nghiên cứu nhưng do thời gian có hạn,
trình độ cũng còn hạn chế nên không tránh khỏi những thiếu sót. Kính mong thầy xem
xét, góp ý để nhóm chúng tôi hoàn thiện, hiểu rõ hơn nữa về các bài toán này.
Xin chân thành cám ơn.
Trang 3
Báo cáo lý thuyết tính toán Nhóm 12
YÊU CẦU ĐỀ TÀI
Phần lý thuyết:
Trình bày các khái niệm theo gợi ý sau đây:
- Văn phạm không hạn chế và máy Turing.
- Văn phạm chính quy.
- Văn phạm cảm ngữ cảnh và Automat tuyến tính giới nội.
Phần bài tập:
Bằng cách loại bỏ lệnh hoán đổi S <n, m> trong máy RAM thô sơ để chỉ còn lại
các lệnh I <n>, D <n>, Z <n>, J <n> (i, j) và HALT, viết chương trình RAM thô sơ
tính n^^p là hàm lũy thừa bậc hai (Double Exponent Function: n^^0 = 1 ; n^^p+1 =
nn^^p) với các số nguyên n, p cho trước.
Trang 4
Báo cáo lý thuyết tính toán Nhóm 12
PHẤN MỘT: LÝ THUYẾT
. I MỘT SỐ KHÁI NIỆM
Trước khi đi vào nội dung chính, ta tìm hiểu một số khái niệm liên quan như: ngôn
ngữ, văn phạm, các phân cấp văn phạm của Chomsky,… Đây là các khái niệm ban đầu
giúp làm nền tảng cho các kiến thức liên quan.
I.I.1. Ngôn ngữ(Languages)
Định nghĩa 1.1. Một ngôn ngữ (Languages) L là một tập hợp các chuỗi của các ký
hiệu(symbols) từ một bộ chữ cái Σ nào đó. Tập hợp chứa chuỗi rỗng (ký hiệu {ε}) và
tập hợp rỗng ∅ cũng được coi là ngôn ngữ.
trong tập biến V; các chữ cái Latinh đầu bảng viết thường (a, b, c, ) dùng chỉ các ký
hiệu kết thúc thuộc tập T. Chuỗi các ký hiệu kết thúc thường được biểu diễn bằng các
chữ cái Latinh cuối bảng viết thường (x, y, z, ).
I.I.3. Sự phân cấp Chomsky trên văn phạm
Dựa trên các kiểu văn phạm, Chomsky đã phân loại các văn phạm theo các cấp bậc
như sau:
o Văn phạm loại 0: Một văn phạm không cần thỏa ràng buộc nào trên tập các
luật sinh được gọi là văn phạm loại 0 hay còn được gọi là văn phạm không hạn chế
(Unrestricted Grammar).
Trang 5
Báo cáo lý thuyết tính toán Nhóm 12
o Văn phạm loại 1: Nếu văn phạm G có các luật sinh dạng α → β và thỏa | β | ≥ |
α | thì G là văn phạm loại 1 hoặc còn được gọi là văn phạm cảm ngữ cảnh CSG
(Context-Sensitive Grammar).Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ
cảm ngữ cảnh (CSL).
o Văn phạm loại 2: Nếu văn phạm G có các luật sinh dạng A → α với A là một
biến đơn và α là một chuỗi các ký hiệu ∈ (V ∪ T)
*
thì G là văn phạm loại 2 hoặc còn
được gọi là văn phạm phi ngữ cảnh CFG (Context-Free Grammar). Ngôn ngữ của
lớp văn phạm này được gọi là ngôn ngữ phi ngữ cảnh (CFL).
o Văn phạm loại 3: Nếu văn phạm G có mọi luật sinh dạng tuyến tính phải
(right-linear): A → wB hoặc A → w với A, B là các biến đơn và w là chuỗi ký hiệu kết
thúc (có thể rỗng); hoặc có dạng tuyến tính trái (left-linear): A → Bw hoặc A → w thì
G là văn phạm loại 3 hay còn được gọi là văn phạm chính quy RG (Regular
Grammar). Ngôn ngữ của lớp văn phạm này được gọi là ngôn ngữ chính quy (RL)
I.I.4. Ôtômát hữu hạn
Định nghĩa 1.3. Một cách hình thức ta định nghĩa ôtômát hữu hạn là bộ gồm năm
thành phần (Q, Σ, δ, q
0
o B : ký hiệu thuộc Γ dùng chỉ khoảng trống trên băng (Blank).
o δ : hàm chuyển ánh xạ : Q × Γ → Q × Γ × {L, R, ∅}
o (δ có thể không xác định với một vài đối số).
o q
0
∈ Q là trạng thái bắt đầu.
o F ⊆ Q là tập các trạng thái kết thúc.
Trang 7
Báo cáo lý thuyết tính toán Nhóm 12
. II VĂN PHẠM KHÔNG HẠN CHẾ VÀ CÁC MÁY TURING
Như đã thấy ở chương trước văn phạm không hạn chế là tổng quát nhất trong phân
cấp các của Chomsky, trong phần này chúng ta sẽ đi vào văn phạm loại 0 và cho thấy
rằng ngôn ngữ thừa nhận chúng có thể được chấp nhận mởi máy Turing.
Định lý 2.1. Nếu G = (V,
Σ
, S, P) là văn phạm không hạn chế thì có một máy
Turing T = (Q, Σ, Γ, q
0
,
δ
) với L(T) = L(G).
Chứng minh:
Chúng ta chứng minh định lý bởi việc xây dựng một máy Turing không đơn
định(Nondeterministic Turing Machine – NTM) để chấp nhận L(G). Nó được tổ hợp từ
nhiều thành phần:
T = MovePastInput
→
Simulate
→
Equal
Ví dụ 2.1.
Cho văn phạm không hạn chế với tập các quy tắc:
S
→
aBS | ∆
aB
→
Ba
Ba
→
aB
B
→
b
Chúng sinh ra ngôn ngữ của của các chuỗi trong {a, b}* với số lượng a và b bằng
nhau.
Hình 2.1 cho thấy máy Turing biểu diễn như trong chứng minh ở Định lý 2.1 Lưu ý
rằng trong ví dụ này chỉ những quy tắc mà chúng ở bên trái hoặc bên phải có độ dài
khác nhau là những S quy tắc, và S xuất hiện cuối cùng bên trái nhất của chuỗi. Trong
trường hợp tổng quát hơn, việc chấp nhận một luật sinh như S
→
aBS có thể hoàn
thành bởi việc sử dụng một máy Turing chèn hai lần và một luật sinh khác S
→
∆ yêu
cầu một bộ xóa.
Trang 9
Báo cáo lý thuyết tính toán Nhóm 12
Hình 2.1 Một bắt chước TM cho Ví dụ 2.1
Định lý 2.2. Nếu L
(a
1
a
1
) (a
2
a
2
)… (a
k
a
k
)
Trang 10
\
Q
\
∆/∆, R
∆/S, S
\
B/b, L
\
]
∆/
∆,
R
∆/∆, L
a/a,
R
q
5
S/
∆,
L
S/
a,
R
q
3
q
3
∆/
B,
R
∆/
S,
L
a/a, L
b/b,L
B/B,L
Báo cáo lý thuyết tính toán Nhóm 12
Ký hiệu “(“ và “)” được sử dụng như là các biến. Ký tự đầu tiên của mỗi cặp còn
lại thì giống nhau, ngược lại cái thứ hai có thể thay đổi trong quá trình mô phỏng.
Khi M bắt đầu, có một ô trống trên ô vuông 0 của băng. Thêm vào đó, M có thể sử
dụng vài phần ô trống của băng bên phải của chuỗi đầu vào. Điều này có nghĩa là ta
thực sự cần thiết một chuỗi có dạng:
(∆∆)(a
1
)… (a
k
a
k
) (∆∆)…(∆∆)
Nếu tại một số điểm trong quá trình xử lý, M có cấu hình
(q, b
0
b
1
… b
i-1
b
i
b
i+1
… b
m)
Thì khi đó chuỗi nhận được tương ứng là
(∆b
0
)(a
1
b
1
)… (a
i-1
b
i-1
)q(a
→
(σ b)q
cho các σ ∈ Σ ∪ {∆}. Lưu ý rằng ký hiệu σ ở đây không thay đổi và trạng thái biến đã
được di chuyển sang trái của cặp ký hiệu. Mỗi di chuyển
Trang 11
Báo cáo lý thuyết tính toán Nhóm 12
δ(p, a) = (q,b,S)
ta có tất cả các luật sinh:
p(σ a)
→
(σ b)
với (σ
∈
Σ
∪
{∆}), và cho mỗi di chuyển
δ(p, a) = (q,b,L)
ta có các luật sinh:
(σ
1
σ
2
)p(σ
3
a)
→
q(σ
1
h(σ
1
σ
2
)
→
h(σ
1
σ
2
)h (σ
1
∈
Σ
∪
{∆}, σ
2
∈
Γ
∪
{∆})
(σ
1
σ
2
)h
∈
Σ
, σ
2
∈
Γ
∪
{∆})
h(∆σ)
→
∆ (σ
∈
Γ
∪
{∆})
Các quy tắc trong hai dòng đầu đơn giản phát sinh các sao chép của h thông qua
chuỗi, và những luật sinh hai dòng cuối xóa đi những thứ cần thiết.
Ví dụ 11.4. Trong ví dụ này, chúng chấp nhận ngôn ngữ đối xứng thông qua {a,
b}. Chúng ta không liệt kê tất cả luật sinh trong văn phạm, chúng có khoảng 251 và
nhiều những thứ không cần thiết bởi vì chúng liên quan đến phép nối (σ
1
, σ
1
) mà không
bao giờ dùng tới. Thay vào đó, chúng ta cho thấy một chấp nhận của chuỗi aba trong
văn phạm. Dãy tương ứng của máy Turing bắt chước di chuyển bởi chuỗi nhận được
thấy bên phải. Bởi vì máy Turing di chuyển phần trước của các ô vuông rỗng sang bên
, ∆aba)
⇒
(∆ ∆)(a ∆)q
2
(bb)(aa)(∆ ∆) ├(q
2
, ∆∆ba)
⇒
(∆ ∆)(a ∆)(bb) q
2
(aa)(∆ ∆) ├(q
2
, ∆∆ba)
⇒
(∆ ∆)(a ∆)(bb)(aa)q
2
(∆ ∆) ├(q
2
,∆∆ba∆)
⇒
(∆ ∆)(a ∆)(bb)q
3
(aa)(∆ ∆) ├(q
3
,∆∆ba)
⇒
(∆ ∆)(a ∆)q
4
(bb)(a∆)(∆ ∆) ├(q
4
(∆ ∆)(a ∆)(b ∆)h(a ∆)h(∆ ∆)
⇒
(∆ ∆)(a ∆)h(b ∆)h(a ∆)h(∆ ∆)
⇒
(∆ ∆)h(a ∆)h(b ∆)h(a ∆)h(∆ ∆)
⇒
h(∆∆)h(a ∆)h(b ∆)h(a ∆)h(∆ ∆)
⇒
h(a ∆)h(b ∆)h(a ∆)h(∆ ∆)
⇒
ah(b ∆)h(a ∆)h(∆ ∆)
⇒
abh(a ∆)h(∆ ∆)
⇒
abah(∆ ∆)
⇒
aba
Trang 13
Báo cáo lý thuyết tính toán Nhóm 12
. III VĂN PHẠM CHÍNH QUY
Chúng ta đã thấy được văn phạm tổng quát hơn CFG, ta trở lại các văn phạm kém
tổng quát hơn CFL, đó là dạng ngôn ngữ chính quy. Trong phần này, chúng ta sẽ thấy
rằng chúng có thể được phát sinh bởi văn phạm không hạn chế từ đó.
Ví dụ 3.1 Cho Ôtômát hữu hạn trong hình dưới đây. Ngôn ngữ đón nhận là {0,
1}*{10}, tập hợp tất cả các chuỗi của {0, 1} kết thúc bởi 10.
Hình 11.2 Một Ôômát hữu hạn
Giả sử rằng chúng ta có như một chuỗi, x = 110001010 và nó tự xử lý bởi FA như
sau:
Xử lý chuỗi phụ Trạng thái
A
0
1
1
0
Báo cáo lý thuyết tính toán Nhóm 12
A
⇒
1B
⇒
11B
⇒
110C
⇒
1100A
⇒
11000A
⇒
110001B
⇒
1100010C
⇒
11000101B
⇒
110001010C
Điều trông thấy rõ ràng này giống như bộ thu nhận ngữ pháp. Để đón nhận ngữ
pháp ta đặc tả các biến thành các trạng thái của FA và bắt đầu với các quy tắc:
A
→
1B
→
110001010
Lưu ý rằng luật sinh chúng ta thêm vào có dạng:
P
→
a
Khi mà
P
→
a
F
Là một dịch chuyển từ P vào một trạng thái chấp nhận F.
Bất kỳ FA nào dẫn dắt một ngữ pháp cũng chính xác trong trường hợp này. Trong
ví dụ chúng ta thật dễ dàng để thấy rằng phát sinh ngôn ngữ là chính xác bởi sự chịu
trách nhiệm bởi FA. Tổng quát hơn, chúng ta phải đủ điều kiện cho phát biểu yếu bởi
vì các quy tắc mà chúng ta liệt kê không có A - quy tắc nào cả, tuy nhiên nó vẫn còn
đúng cho chuỗi khác null được chấp nhận bởi FA thì rõ ràng cho những phát sinh bởi
kết quả của văn phạm.
Định nghĩa 3.1 Một văn phạm G = (V,
Σ
, S, P) là chính quy nếu mọi luật sinh là
một trong hai dạng
B
→
aC
Trang 15
Báo cáo lý thuyết tính toán Nhóm 12
B
→
a
được chấp nhận bởi M và n ≥ 1. Khi đó có một dãy các
chuyển tiếp:
→
q
0
→
1
a
q
1
→
2
a
q
2
→
3a
…
→
−1n
a
q
n-1
→
n
a
q
n
n-1
⇒
a
1
a
2
… a
n-1
a
n
Tương tự, nếu x được phát sinh bởi G, dễ thấy rằng x được chấp nhận bởi M.
Ngược lại giả sử rằng G = (V, Σ, S, P) là văn phạm chính quy phát sinh L. Trong
một vài trường hợp ta có thể hoán đổi cấu trúc ở trên: Chúng ta định nghĩa trạng thái
tương ứng cho tất cả các biến và tạo ra chuyển tiếp:
B
→
a
C
cho mọi luật sinh dạng B
→
aC. Lưu ý rằng điều này giống như một chỉ dẫn không xác
định. Chúng ta có thể nắm giữ kiểu dẫn xuất khác bằng cách thêm một trạng thái mở
rộng f, sẽ chỉ chấp nhận trạng thái và ta có các quy tắc B
→
a tương ứng cho chuyển
tiếp B
→
a
f.
Ta có máy M = (Q,
n
∈
L = L(G) thì có một dẫn xuất có dạng:
S
⇒
a
1
q
1
⇒
a
1
a
2
q
2
⇒
…
⇒
a
1
a
2
… a
n-1
q
n-1
a
q
n
Trang 16
Báo cáo lý thuyết tính toán Nhóm 12
từ đó cho thấy x được chấp nhận bởi M.
Ngược lại, nếu x = a
1
…a
n
được chấp nhận bởi M, khi đó | x | ≥ 1 bởi vì f chỉ là
trạng thái chấp nhận của M. Một chuyển tiếp gây ra từ x được chấp nhận như sau:
q
0
→
1
a
q
1
→
2
a
…
→
−1n
a
q
n-1
Ta đã định nghĩa một CSG như là “văn phạm không hạn chế” với sự hạn chế đã đặt ra
và mặc dù nghe như là “cảm ngữ cảnh” có nghĩa là “không phải phi ngữ cảnh” thì nó
rõ ràng rằng với mọi CFG nào mà không có luật sinh A thì đều là cảm ngữ cảnh.
Chúng ta đi vào khả năng giống nhau của các bài toán trước đó, như là máy “không
đơn định” rằng, thực tế là đơn định. Một CSL không cần thiết phải là phi ngữ cảnh.
Thứ hai rất dễ hiểu cụm từ “cảm ngữ cảnh” nếu chúng ta nhìn vào những đặc trưng
khác nhau của các ngôn ngữ. Nó cho thấy rằng ngôn ngữ là cảm ngữ cảnh nếu và chỉ
nếu nó được sinh ra bởi văn phạm với các luật sinh dạng:
α A β
→
α X β
với α, β, X là các chuỗi biến, các ký tự kết thúc hoặc cả hai, X ≠ null, A là biến.
Ví dụ 4.1 : Trong Ví dụ 2.1, chúng ta biểu diễn văn phạm của ngôn ngữ:
L = {a
n
b
n
c
n
| n ≥ 1}
là không phải cảm ngữ cảnh. Bởi một sự thay đổi rõ ràng, tuy nhiên chúng ta có thể
thấy rằng L là một CSL. Thay vì sử dụng một biến phân biệt F đặt phía trước chuỗi, ta
có thể dễ dàng phân biệt giữa ký tự đầu A trong chuỗi và phần còn lại của A. Bạn có
thể kiểm tra rằng CSF với những quy tắc sinh L:
S
→
ABCS
1
| ABC
S
Định nghĩa 4.2. Một Ôtômát tuyến tính giới nội(Linear – bounded automata –
LBA) là một bộ gồm 5 phần M = (Q, Σ, Γ, q
0
, δ) mà nó như là một máy Turing không
đơn định. Có hai băng mở rộng các ký hiệu
〈
và
〉
, giả sử rằng không có các thành
phần của Γ. NTM M bắt đầu với cấu hình (q
0
,
〈
x
〉
) với băng vào của nó quét ký tự
〈
trong ô vuông 0 và ký tự
〉
trong ô đầu tiên bên phải của chuỗi vào x; trong các di
chuyển tiếp, M không có quyền thay thế ký hiệu
〈
hoặc
〉
hoặc di chuyển đầu bên trái
của nó từ ô vuông với
〈
hoặc phải từ ô vuông với
〉
.
dẫn xuất đó trên rãnh 2, giữa hai ký hiệu đánh dấu đầu mút ⊄ và $. Vậy M chấp nhận
chuỗi nhập w.
Tóm lại M sẽ chấp nhận mọi chuỗi sinh ra bởi văn phạm G.
Định lý 11.5. Nếu có một Automat tuyến tính giới nội M = (Q,
Σ
, Γ, q
0
, δ) chấp
nhận ngôn ngữ L ⊆ Σ* thì có một văn phạm cảm ngữ cảnh phát sinh L – {∆}.
Chứng minh:
Trang 19
Báo cáo lý thuyết tính toán Nhóm 12
Ta xây dựng một CSG G thực hiện 3 giai đoạn:
oGiai đoạn 1: Văn phạm cho phép sinh ra một chuỗi w (chuỗi nhập của M), cũng
được chứa trong ⊄, $ và q
0
.
oGiai đoạn 2: Văn phạm lặp lại công việc của M.
oGiai đoạn 3: Khi xuất hiện trạng thái q ∈ F, ta thu về chuỗi w với lưu ý rằng
các luật sinh α → β đều có | α | = | β |.
Quá trình mô phỏng lại các luật sinh đó bởi các luật sinh của CSG sẽ không có gì
vướng mắc. Chỉ ở giai đoạn 3, việc xoá đi các ký hiệu đánh dấu hai đầu mút ⊄ và $, q
không được phép làm rút ngắn chuỗi nhập lại. Để giải quyết vướng mắc này, ta gắn
các ký hiệu ⊄, $, q kề bên với các ký hiệu của chuỗi nhập mà không để đứng rời ra
như trước.
Cụ thể, giai đoạn 1 thực hiện bởi các luật sinh trong G sau:
S
1
→ [a, q
0
Trang 20
Báo cáo lý thuyết tính toán Nhóm 12
Một bộ nhận aa trong văn phạm cho thấy với các gạch chân các phần phía trái của
luật sinh sẽ được sử dụng cho bước tiếp theo và LBA di chuyển tương ứng xuất hiện
bên phải.
S
⇒
T(aa
〉
)
⇒
q
0
(a
〈
a)
L
(aa
〉
) (q
0
,
〈
aa
〉
)
⇒
q
1
2
(aa
〉
)
R
├ (q
2
,
〈
∆a
〉
)
⇒
(a
〈
∆)q
3
(aa
〉
) ├ (q
3
,
〈
∆a
〉
)
⇒
q
4
(a
〈
∆∆
〉
)
⇒
h(a
〈
∆)h(a∆
〉
)
⇒
ah(a∆
〉
)
⇒
aa
Hình 4.1. Một LBA chấp nhận ngôn ngữ đối xứng.
Trang 21
q
5
q
6
∆/∆, R
a/∆, L
a/∆, R
a/a, R
b/b, R
a/∆, R
q
0
nghĩa, định lý.
2. Tìm hiểu về máy Turing chấp nhận ngôn ngữ không hạn chế.
3. Tìm hiểu các khái niệm, định lý, định nghĩa về văn phạm chính quy, phân
tích ví dụ cụ thể.
4. Tìm hiểu về văn phạm cảm ngữ cảnh và Ô tô mát tuyến tính giới nội, có ví
dụ minh họa cụ thể.
Các vấn đề chưa thực hiện được như sau:
1. Phân tích nhiều ví dụ cụ thể, rõ ràng cho người đọc.
2. Trình bày lý thuyết và các ví dụ một cách mạch lạc, rõ ràng hơn.
Trang 22
Báo cáo lý thuyết tính toán Nhóm 12
PHẦN HAI: BÀI TẬP
Đề bài:
Bằng cách loại bỏ lệnh hoán đổi S <n, m> trong máy RAM thô sơ để chỉ còn lại
các lệnh I <n>, D <n>, Z <n>, J <n> (i, j) và HALT, viết chương trình RAM thô sơ
tính n^^p là hàm lũy thừa bậc hai (Double Exponent Function: n^^0 = 1 ; n^^p+1 =
n
n^^p
) với các số nguyên n, p cho trước.
Bài làm:
. I Giới thiệu RAM thô sơ.
Từ một mô hình chương trình RAM, ta có thể rút gọn các lệnh xuống thành
những lệnh cơ bản, nhưng từ những lệnh này, có thể xây dựng các chương trình
như một RAM bình thường. Một RAM chỉ gồm những lệnh cơ bản gọi là RAM thô
sơ.
Ta có thể rút gọn các lệnh trong máy RAM như sau:
- Thu gọn tập lệnh ngắt: Chuyển lệnh ngắt JUMP và JGTZ về thành lệnh ngắt
JZERO.
- Thu gọn tập hợp các lệnh số học: Các lệnh nhân(MULT), chia(DIV) có thể
chuyển về lệnh cộng(ADD), trừ(SUB), các lệnh cộng(ADD) và trừ(SUB) có
f(n,p) = n^^p
Ta có: f(n,0) = 1
f(n,p) = n^n^^(p-1)
n, p cho trước.
Thuật toán cơ bản, đệ quy được viết như sau, ta giả sử hàm Exp(a,b) trả về kết quả
a^b:
Tinh (n,p: integer): long
Begin:
If(p = 0) Tinh = 1
Else Tinh = Exp(n,Tinh)
Endif
End
Từ thuật toán trên, ta khử đệ quy, được thuật toán sau đây, ta giả sử kết quả được
lưu vào biến T:
Begin:
Read n,p
T = 1
while(p >0)
p = p -1
T = Exp(n,T)
Endwhile.
Write T.
End
Thuật toán Exp(n,b) có thể triển khai bằng đoạn mã sau đây:
S = n
While(b>0)
Trang 24
Báo cáo lý thuyết tính toán Nhóm 12
S = S * n
b = b -1
Ngoài ra ta có phép gán: S = n, phép gán này có thể thực hiện bằng vòng while như
trong bảng sau, giả sử R1 = S, R2 = n, muốn gán R1 = R2 ta làm như sau:
Trang 25
Copyright: Tài liệu đại học ©