
Tiểu luận Lý thuyết tính toán

ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA

TIỂU LUẬN
MÔN LÝ THUYẾT TÍNH TOÁN
§Ò tµi:
TRÌNH BÀY LÝ THUYẾT VỀ AUTOMAT ĐẨY XUỐNG
VÀ MINH HỌA BÀI TOÁN TRONG TIN HỌC
BẰNG CHƯƠNG TRÌNH RAM
CBHD: PGS. TS. PHAN HUY KHÁNH
HỌC VIÊN: MAI LAM
HỒ THỊ NGỌC
LÊ THỊ HƯƠNG GIANG
LỚP: KHMT- KHÓA 12
Đà Nẵng 03/2010
Nhóm 9- Lớp KHMT Khóa 12 Trang 1

Tiểu luận Lý thuyết tính toán

LỜI MỞ ĐẦU
Lý thuyết tính toán là lĩnh vực nghiên cứu các lý thuyết về máy tính, đó là nghiên cứu về
tính toán hiệu quả, các mô hình của các quá trình tính toán, và giới hạn của chúng. Lĩnh vực này
đã nổi lên trong vài thập kỷ qua như là một căn bản khoa học kỷ luật cũng như chuyên sâu của
khoa học máy tính.
Là một ngành khoa học non trẻ, với nhiều câu hỏi trung tâm vẫn chưa được trả lời, và nó
cũng là một khoa học sẵn sàng để có tác động đáng kể về các vấn đề hiện tại trong sự phát triển
của các hệ thống và phần mềm, của mạng lưới quốc gia và cơ sở hạ tầng thông tin liên lạc, tin
học sinh học và khoa học vật lý. Cũng như tham gia vào các lĩnh vực như thiết kế các thuật toán

CHƯƠNG 2. PHẦN BÀI TẬP 27
2.1. Ý tưởng: 27
2.2. Đề xuất thuật toán: 27
2.3. Minh họa thuật toán bằng chương trình RAM: 28
TÀI LIỆU THAM KHẢO 30
Nhóm 9- Lớp KHMT Khóa 12 Trang 3

Tiểu luận Lý thuyết tính toán

CHƯƠNG 1. PHẦN LÝ THUYẾT
1.1. Giới thiệu theo cách trình bày ví dụ
Trong chương này chúng ta xem xét cẩn thận về phương thức mở rộng mô hình tính toán
trạng thái giới hạn để chúng ta có thể nhận ra ngôn ngữ phi ngữ cảnh. Trong ví dụ đầu tiên, ta
xem xét một trong những ngôn ngữ phi ngữ cảnh bất quy tắc đơn giản nhất. Mặc dù các máy
trừu tượng mà chúng ta mô tả rõ ràng không liên quan gì đến CFG (CFG: văn phạm phi ngữ
cảnh) – tạo ra ngôn ngữ máy nhưng sau này chúng ta sẽ xét đến các trường hợp: các máy cùng
loại nói chung có thể dùng chung bất kỳ ngôn ngữ phi ngữ cảnh nào và việc có thể dễ dàng xây
dựng được một máy từ văn phạm.
Ví dụ 1.1 về một máy chấp nhận chuỗi Palindromes đơn giản. Với G là một văn phạm
phi ngữ cảnh, ta có kết quả sau:
G tạo ra ngôn ngữ máy là:
Các chuỗi trong L là chuỗi có chiều dài lẻ trên {a,b} (ví dụ 6.3), trừ trường hợp kí tự giữa
là c. (Chúng ta hãy xét đến các chuỗi Palindrome thông thường. Kí hiệu “đánh dấu” ở giữa giúp
ta dễ dàng nhận ra các chuỗi kí tự)
Cũng không khó gì để viết một thuật toán kiểm tra các xâu trong L bằng cách đọc các kí
tự từ trái sang phải. Ta lưu lại các kí tự của nửa đầu xâu chuỗi mà ta đã đọc, để một khi chúng ta
bắt gặp kí tự c thì ta có thể bắt đầu thực hiện việc so khớp các kí tự đang vào với các kí tự đã
được đọc. Để thực hiện được điều này, ta phải lấy lại các kí hiệu đã được lưu trữ bằng cách sử
dụng quy tắc “ vào sau, ra trước” (viết tắt là LIFO): Kí tự thường được đem đi so khớp với các
kí tự đang vào kế tiếp là một kí tự đã được đọc hoặc đã được lưu trữ. Cấu trúc dữ liệu dùng quy

