Bài tập môn học Lý thuyết tính toán KHMT Khóa 12
BỘ GIÁO GIỤC ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
TIỂU LUẬN
Đề tài : MÔN HỌC LTTT
GVHD : PGS.TS PHAN HUY KHÁNH
HVTH
: ĐÀO NGỌC TUẤN ANH
: NGUYỄN VĂN KIỂM
: PHAN MINH TIẾN
Nghành : Khoa học máy tính
Đà Nẵng – ngày 09 tháng 05 năm 2010
Trang
Bài tập môn học Lý thuyết tính toán KHMT Khóa 12
PHẦN I: LÝ THUYẾT
10.4. Ngôn ngữ đó không phải là đệ quy liệt kê.
11.1. Văn phạm không hạn chế.
PHẦN II: BÀI TẬP
I. Khái niệm số phức
I.1. Định nghĩa số phức
I.2. Các dạng biểu thức của số phức
II. Các phép tính cơ bản trên số phức.
III. Phân tích bài toán.
1.1. Mục đích.
1.2. Giải thuật.
1.3. Thực hiên trên máy RAM thô sơ.
1.4. Chương trình RAM thô sơ.
Trang
Bài tập môn học Lý thuyết tính toán KHMT Khóa 12
PHẦN I: LÝ THUYẾT
10.4. NGÔN NGỮ KHÔNG PHẢI LÀ ĐỆ QUY LIỆT KÊ

j
” bằng e(T
i
) không chấp nhận bởi T
j
. Bạn có thể tạm
ngừng đọc vào lúc này, bạn có khả năng mô tả xong ngôn ngữ cho thấy là
không thể chấp nhận bởi bất kỳ TM.
Định nghĩa chính thức của chúng tôi sẽ hơi khác, một phần vì nó
không giải trình rõ việc thiết lập của TMs, nhưng chủ yếu vì nó sẽ thuận
tiện trong một vài ứng dụng sau này để xem xét ngôn ngữ bậc cao hơn.
Định nghĩa 10.4. Với NSA (Không tự-Chấp Nhận) là tập hợp con
của {0, 1}* :NSA = NSA1 ∪ NSA2
Nơi
NSA1 = {ω ϵ {0, 1}* | ω = e(T) cho một vài TM T, và T không chấp
nhận ω}
NSA2 = {ω ϵ {0, 1}* | ω không phải e(T) cho bất cứ TM T}
Với SA (tự-chấp nhận) là phần bổ sung của NSA trong {0, 1}*, sao cho
SA = {ω ϵ {0, 1}* | ω = e(T) cho một vài TM T, và T chấp nhận ω}
Định lý 10.9. Ngôn ngữ NSA không phải là đệ quy có thể liệt kê
Chứng minh. Khi trong đối số chéo trước, chứng minh này do mâu
thuẫn, giả dụ có TM với L(To) = NSA. Trong các từ khác, chấp nhận 1
chuỗi nhập vào ω nếu chỉ nếu ω ϵ NSA. Với ω
0
là chuỗi e(T
0
). Chúng ta có
Trang
Bài tập môn học Lý thuyết tính toán KHMT Khóa 12
thể hỏi TM T

