<< Chapter < Page Chapter >> Page >

2)d(q1, 1, R) = {(q1,YR)}

3)d(q1, 0, B) = {(q1, BB), (q2, e)}

4)d(q1, 0, Y) = {(q1, BY)}

5)d(q1, 1, B) = {(q1, YB)}

6)d(q1, 1, Y) = {(q1, YY),(q2, e)}

7)d(q2, 0, B) = {(q2, e)}

8)d(q2, 1, Y) = {(q2, e)}

9)d(q1, e, R) = {(q2, e)}

10)d(q2, e, R) = {(q2, e)}

Hình 6.4 - Mô tả PDA không đơn định chấp nhận wwR bằng Stack rỗng

Quy tắc (1) đến (3) cho phép M lưu trữ input trên Stack, quy tắc (3) và (6) cho phép M lựa chọn một trong hai phép chuyển. M có thể quyết định (đoán) đã đi đến giữa chuỗi nó chuyển sang phép chuyển thứ 2: M chuyển sang q2 và thử sự thích hợp của phần chuỗi còn lại với các ký hiệu đang ở trên Stack. Nếu M đoán đúng và nếu chuỗi nhập có dạng wwR thì M sẽ làm rỗng Stack của nó và chấp nhận chuỗi nhập.

Cũng như NFA một PDA không đơn định (NPDA) M chấp nhận một input nếu có một chuỗi các lựa chọn mà M làm rỗng Stack của nó. Nghĩa là M luôn luôn "đoán đúng", đoán sai không phải là nguyên nhân để loại bỏ input. Một input bị loại bỏ nếu và chỉ nếu không có sự lựa chọn nào để làm rỗng Stack (hay là không thể "đoán đúng" vì không tồn tại cách đúng).

Thí dụ 6.4 :Các phép chuyển hình thái của PDA chấp nhận chuỗi 001100 thuộc ngôn ngữ {wwR w  (0+1)*} bằng Stack rỗng như sau :

Khởi đầu

¯

(q1, 001100, R) ® (q2, 001100, e) : Không chấp nhận

¯

(q1, 01100, BR) ® (q2, 1100, R) ® (q2, 1100, e) : Không chấp nhận

¯

(q1, 1100, BBR)

¯

(q1, 100, YBBR) ® (q2, 00, BBR)

¯ ¯

(q1, 00, YYBBR) (q2, 0, BR)  (q2, e, R)  (q2, e, e) : Chấp nhận

¯

(q1, 0, BYYBBR) ® (q2, e, YYBBR) : Không chấp nhận

¯

(q1, e, BBYYBBR) : Không chấp nhận

Hình 6.5 - Hình thái của PDA với input 001100

PDA đơn định (DPDA)

Một PDA M (Q, , , , q0, Z0, F) được gọi là đơn định nếu:

1) q  Q và Z  : nếu (q, , Z)   thì (q, a, Z) = , a  

2) Không có q Q, Z   và a  (  {}) mà (q, a, Z) chứa nhiều hơn một phần tử.

Điều kiện 1 không cho phép khả năng chọn lựa giữa phép chuyển không xác định ký hiệu nhập ( - dịch chuyển) và phép chuyển trên một ký hiệu input. Điều kiện 2 không cho phép chọn lựa một vài phép chuyển nào đó (q, a, Z) hay (q, , Z). Không như ôtômát hữu hạn FA, một PDA thì thông thường được xét là không đơn định trừ khi ta có ghi chú cụ thể.

Đối với ôtômát hữu hạn, dạng đơn định và không đơn định là tương đương nhau về phương diện chấp nhận ngôn ngữ. Tuy nhiên, điều này không đúng với ôtômát đẩy xuống, PDA không đơn định và PDA đơn định là không tương đương nhau. Thực tế ngôn ngữ wwR được chấp nhận bởi một PDA không đơn định nhưng không được chấp nhận bởi bất kỳ một PDA đơn định nào.

Pda và văn phạm phi ngữ cảnh