tại một nửa đầu xâu chuỗi hoàn toàn trùng khớp với mỗi kí tự đầu vào của xâu chuỗi còn lại và
lúc này máy sẽ chuyển sang trạng thái chấp thuận q2
Bây giờ ta xét đến phương thức miêu tả một cách chính xác sự hoạt động của một máy
trừu tượng mà chúng ta đã phát thảo. Mỗi động thái của máy sẽ được xác định bởi 3 yếu tố:
1. Trạng thái hiện tại
2. Dữ liệu nhập kế tiếp
3. Kí tự ở đầu ngăn xếp
Nhóm 9- Lớp KHMT Khóa 12 Trang 5

Tiểu luận Lý thuyết tính toán

Và bao gồm 2 phần:
1. Sự thay đổi trạng thái ( hoặc vẫn ở cùng trạng thái)
2. Sự thay thể kí tự ở đỉnh ngăn xếp bằng một chuỗi số 0 hoặc các kí tự khác.
Việc mô tả sự dịch chuyển theo cách này cho phép chúng ta có thể xét 2 sự chuyển dịch cơ bản
của ngăn xếp như là các trường hợp đặc biệt:
- Đẩy kí tự tại vị trí đầu tiên (pop) ra khỏi ngăn xếp để thay thế bằng một kí tự kế tiếp Λ, và đẩy
kí tự Y (push) vào ngăn xếp tức là thay kí tự X tại vị trí đỉnh của ngăn xếp bằng kí tự YX (với
giả định là kí tự tận cùng bên trái của chuỗi nằm tương ứng với vị trí đỉnh của ngăn xếp).
Chúng ta sẽ tuân theo quy luật ngăn xếp một cách nghiêm ngặt với yêu cầu là ứng với một sự
dịch chuyển trong ngăn xếp thì đó phải là chuyển động duy nhất trong ngăn xếp: hoặc là đẩy kí
tự vào (push) hoặc là đẩy kí tự ra (pop). Tuy nhiên việc thay thế một kí tự X trong ngăn xếp
bằng 1 kí tự alpha có thể được thực hiện bằng một chuỗi các chuyển động cơ bản (hành động
đẩy kí tự ra, theo sau là một chuỗi các số 0 hoặc nhiều hành động đẩy kí tự vào) và càng nhiều
sự chuyển động chung chung thì càng làm cho số lượng chuyển động khác biệt trở nên ít hơn.
Trong trường hợp của thiết bị ôtômát hữu hạn thì chức năng chuyển dịch có dạng:
Tại đây nếu chúng ta cho phép xảy ra trường hợp: các kí tự chữ cái chứa trong ngăn xếp (một
tập hợp các kí tự có thể xuất hiện trong ngăn xếp) khác với các kí tự chữ cái nhập vào thì ta có:
Với trạng thái q, dữ liệu nhập là a và kí tự trong ngăn xếp là X, ta có:
Nghĩa là trong trạng thái q , với kí tự X nằm ở vị trí đỉnh trong ngăn xếp, ta đọc kí tự a, chuyển

