<< Chapter < Page Chapter >> Page >

Thí dụ 8.2 : Xét CSG G (V, T, P, S) với các luật sinh được cho như trong Thí dụ 8.1 trên và xét chuỗi nhập w = abbc. Ta cần xác định xem liệu chuỗi w  L(G)?

Để tìm đường đi từ đỉnh S tới đỉnh abbc trong đồ thị nói trên ta có thể dùng phương pháp “vết dầu loang” như sau:

Lập các R(i), i = 0, 1, 2, … theo quy tắc sau:

R(0) = { S }

R(i) = R(i -1)  {      với   R(i -1) và      w  }

Do R(0)  R(1)  …  R(i)  R(i +1)  …  tập các đỉnh, vậy tồn tại số k nào đó sao cho:

R(k) = R(k +1) = R(k +2) = …

Do đó quá trình thành lập các R(i) sẽ có thể ngừng sau k bước.

Và w  L(G) khi và chỉ khi có i  k để cho w  R(i).

Trong thí dụ trên, giả sử khi ta xét  w = 4, ta có:

R(0) = { S }

R(1) = {S, aSBC, aBC}

R(2) = {S, aSBC, aBC, abC}

R(3) = {S, aSBC, aBC, abC, abc}

R(4) = R(3)

Vậy chuỗi abbc không thuộc L(G).

Sự tương đương giữa lba và csg

Chúng ta chú ý rằng LBA có thể chấp nhận các chuỗi rỗng , còn CSG không thể sinh ra chuỗi rỗng. Ngoài trường hợp đó ra thì LBA sẽ chấp nhận chính xác tất cả các chuỗi được sinh ra từ CSG.

ĐỊNH LÝ 8.2 : Nếu L là một CSG thì L sẽ được chấp nhận bởi một LBA nào đó.

Chứng minh

Cách chứng minh định lý này cũng tương tự như cách chứng minh của định lý 7.9 ở chương trước về sự tương đương giữa lớp ngôn ngữ sinh từ văn phạm loại 0 với lớp ngôn ngữ mà máy Turing chấp nhận, chỉ khác là ở đây không cần dùng một băng nhập thứ hai để phát sinh các dạng câu theo chuỗi dẫn xuất lần lượt theo các suy dẫn của văn phạm, mà chỉ cần dùng rãnh thứ hai trên băng nhập của LBA vào việc đó.

Cho G = (V, T, P, S) là một CSG, ta xây dựng ôtômát LBA M như sau: Băng nhập của LBA gồm hai rãnh : rãnh 1 chứa chuỗi nhập w với các ký hiệu đánh dấu , $ ở hai đầu, rãnh 2 dùng để phát sinh các dạng câu . Trạng thái bắt đầu, nếu w =  thì M ngừng và không chấp nhận input, nếu không thì đầu đọc viết ký hiệu S ở rãnh 2, ngay dưới ký hiệu bên trái nhất của chuỗi w, tiếp đó M thực hiện quá trình sau:

1) Chọn trong số không đơn định một chuỗi con  của chuỗi  trên rãnh 2 sao cho    là một luật sinh trong P.

2) Thay  bởi , nếu cần thiết ta phải dịch chuyển phần cuối chuỗi sang phải cho đủ chỗ, tuy nhiên nếu dịch chuyển ra ngoài $ thì LBA ngừng và không chấp nhận.

3) (Hình thái hiện tại ở rãnh 1 là  w $, còn ở rãnh 2 là chuỗi , mà S G  và      w ). So sánh rãnh 1 và rãnh 2, nếu  = w thì LBA ngừng và chấp nhận w. Nếu không thì trở về bước (1).

Như vậy khi M chấp nhận chuỗi w, thì S G* w. Ngược lại nếu S G* w thì mọi dạng câu  xuất hiện trong chuỗi dẫn xuất đó đều thoả mãn      w , bởi vì mọi luật sinh    trong văn phạm G đều thỏa       . Như vậy M có thể thực hiện chuỗ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Ý 8.3 : Nếu L = L(M) với một LBA M (Q, , ,,qo,, $, F) thì L – {} là một ngôn ngữ cảm ngữ cảnh.

Chứng minh

Cách chứng minh định lý này cũng tương tự như cách chứng minh của định lý 7.10 ở chương trước, bằng cách ta xây dựng một CSG G thực hiện 3 giai đoạn:

Questions & Answers

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
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
Introduction about quantum dots in nanotechnology
Praveena Reply
what does nano mean?
Anassong Reply
nano basically means 10^(-9). nanometer is a unit to measure length.
Bharti
do you think it's worthwhile in the long term to study the effects and possibilities of nanotechnology on viral treatment?
Damian Reply
absolutely yes
Daniel
how did you get the value of 2000N.What calculations are needed to arrive at it
Smarajit Reply
Privacy Information Security Software Version 1.1a
Good
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