0
chấp nhận ω
0
hoặc không.
Tuy nhiên, chúng ta có thể nói rằng cả hai đều không thể xảy ra. Do đó, giả
định L(To) = NSA phải sai.
Mặt khác bạn có thể tự do để hỏi “vậy thì sao?” (ít nhất bạn tự do
để hỏi điều này nếu bạn có đọc chứng minh và hiểu nó) Ngôn ngữ NSA có
vẻ không thực tế, thực ra mà nói, và chúng ta đã biết có nhiều máy không
đệ quy – có thể đếm ngôn ngữ. Tuy nhiên, định lý 10.9 có một vài hệ quả
quan trọng. Chúng ta có thể dùng nó để hiển thị một số vấn đề, bao gồm
một số không âm giả định, là “không có lời giải”, Bây giờ chúng ta có thể
dùng nó để tạo ra ví dụ khác, lọc mối quan hệ giữa đệ quy liệt kê và đệ
quy.
Định lý 10.10. SA là đệ quy liệt kê nhưng không đệ quy, nói cách
khác, mặc dù SA có thể chấp nhận bởi máy Turing, TM nào chấp nhận nó
sẽ lặp mãi mãi ít nhất 1 chuỗi vào không phải ngôn ngữ.
Chứng minh, dễ dàng từ phần thứ 2 của định lý 10.9. Nếu SA đã đệ
quy thì bổ sung của NSA cũng đệ quy. Định lý 10.9 biểu diễn SA không
thể đệ quy vì nó không phải đệ quy có thể liệt kê. Do đó để hoàn thành
chứng minh, là đủ để xây dựng TM T
sa
chấp nhận ngôn ngữ SA.
Nhớ lại rằng SA = {ω | ω = e(T) và T chấp nhận ω}. Các T
sa
bằng
cách xác định liệu các chuỗi đầu vào ω có dạng e(T) đối với T, nếu không
T
sa
sẽ bị treo. Nếu ω = e (T), thì T

(T) đối với một số T, ngay cả khi máy T treo ngay lập tức hoặc hỏng vì
các lý do khác để thực hiện bất cứ hành động có ý nghĩa.
Tất cả phần hai của các điều kiện dễ dàng kiểm tra. Để kiểm tra cho
phần hai, T1 thực hiện một vòng lặp, trong lần lặp thứ i trong đó T1 tìm
kiếm cho 5-tuples sau lần thứ i có cùng đầu tiên hai phần như lần thứ i. Các
chi tiết về căn bản giống như việc “tìm kiếm” phần TM thể hiện trong fig
9-19, và chúng tôi sẽ không mô tả nó thêm nữa.
Nếu một trong bốn điều kiện cho ω có dạng e(T) không được đáp
ứng, sau đó T1 bị treo. Nếu tất cả bốn điều kiện được thỏa mãn thì phục
hồi T1 đầu vào ω để hình thành ban đầu của nó và thêm vào kết thúc của
nó chuỗi e (ω). Bởi vì ω chính nó là một chuỗi của 0 và 1, tạo ra chuỗi e
(ω) là đơn giản. Nó bắt đầu với 11. Nếu hai ký hiệu 0 và 1 là a
i
và a
j
, tương
ứng, trong bảng chữ cái S, mỗi 0 trong ω được mã hoá bởi 0
i+1
và mỗi 1 bởi
0
j+1
, mỗi chuỗi như vậy đang được theo sau bởi 1. Ví dụ, 00101 trở thành
110
i+1
1
10
i+1
10
j+1
10

trong chuỗi hiện hành của sự phát sinh có thể được thay thế bởi vế bên phải
của việc tạo ra A, độc lập của ngữ cảnh. Vế bên trái tạo ra là một biến đơn,
và việc tạo ra có thể áp dụng bất cứ khi nào biến xuất hiện trong chuỗi. Đó
là ngữ cảnh-tự do mà cho phép chúng ta chứng minh bổ đề bơm cho CFLs,
vì bất kỳ kết quả dài lâu phải có một "tự nhúng" biến, một biến A mà S ⟹
* υAz ⟹ * υωAyz. Chúng có thể làm cho văn phạm tổng quát hơn bằng
cách cho phép vế bên trái của tạo ra được nhiều hơn một biến đơn. Ví dụ,
chúng có thể sử dụng để tạo ra
αAβ→αγβ
Nếu muốn để cho phép một biến A sẽ được thay thế bằng chuỗi γ,
nhưng chỉ khi A là trực tiếp trước trong chuỗi của α và trực tiếp theo sau β.
Văn phạm trong đó tạo ra được kiểu này. Những yêu cầu bổ sung mà γ ≠
A, vừa được nghiên cứu và sẽ được bàn luận sau ở trong chương này. Nếu
không có và hạn chế về γ, việc tạo ra kiểu này là tổng hợp đủ để mô tả các
ngôn ngữ chúng ta đang quan tâm, tuy nhiên, nó thường được thuận tiện
hơn để viết chúng trong mẫu.
αAβ→γ
hoặc, đơn giản hơn
α→β
Điều này có nghĩa rằng chuổi tạo ra bây giờ được xem là thay thế
một cách đơn giản của một chuỗi cho nhau, với ý tưởng thay thế các chuỗi
biến chỉ giữ lại theo ý nghĩa là ở vế bên trái của chuổi sinh ra phải có ít
nhất một biến.
Trang
Bài tập môn học Lý thuyết tính toán KHMT Khóa 12
Định nghĩa 11.1. Không hạn chế, hay cấu trúc giai đoạn văn phạm
là 4 tuples G = (V, Σ, S, P), mà V và Σ là bộ phân chia của biến và phần
vào ra, tương ứng; S là một phần của V gọi là các ký tự bắt đầu; và P là
một chuổi tạo ra theo mẫu.
α→β