giản: Q sẽ là một tập {q0, q1, q2} với q0 là trạng thái ban đầu, q2 là trạng thái duy nhất được
chấp nhận. Bảng chữ cái đầu vào là {a, b, c} và ngăn xếp bảng chữ cái là (a, b, z0). Chức năng
chuyển dịch của δ được trình bày ở bảng 1.1. Hãy nhớ rằng khi chúng ta đưa một chuỗi vào
ngăn xếp thì vị trí trên cùng của ngăn xếp sẽ tương ứng với vị trí cuối cùng bên phải của chuỗi.
Quy ước này là nếu chúng ta cùng một lúc có thể đưa nhiều ký tự vào thì chúng ta phải thực
hiện theo trật tự từ phải qua trái hoặc theo thứ tự ngược lại. Vấn đề là khi chúng ta đang cố gắng
Nhóm 9- Lớp KHMT Khóa 12 Trang 7

Tiểu luận Lý thuyết tính toán

xử lý các ký tự trong ngăn xếp thì thứ tự mà chúng ta gặp cũng giống như thứ tự đã được sắp
xếp trong chuỗi.
Khi dịch chuyển từ 1 đến 6: đẩy những ký tự đầu đầu vào a, b vào trong ngăn xếp và sự
dịch chuyển từ 7 đến 9: làm thay đổi trạng thái mà không ảnh hưởng đến ngăn xếp, sự dịch
chuyển từ 10 đến 11: so khớp ký tự nhập với ký tự ngăn xếp và cả hai đều bị xóa bỏ, và sự
chuyển dịch cuối cùng sẽ được chấp nhận với điều kiện sẽ không còn ký tự nào ngoại trừ ký tự
Zo ở trong ngăn xếp.
Bảng 1.1 minh họa cho Ví dụ 1.1
Số lần dịch
chuyển
Trạng
thái
Vào
Biểu tượng
ngăn xếp
Dịch
chuyển
Nhóm 9- Lớp KHMT Khóa 12 Trang 8
Tất cả các kết hợp khác không


để gán nhãn trên mũi tên thì biểu đồ ở dạng này không hoàn toàn nắm hết được các hành vi của
một PDA cũng giống như cách thức mà một biểu đồ chuyển tiếp của FA thể hiện. Với một FA
thì bạn có thể bắt đầu tại bất kỳ vị trí nào trên sơ đồ này với các kí tự đầu vào và dõi theo các
hành động của đầu đọc theo hướng của của các mũi tên. Tuy nhiên trong hình 1.1 bạn không thể
dõi theo các mũi tên mà không dò theo nội dung của ngăn xếp (có thể là toàn bộ nội dung). Số
lượng các trạng thái kết hợp có thể có và nội dung của ngăn xếp là vô hạn, vì vậy ta không thể
suy ra được một sơ đồ các trạng thái hữu hạn trong cùng một trường hợp cho một FA. Trong
hầu hết các trường hợp, trong chương này, chúng ta có thể mô tả một automat đẩy xuống bằng
các bảng chuyển tiếp tương tự như bảng 1.1, mặc dù thi thoảng nó cũng rất hữu ích để trình bày
một sơ đồ chuyển tiếp.
1.2. Định nghĩa của một Automat đẩy xuống
Dưới đây là một định nghĩa chính xác về các loại máy trừu tượng trong mục 1.1. Nên nhớ rằng
những gì đang được định nghĩa nói là chung không xác định.
Định nghĩa 1.2. Định nghĩa về một PDA.
Một PDA là một tập M có 7 phần tử M = (Q, Σ, 0, Z, A, δ)
Với Q là một tập hợp các trạng thái hữu hạn – Σ là một tập hữu hạn gồm các dữ liệu đầu vào,
bảng ngăn xếp các ký tự chữ cái tương ứng.
qo trạng thái ban đầu, là một thành phần của tập Q
Zo là ký tự ngăn xếp ban đầu, là một phần tử của ngăn xếp.
A là một tập hợp các trạng thái chấp nhận, là một tập con của Q.
 một tập hợp các tập con hữu hạn của