Tương đương của việc chấp nhận chuỗi bởi trạng thái kết thúc và bởi stack rỗng

ĐỊNH LÝ 6.1: Nếu L là L(M2) với PDA M2 thì L là N(M1) với PDA M1 nào đó.

Chứng minh

Ta sẽ xây dựng M1 tương tự như M2 nhưng M1 sẽ xóa rỗng Stack của nó khi M2 đi vào trạng thái kết thúc. Ta dùng một trạng thái qe của M1 để xóa Stack của nó và dùng ký hiệu đánh dấu đáy Stack M1 bằng ký hiệu X0, vì vậy M1 không thể làm rỗng Stack của nó khi M2 chưa đi vào trạng thái kết thúc.

Đặt M2 (Q, , , , q0, Z0, F) là PDA sao cho L = L(M2).

Questions & Answers

what are the products of Nano chemistry?
Maira Reply
There are lots of products of nano chemistry... Like nano coatings.....carbon fiber.. And lots of others..
learn
Even nanotechnology is pretty much all about chemistry... Its the chemistry on quantum or atomic level
learn
Preparation and Applications of Nanomaterial for Drug Delivery
Hafiz Reply
Application of nanotechnology in medicine
what is variations in raman spectra for nanomaterials
Jyoti Reply
I only see partial conversation and what's the question here!
Crow Reply
what about nanotechnology for water purification
RAW Reply
please someone correct me if I'm wrong but I think one can use nanoparticles, specially silver nanoparticles for water treatment.
Damian
yes that's correct
Professor
I think
Professor
what is the stm
Brian Reply
is there industrial application of fullrenes. What is the method to prepare fullrene on large scale.?
Rafiq
industrial application...? mmm I think on the medical side as drug carrier, but you should go deeper on your research, I may be wrong
Damian
How we are making nano material?
LITNING Reply
what is a peer
LITNING Reply
What is meant by 'nano scale'?
LITNING Reply
What is STMs full form?
LITNING
scanning tunneling microscope
Sahil
how nano science is used for hydrophobicity
Santosh
Do u think that Graphene and Fullrene fiber can be used to make Air Plane body structure the lightest and strongest. Rafiq
Rafiq
what is differents between GO and RGO?
Mahi
what is simplest way to understand the applications of nano robots used to detect the cancer affected cell of human body.? How this robot is carried to required site of body cell.? what will be the carrier material and how can be detected that correct delivery of drug is done Rafiq
Rafiq
if virus is killing to make ARTIFICIAL DNA OF GRAPHENE FOR KILLED THE VIRUS .THIS IS OUR ASSUMPTION
Anam
analytical skills graphene is prepared to kill any type viruses .
Anam
Any one who tell me about Preparation and application of Nanomaterial for drug Delivery
Hafiz
what is Nano technology ?
Bob Reply
write examples of Nano molecule?
Bob
The nanotechnology is as new science, to scale nanometric
brayan
nanotechnology is the study, desing, synthesis, manipulation and application of materials and functional systems through control of matter at nanoscale
Damian
Is there any normative that regulates the use of silver nanoparticles?
Damian Reply
what king of growth are you checking .?
Renato
What fields keep nano created devices from performing or assimulating ? Magnetic fields ? Are do they assimilate ?
Stoney Reply
why we need to study biomolecules, molecular biology in nanotechnology?
Adin Reply
?
Kyle
yes I'm doing my masters in nanotechnology, we are being studying all these domains as well..
Adin
why?
Adin
what school?
Kyle
biomolecules are e building blocks of every organics and inorganic materials.
Joe
anyone know any internet site where one can find nanotechnology papers?
Damian Reply
research.net
kanaga
sciencedirect big data base
Ernesto
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get the best Algebra and trigonometry course in your pocket!





Source:  OpenStax, Giáo trình tin học lý thuyết. OpenStax CNX. Jul 30, 2009 Download for free at http://cnx.org/content/col10826/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Giáo trình tin học lý thuyết' conversation and receive update notifications?

Ask