chuỗi không hợp lý bởi những vi phạm quy tắc.
BA→AB
CA→AC
Trang
Bài tập môn học Lý thuyết tính toán KHMT Khóa 12
CB→BC
Với kiểu thứ ba, chúng ta không thể thêm chuỗi tạo ra, như A → α,
vì nó có thể được sử dụng quá sớm, có nghĩa là, trước khi chính các dãy
biến đúng. Thay vào đó, chúng ta nói rằng C có thể được thay thế bằng c
nhưng nếu chỉ trước c hay b.
cC→cc
bC→bc
B có thể được thay thế bằng b nếu trước b hoặc α
bB→bb
aB→ab
Và, không dứt điểm, có thể được thay thế bằng α nếu trước bởi α:
α A→ α α
Qua những vấn đề cụ thể tại một thời điểm, chúng ta thấy rằng việc
tạo ra làm cho ba sự kết hợp không hợp lý bα, cα, và cb là không thể. Lúc
này, vấn đề là: đầu tiên α đến từ đâu? nó vẫn không chính xác để có A →
a, ngay cả với những hạn chế của chúng vào của b và c. Điều này sẽ cho
phép dãy abcabc, ví dụ, vì trong chuỗi ABCABC hai nửa bắt đầu với A chỉ
có sự kết hợp của quy tắc. Bằng cách nào đó cuối cùng vế trái A trở thành
một α để bắt đầu mọi thứ. Chúng giải quyết vấn đề bằng cách sử dụng
thêm một biến F để đứng cuối vế trái của chuỗi. Sau đó chúng ta có thể cho
rằng A có thể được thay thế bằng α chỉ khi nó đứng trước bởi α hoặc F:
α A→ α α
FA→ α
Chúng chỉ dẫn biến F vào cuối vế trái. Cho phép tạo ra S → FS ngoài các S
chuỗi tạo ra nó không đúng vì điều này sẽ cho phép thu được.

⟹aabBCC ⟹aabbCC⟹aabbcC⟹ aabbcc
Dễ dàng thấy rằng bất cứ chuỗi trong L có thể được bắt đầu từ văn phạm
này, tuy nhiên, rõ ràng không phải bất cứ chuỗi nào cũng có thể được tạo
ra. Lưu ý đầu tiên nếu S ⟹ * α, khi đó α không thể có một ký hiệu cuối
xuất hiện sau một biến, và do đó α ∈ Σ * V *. Thứ hai, bất kỳ chuổi nào
được sinh ra tiếp theo những chuỗi nguyên vẹn của phần vào ra và sắp xếp
lại các biến hoặc bổ sung thêm nhiều hơn phần vào ra. Giả sử u ∈ L (G) và
u có sự kết hợp phần vào ra không hợp lệ, gọi là ba. Sau đó u = υbaω, và
có kết quả của u từ S ⟹ * υbβ cho β ∈ V *. Điều này là không khả thi,
tuy nhiên, vì vấn đề không phải β là gì, khi ấy không thể tạo ra α như là
phần cuối tiếp.
Kết quả Trong ví dụ này, sự thay đổi vế trái của A và vế phải của C,
cũng như "phổ biến" ký hiệu vào ra bên phải trong phần vào ra, có thể đề
xuất rất hay là thay đổi phần đầu băng từ của TM và dịch chuyển máy làm
cho nó biến đổi như băng từ của nó. Tương tự Đây không phải là trùng hợp
ngẫu nhiên. Bằng chứng rằng những văn phạm có thể tạo ra các ngôn ngữ
đệ quy liệt kê tùy ý sử dụng khả năng của một văn phạm để bắt chước một
TM và để thực hiện cùng một loại "máy điện toán" .Trong mọi trường hợp,
ý tưởng của ký hiệu biến đổi thông qua các chuỗi là một kỹ thuật hữu ích
và có thể lần nữa được sử dụng trong ví dụ tiếp theo của nó.
Ví dụ 11.2.
Trang
Bài tập môn học Lý thuyết tính toán KHMT Khóa 12
L={ss|s ∈ {a,b}*}
Một TM có thể sinh ra chuỗi trong L thuật toán không đơn định bằng
cách tạo ra một nửa đầu tùy ý và sau đó tự ý làm một bản sao trực tiếp sau
đây. Văn phạm của chúng kế tiếp sau này, ngoại trừ mỗi ký hiệu trong nửa
đầu được sao chép ngay lập tức sau khi nó được tạo ra. Giả sử chúng ta sử
dụng một M đánh dấu để chỉ giữa chuỗi và tại một số điểm chúng có các
chuỗi sMs. Để tạo ra một chuỗi dài của cùng loại, chúng có thể chèn một