Các δ chức năng được gọi là chức năng chuyển tiếp của M.
Nhóm 9- Lớp KHMT Khóa 12 Trang 10

Tiểu luận Lý thuyết tính toán

Bảng chữ cái ngăn xếp và ký tự ban đầu ngăn xếp Zo là những yếu tố cần thiết để tạo ra 7 – bộ
dữ liệu thay vì 5 bộ dữ liệu. Nếu không, các thành phần của bộ dữ liệu cũng giống như trường
hợp của FA, ngoại trừ việc chức năng chuyển đổi δ trở nên phức tạp hơn.
Chúng ta có thể theo dõi hoạt động của một Automat hữu hạn bằng cách dò theo trạng thái hiện

rỗng hoặc không rỗng. Ta có thể nói rằng một ngôn ngữ L ⊆ Σ* được thừa nhận bởi M nếu như
L là một tập các chuỗi được chấp nhận bởi M ; trong trường hợp này chúng ta viết L=L(M).
Lưu ý rằng việc có hay không một chuỗi được chấp nhận chỉ phụ thuộc vào trạng thái hiện hành
trong lúc chuỗi đang được xử lý và không còn thuộc nội dung của ngăn xếp.
Chúng ta có thể sử dụng cụm từ ‘cấu hình đang chấp nhận để chỉ bất kỳ cấu hình nào đang trong
trạng thái đang chấp nhận. Dạng chấp nhận này đôi khi được gọi là sự chấp nhận bởi trạng thái
cuối.
Mục này sẽ được trình bày một cách ngắn gọn tại mục 7.5 mô tả một trường hợp khác: sự chấp
thuận bởi ngăn xếp trống. Trong phương pháp này, một chuỗi được xem là được chấp nhận nếu
nó cho phép PDA đạt đến cấu hình mà tại đó ngăn xếp hoàn toàn rỗng, bất kể là trạng thái lúc đó
có phải là trạng thái chấp thuận hay không. Cũng không khó để nhận ra rằng 2 loại chấp nhận là
tương đương nhau (tại mục 7.5, bài tập 7.41 và 7.42), trong trường hợp nếu một ngôn ngữ được
một số PDA chấp thuận, đang sử dụng một trong những mode của trạng thái chấp nhận thì cũng
sẽ được thừa nhận bởi một PDA đang ở một mode khác.
Phải nhấn mạnh thêm rằng khi ta nói một PDA thừa nhận một chuỗi X thì nghĩa là đang có một
chuỗi các chuyển động mà nó là tác nhân làm cho máy tiến đến cấu hình của sự chấp nhận và
đó là kết quả của việc đọc các kí tự X. Khi PDA là không xác định thì có khả năng có thể có các
chuỗi chuyển động khác nhưng không làm cho máy tiến đến cấu hình của sự chấp nhận. Mỗi lần
có sự lựa chọn của sự dịch chuyển thì ta có thể quan sát PDA khi nó đang thực hiện công việc
Nhóm 9- Lớp KHMT Khóa 12 Trang 12

Tiểu luận Lý thuyết tính toán

dự đoán xem lựa chọn nào sẽ được thực hiện. Sự chấp nhận xảy ra, có nghĩa là PDA đã đoán
đúng tại mỗi bước dịch chuyển và máy sẽ đạt đến cấu hình của sự chấp nhận. Ở ví dụ kế tiếp,
chúng sẽ sẽ xem xét thêm để làm rõ việc dự đoán đúng có ý nghĩa như thế nào tại mỗi bước
chuyển động.
Ví dụ 1.2 về sự chấp nhận ngôn ngữ của chuỗi Panlidromes của một PDA.
Thí dụ này có liên quan đến ngôn ngữ pal của chuỗi Panlidromes trên tập {a,b} (cả hai đều có
cùng độ dài chẵn và lẻ) không có kí hiệu đánh dấu ở vị trí giữa, nó tạo ra một tín hiệu làm cho

chuỗi lựa chọn phù hợp mà máy có thể dự đoán đúng tại một thời điểm thích hợp thì tất nhiên
chuỗi z đầu vào phải là một chuỗi palindrome, nếu thiết bị PDA đoán đúng tại một thời điểm
không thích hợp hoặc đoán sai thì có khả năng quá trình chấp thuận các chuỗi palidrome khác sẽ
kết thúc, ngoại trừ chuỗi z; hoặc đơn giản là kết thúc hẳn trạng thái không chấp thuận. Điều này
không có nghĩa là thiết bị PDA làm sai, chỉ là PDA không chọn đúng trình tự dịch chuyển mà có
thể dẫn đến sự thừa nhận chuỗi z.
Bảng chuyển đổi của thiết bị PDA được trình bày ở bảng 1.2. Trong thí dụ 1.1, tập hợp Q và A
là những tập hợp giống nhau và lưu ý là có nhiều điểm tương đồng giữa 2 bảng chuyển đổi. Sự
chuyển động tại 6 dòng đầu tiên trong bảng 1.1 cho thấy là có nhiều sự chuyển động có thể có
tại các dòng tương ứng của bảng 1.2, và 3 dòng cuối của 2 bảng – đại diện cho tiến trình xử lý
nửa chuỗi sau – là giống hệt nhau.
Thực tế là 6 dòng đầu tiên của bảng 1.2 hiển thị hai dịch chuyển có thể có, điều này cho thấy
được sự bất định. Máy dự đoán sai với hai lựa chọn trong mỗi dòng trên (được trình bày trong
bảng 1.1) và máy dự đoán được kí tự đầu vào là một ký tự nằm ở vị trí giữa của xâu có chiều dài
chẵn. Trong cả hai trường hợp, ký tự nhập đều được đọc; với lựa chọn đầu tiên, máy đẩy kí tự
vào ngăn xếp, với lựa chọn thứ hai, máy xóa bỏ kí tự.
Tuy nhiên cũng có trường hợp bất định với những trình tự ít rõ ràng. Giả dụ, PDA đang trong
trạng thái q0, kí tự tại vị trí đỉnh ngăn xếp là a và kí tự nhập kế tiếp cũng là a (dòng 3). Ngoài 2
động thái được thể hiện trong dòng 3 thì còn có lựa chọn thứ 3 được trình bày ở dòng 8: không
phải là để đọc tất cả các ký tự nhập nữa mà để thực hiện sự chuyển đổi sang trạng thái q1. Điều
này đại diện cho tất cả các lần đoán đúng khác, nó là kết quả của quá trình đọc các kí tự gần đây
nhất (hiện đang ở tại vị trí đỉnh của ngăn xếp) và chúng ta đang ở tại vị trí giữa của chuỗi có
chiều dài chẵn. Sự lựa chọn này được thực hiện mà không cần quan tâm đến ký tự đầu vào kế
tiếp. (Một phương pháp tiếp cận khác là đọc kí tự a và so khớp kí tự này với ký tự a trong ngăn
xếp và máy chuyển sang trạng thái q1; tất cả đều có cùng cách thức dịch chuyển; tuy nhiên
Nhóm 9- Lớp KHMT Khóa 12 Trang 14

Tiểu luận Lý thuyết tính toán

những sự dịch chuyển ở trong bảng cho thấy có điểm khác biệt giữa trạng thái q0 trong tất cả

chấp nhận
Thứ tự này là một trong những dịch chuyển của lần dự đoán đúng với sự lựa chọn phù hợp và
đúng thời điểm. Những đường bị lệch khỏi phương thẳng đứng kết thúc quá sớm trước khi PDA
hoàn thành việc đọc dữ liệu nhập; máy sẽ rơi vào tình trạng bị treo hoặc sẽ sớm đi vào trạng thái
chấp thuận q2 (để chuỗi được chấp nhận là một chuỗi palindrome có độ dài là 0 hoặc 1). Những
đường chạy dọc theo phương thẳng đứng quá dài có thể làm cho PDA bị treo hoặc không còn ký
tự để nhập vào trước khi ngăn xếp rỗng.
Nhóm 9- Lớp KHMT Khóa 12 Trang 16

Tiểu luận Lý thuyết tính toán

1.3. MỘT ÔTÔMÁT ĐẨY XUỐNG TƯƠNG ỨNG VỚI MỘT VĂN PHẠM PHI NGỮ
CẢNH XÁC ĐỊNH.
Tính đến thời điểm này, các PDA chúng ta đã xây dựng được dựa trên các tính chất đối
xứng đơn giản của các chuỗi trong các ngôn ngữ được nhận biết hơn là trên bất kỳ đặc tính nào
của CFG (CFG) hình thành nên ngôn ngữ.
Điều đó có nghĩa là, không phải ngôn ngữ phi ngữ cảnh nào cũng có thể được nhận biết
bởi một PDA. Tuy nhiên, điều này chúng ta sẽ chứng minh trong phần này. Bắt đầu với một văn
phạm phi ngữ cảnh G, chúng ta muốn xây dựng một PDA có thể kiểm tra một chuỗi tùy ý và xác
định xem liệu nó có thể được dẫn xuất từ G. Chiến lược cơ bản là mô phỏng dẫn xuất của một
chuỗi trong văn phạm xác định.
Điều này sẽ đòi hỏi phải đoán các bước của dẫn xuất, và PDA của chúng ta sẽ là không
đơn định (Như chúng ta thấy trong Phần 7.6, có mốt số dạng văn phạm xác định mà chúng ta có
thể điều chỉnh PDA, giữ lại các tính năng thiết yếu và loại bỏ tính không đơn định. Cách tiếp
cận trên đặc biệt rất hữu hiệu trong các trường hợp này, bởi vì với một chuỗi x trong ngôn ngữ,
theo dõi sự dịch chuyển của máy ở đầu vào x không những cho phép chúng ta xác nhận sự có
mặt của x trong ngôn ngữ, mà con bộc lộ một dẫn xuất của x trong văn phạm. Bởi vì ngôn ngữ
thân thuộc như người bạn, tuy nhiên để tìm ra PDA đơn định nói chung là quá sức mong đợi).
Theo tiến trình mô phỏng, máy sẽ kiểm tra chuỗi đầu vào để đảm bảo rằng nó vẫn còn
phù hợp với tiến trình dẫn xuất. Nếu chuỗi đầu vào thực sự có dẫn xuất từ văn phạm, và nếu dự

Đặt G = (V,Σ,S,P) là 1 văn phạm phi ngữ cảnh. Chúng ta định M = (Q,Σ,Γ,q
0
,Z
0
,A,δ) như sau:
Q={q
0
,q
1
,q
2
} A={q
2
} Γ =V ∪ Σ ∪ {Z
0
} (Trong đó Z
0
∉ V ∪ Σ)
Dịch chuyển ban đầu của M là đặt S vào stack và dịch chuyển sang q1: δ(q
0
,∧,Z
0
) = {(q
1
,SZ
0
)}.
Dịch chuyển duy nhất tới trạng thái chấp nhận q
2
là từ q

Chứng minh
Trước tiên, chứng minh L(G) ⊆ L(M). If x là 1 chuỗi bất kỳ trong L(G), thì bước cuối cùng
trong dẫn xuất trái nhất của x là:
yAz ⇒ yy’ = x
trong đó y, z và y’ là các chuỗi ký hiệu, và bước thông thường sẽ là:
yAα ⇒ yy’β
ở đây, một lần nữa y và y’ là những chuỗi kết thúc, trong đó yy’ là tiếp đầu ngữ của x, và chuỗi
β bắt đầu với 1 biến. Chúng ta có thể lấy trường hợp thứ 2 như một đại diện cho trường hợp 1,
nếu chúng ta nói rằng β hoặc là A, hoặc là bắt đầu bằng 1 biến.
Cái chúng ta muốn chứng minh trong trường hợp này là một chuỗi dịch chuyển tuần tự của PDA
đã ảnh hưởng tới việc đọc chuỗi kết thúc yy’, so khớp với ký tự kết thúc trong stack, để chuỗi β
trong stack (thực chất là βZ
0
) và đặt PDA ở trạng thái q
1
. Nó sẽ tiếp theo, từ trạng thái đặc biệt
trong đó β = A, tức là với 1 chuỗi đầu vào x, PDA có thể đạt đến cấu hình (q
1
, A, Z
0
); do đó, bởi
vì sự dịch chuyển tới q2 như đã mô tả ở phần định nghĩa, PDA chấp nhận x.
Một phát biểu chính xác nói điều này và thích hợp cho việc chứng minh bằng quy nạp sau đây:
Với bất kỳ n ≥ 1, nếu x ∈ L(G) Và bước thứ n trong dẫn xuất trái nhất của x là yAα ⇒ yy’β,
trong đó x = yy’z, yy’ là chuỗi kết thúc, và β hoặc là A, hoặc là bắt đầu bằng 1 biến, trong đó
Với bước chứng minh cơ bản, đặt n = 1. Bước đầu tiên trong dẫn xuất của x là sử dụng phép
sinh dạng S  y’β, vì thế chuỗi y trong (7.1) là rỗng.
Sử dụng dịch chuyển khởi đầu trong định nghĩa của M và dịch chuyển của dạng (1), chúng ta
có:
Nhóm 9- Lớp KHMT Khóa 12 Trang 19

sử dụng dịch chuyển dạng (2), và hoàn tất chứng minh rằng L(G) ⊆ L(M)
Kế tiếp, chứng minh rằng L (M) ⊆ L (G). Nói đại khái, điều này có nghĩa chúng ta cần chứng
minh ngược lại phát biểu trước đó; hay nói cách khác, cấu hình (q
1
, z, βZ
0
) chỉ có thể xảy ra khi
và chỉ khi có một số dẫn xuất trái nhất trong văn phạm sinh ra các chuỗi yβ , trong đó x = yz. Để
chính xác, chúng ta chứng minh như sau:
Với bất kỳ n ≥ 1, nếu có 1 chuỗi tuần tự n dịch chuyển dẫn từ cấu hình (q
0
,x,Z
0
) tới (q
1
, z, βZ
0
)
thì y ∈ Σ*, x=yz và S ⇒ *
G
yβ.
Bước cơ bản khá dễ, bởi vì chỉ có dịch chuyển duy nhất sinh ra cấu hình bên phải là dịch chuyển
khởi đầu của M; trong trường hợp này z = x và β = S, vì thế y có thể được lựa chọn để trở thành
A
Nhóm 9- Lớp KHMT Khóa 12 Trang 20

Tiểu luận Lý thuyết tính toán

Giả sử rằng k ≥ 1, và phát biểu của chúng ta là đúng với mọi n ≥ k. Cũng giả sử rằng một số
dịch chuyển tuần tự (k + 1) sinh ra cấu hình (q

x và x ∈ L(G).
Ví dụ 7.5: Một PDA đẩy xuống cho chuối có nhiều a’s hơn là b’s
Xem xét ngôn ngữ:
Trong đó chúng ta xây dựng một DPDA trong Ví dụ 7.4. Từ Ví dụ 6.10 chúng ta biết rằng 1 văn
phạm phi ngữ cảnh của L là một phép sinh:
S → a | aS | bSS | SSb | SbS
Tiếp theo việc xây dụng trong chứng minh ở Định lý 7.2, chúng ta đạt được một PDA M =
(Q,Σ,Γ,q
0
,Z
0
,A,δ) trong đó Q={q
0
,q
1
,q
2
}, Σ={a,b}, Γ={S,a,b,Z
0
}, A={q
2
}, hàm chuyển δ được
Nhóm 9- Lớp KHMT Khóa 12 Trang 21

Tiểu luận Lý thuyết tính toán

định nghĩa bởi bảng sau:
Chúng ta xem như chuỗi x = abbaaa L và so sánh các dịch chuyển tạo bởi M trong việc chấp∈
nhận x với một dẫn xuất trái nhất của x trong văn phạm. Mỗi bước chuyển trong đó một biến bị
thay thế trong stack bởi 1 chuỗi tương ứng với một bước trong dẫn xuất trái nhất của x, và bước

cùng, có được lấy ra khỏi stack và Z
0
là điều duy nhất còn lại. Toàn bộ quá trình mô phỏng một
dẫn xuất là để đảo ngược thứ tự của chuỗi đầu vào. Tại mỗi bước, chuỗi hiện hành của dẫn xuất
được hình thành bởi các nội dung của stack (ngược lại), theo sau là chuỗi đầu vào chưa đọc, bởi
vì sau mỗi lần giảm, biến trên đầu trang của stack là phần phải nhất trong chuỗi hiện hành, dẫn
xuất được mô phỏng trong đảo ngược là một dẫn xuất phải nhất.
Ví dụ 7.6: Một PDA đẩy lên cho các biểu thức đại số đơn giản
Hãy minh họa cho cách tiếp cận này bằng cách sử dụng văn phạm G, một phiên bản đơn giản
Phần 6.4, với các phép sinh:
(1) S → S+T
(2) S → T
(3) T → T*a
(4) T → a
Lý do để đánh số các phép sinh sẽ được nhìn thấy ngay. Giả sử là chuỗi đầu vào a+a*a$, trong
đó có dẫn xuất phải nhất.
Nhóm 9- Lớp KHMT Khóa 12 Trang 23

Tiểu luận Lý thuyết tính toán

S ⇒ S+T
⇒ S+T*a
⇒ S+a*a
⇒ T+a*a
⇒ a+a*a
Các bước tương đương hoặc nhóm các bước thực hiện bởi các PDA đẩy lên như chuỗi a+a*a
được xử lý thể hiển trong Bảng 7.6. Hãy nhớ rằng tại mỗi điểm, sự đảo ngược của chuỗi trên
stack (bỏ qua Z
0
), theo sau là chuỗi đầu vào chưa đọc, tạo thành chuỗi hiện hành của dẫn xuất,

chuyển khả dĩ chỉ có thể là để loại bỏ T khỏi stack, thay thế nó bằng T, và trở về trạng thái q.
Tất nhiên, tất cả các dịch chuyển tuần tự này là quá trình chuyển đổi A, chỉ ảnh hưởng đến
stack.
Ngoài các trạng thái đặc biệt được sử dụng để rút gọn, PDA nằm ở trạng thái q trong hầu hết quá
trình xử lý. Khi S lên đầu stack, nó lấy S ra và di chuyển đến q
1
, từ đó nó chấp nhận trạng thái
q2 nếu tại thời điểm đó stack trống rỗng ngoại trừ Z
0
. Bảng chữ cái đầu vào là {a, +, *} và bảng
chữ cái trong stack là {a, +, *, S, T, Z
0
}
Chú ý rằng trong sự dịch chuyển, một số kết hợp của ký hiệu đầu vào và stack có thể được bỏ
qua. Ví dụ như, khi 1 chuỗi trong ngôn ngữ được xử lý, ký hiệu + sẽ không bảo giờ xảy ra một
Nhóm 9- Lớp KHMT Khóa 12 Trang 25
Trạng thái Đầu vào Stack ký tự Chuyển