bB
Cho phép các biến để di chuyển qua các phần vào ra trong nửa đầu. Cuối
cùng,biến chuyển số lần xem M, lúc này nó tương ứng với đặt phần vào ra
ở phía bên kia và không xuất hiện, bằng cách sử dụng chuỗi tạo ra.
AM

Ma
BM

Mb
Để hoàn thành một kết quả chúng cần chuỗi tạo ra
Trang
Bài tập môn học Lý thuyết tính toán KHMT Khóa 12
F

Λ
M

Λ
Các chuỗi abbabb có kết quả sau đây. ở trên, phần nhấn mạnh của mỗi
chuỗi là vế bên trái của việc sử dụng tạo ra tiếp theo.
SFMFbBMFbMbFbBbMbFbbBMbFbbMbbFaAbbMbb
FabAbMbbFabbAMbbFabbMabbabbMabbabbabb
Đây là nguyên nhân rõ ràng rằng bất kỳ chuỗi trong L có thể được
tạo ra bởi văn phạm của chúng. Chúng ta kết luận rằng không có dãy khác
được tạo ra, vậy cho phép. Trước tiên, nó bị xóa chuỗi trong L (G) chiều
dài giống nhau, kể từ khi tạo ra chỉ thay đổi độ dài cuối cùng của chuỗi
tăng nó bằng 2. thứ hai, khi M cuối cùng bị loại trong kết quả, tất cả những
ký hiệu phần vào ra trong chuỗi cuối cùng có mặt, và một nửa phần trước

ngược lại, mọi điểm M(a,b) của mặt phẳng Oxy đều có thể xem như là ảnh
của số phức a + bi.
Nếu z = a: Thì M(a,0) nằm trên trục Ox. Vì vậy, trục Ox còn được
gọi là trục thực.
Nếu z = bi: Thì M(0,b) nằm trên trục Oy. Vì vậy, trục Oy còn được
gọi là trục ảo.
Hai số phức liên hợp được biểu diễn bởi hai điểm đối xứng với nhau
qua trục Ox.
Nối điểm A(a,b) với gốc tọa độ, ta được vectơ Trong nhiều trường hợp,
người ta xem vec tơ như là biểu diễn hình học của số phức z = a + bi.
II. Những phép tính cơ bản trên số phức:
Cho hai số phức z = a + bi và w = c + di. Lần lượt có dạng lượng giác là
.
• Phép cộng :
• Phép trừ :
• Phép nhân :
• Phép chia :

III. PHÂN TÍCH BÀI TOÁN
Trang
Bài tập môn học Lý thuyết tính toán KHMT Khóa 12
1.1. Mục đích : Tính tổng và tích của hai số phức cho trước.
1.2. Giải thuật :
1.2.1. Khai báo: (các modul cần thiết)
public:
so_phuc()
{
thuc=0;
ao=0;
}

}
1.2.2.4. Modul Nhan( ) //thực hiện tính tích 2 số phức
void
so_phuc::nhan(so_phuc&z1,so_phuc&
z2)
{
this->thuc=z1.thuc*z2.thuc-
z1.ao*z2.ao;
this-
>ao=z1.thuc*z2.ao+z1.ao*z2.thuc;
}
1.3. Thực hiện trên RAM thô sơ :
Đặt R1 = a, R2 = b, R3 = c, R4 = d.
//R1, R2, Ri là các thanh ghi
Ghi nội dung ở thanh ghi R1 sang các thanh ghi R5, R6, R7, R8,
và R9. //R1 = 0 , R5=R6=R7=R8=R9= a
Ghi nội dung ở thanh ghi R2 sang các thanh ghi R10, R11, R12,
R13, và R14. //R2 = 0, R10=R11=R12=R13=R14= b
Tính tổng :
Thực hiện phép cộng phần thực (a + c) trên (R5, R3) và ghi nội
dung của R3 sang R15 và R16. //R5 = a+c, R3=0, R15=R16=
c
Chuyển nội dung vừa tính trên R5 về R1
// R5 = 0, R1 = a+c

kết quả phần nguyên phép cộng
Trang
Bài tập môn học Lý thuyết tính toán KHMT Khóa 12
Thực hiện phép cộng phần ảo (b+d)
I

1 J<1> (9,2) Chuyển nội dung
thanh ghi R1 sang
các thanh ghi R5,
R6, R7,R8,R9
R1 = 0
R5 = a
R6 = a
R7 = a
R8 = a
R9 = a
2 D<1>
3 I<5>
4 I<6>
5 I<7>
6 I<8>
7 I<9>
8 J<1> (9,2)
9 J<2> (17,10) Chuyển nội dung
thanh ghi R2 sang
các thanh ghi R10,
R2 = b
R10 = b
R11 = b
10 D<2>
11 I<10>
Trang
Bài tập môn học Lý thuyết tính toán KHMT Khóa 12
R11, R12, R13, R14 R12 = b
R13 = b
R14 = b

i
và chép
nội dung của thanh
ghi R4 sang thanh
ghi R17
R10 =
(b+d)
i
R4 = 0
R17 = d
R18 = d
28 D<4>
29 I<10>
30 I<17>
31 I<18>
32 J<4> (33,28)
33 J<10> (37,34) Chuyển nôi dung
của R10 qua R2
R2 = (b+d)
i
R10 = 0
34 D<10>
35 I<2>
36 J<10> (37,34)
37 J<15> (49,38) Thực hiện phép
nhân a*c
R6 = a*c
R7 = a
R15 = 0
R19 = a

54 I<20>
55 J<12> (56,52)
56 J<20> (60,57) Hồi giá trị R12
R12 = b
R20 = 0
57 D<20>
58 I<12>
59 J<20> (60,57)
60 J<17> (61,50)
61 J<11> (65,62) Thực hiện phép trừ
R6 = R6 – R11
R6 = (a*c
– b*d)
R11 = 0
62 D<11>
63 D<6>
64 J<11> (65,62)
65 J<6> (69,66) Đưa nội dung
R6  R3
R3 = (a*c
– b*d)
R6 = 0
66 D<6>
67 I<3>
68 J<6> (69,66)
69 Z<7> R7 = 0 R7 = 0
70 J<18> (82,71) Thực hiện phép
nhân a*d
R8 = a*d
R9 = a

87 I<13>
88 I<12>
89 J<14> (90,86)
90 J<12> (94,91) Hồi giá trị R14
R14 = b
R12 = 0
91 D<12>
92 I<14>
93 J<12> (94,91)
94 J<16> (95,84)
95 J<13> (99,96) Thực hiện phép R8 = (a*d
Trang
Bài tập môn học Lý thuyết tính toán KHMT Khóa 12
cộng
R8 = R8 + R13
+ b*c)
i
R13 = 0
96 D<13>
97 I<8>
98 J<13> (99,96)
99 J<8>
(103,100)
Đưa nội dung
R8  R4
R4 = (a*d
+ b*c)
i
R8 = 0
100 D<8>