<< Chapter < Page Chapter >> Page >

A-cây có nút đỉnh là 3 tạo ra chuỗi con abba theo chuỗi dẫn xuất :

S Þ SbAÞ abA Þ abba

Câu hỏi :

?

Các cây dẫn xuất được sinh từ những chuỗi dẫn xuất khác nhau cho cùng một chuỗi nhập có là những cây dẫn xuất khác nhau không ?

Quan hệ giữa dẫn xuất và cây dẫn xuất

ĐỊNH LÝ 5.1 : Nếu G (V, T, P, S) là một văn phạm phi ngữ cảnh thì S *  nếu và chỉ nếu có cây dẫn xuất trong văn phạm sinh ra .

Chứng minh

Ta chứng minh rằng với biến A bất kỳ, A * nếu và chỉ nếu có một A-cây sinh ra .

Nếu: Giả sử  được sinh bởi A-cây, ta chứng minh quy nạp theo số nút trung gian của cây dẫn xuất rằng A *.

Nếu có 1 nút trung gian thì cây phải có dạng như hình sau :

Khi đó X1X2 ... Xn là chuỗi  và A   là một luật sinh trong P theo định nghĩa cây dẫn xuất.

Hình 5.2(a) - A-cây với một nút trong

Giả sử kết quả đúng tới k -1 nút trung gian ( k>1)

Ta chứng minh kết quả cũng đúng với k nút.

Xét  được sinh ra bởi A-cây có k nút trung gian. Rõ ràng các nút con của nút gốc không phải tất cả đều là lá, ta gọi chúng từ trái sang phải là X1, X2, ..., Xn thì chắc chắn rằng A  X1X2 ... Xn là một luật sinh. Xét nút Xi bất kỳ :

- Nếu Xi không là nút lá thì Xi phải là một biến và Xi - cây con sẽ sinh ra một chuỗi i nào đó.

- Nếu Xi là nút lá, ta đặt i = Xi. Dễ thấy rằng nếu j<i thì các j ở bên trái j, do vậy chuỗi đọc từ lá vẫn có dạng  = 12 ... n. Mỗi Xi - cây con phải có ít nút trung gian hơn cây ban đầu, vì thế theo giả thiết quy nạp, với mỗi đỉnh i không phải là lá thì Xi *i.

Vậy A  X1X2 ... Xn * 1X2 ... Xn * 12X3 ... Xn * ... * 12 ... n = 

Hay ta có A *  . Chú ý rằng đây chỉ là một trong nhiều cách dẫn xuất ra .

Chỉ nếu : Ngược lại, giả sử A *  ta cần chỉ ra một A - cây sinh ra .

Nếu A *  bằng một bước dẫn xuất thì A   là một luật sinh trong P và có cây dẫn xuất sinh ra  như trong hình trên.

Giả sử kết quả đúng tới k-1 bước dẫn xuất

Xét A *  bằng k bước dẫn xuất, gọi bước đầu tiên là A  X1X2 ... Xn.

Rõ ràng, một ký hiệu trong  phải được dẫn ra từ một biến Xi nào đó. Vì vậy, ta có thể viết  = 12 ... n, trong đó mỗi 1  i  n thoả mãn :

- i = Xi nếu Xi là ký hiệu kết thúc.

- Xi * i nếu Xi là một biến.

Nếu Xi là biến thì dẫn xuất của i từ Xi phải có ít hơn k bước. Vì vậy, theo giả thiết quy nạp ta có Xi - cây sinh ra i, đặt cây này là Ti

Bây giờ ta dựng A - cây có n lá X1X2 ... Xn. Mỗi Xi không là ký hiệu kết thúc ta thay bằng cây Ti tương ứng. Cuối cùng, ta có cây dẫn xuất sinh ra có dạng như sau :

Hình 5.2(b) - A-cây

Thí dụ 5.6 :Xét chuỗi dẫn xuất S * aabbaa cho văn phạm ở Thí dụ 5.4.

Bước đầu tiên trong dẫn xuất đó là S  aAS. Theo dõi các bước suy dẫn sau đó, ta thấy biến A được thay bởi SbA, rồi trở thành abA và cuối cùng thành abba, đó chính là kết quả của cây T2 (A - cây). Còn biến S thì được thay bởi a và đó là kết quả của cây T3 (S -cây). Ghép nối lại, ta được cây dẫn xuất mà kết quả là chuỗi aabbaa như dưới đây.

[

Hình 5.3 - Ghép nối các cây dẫn xuất

Dẫn xuất trái nhất, dẫn xuất phải nhất

Nếu tại mỗi bước dẫn xuất, luật sinh được áp dụng vào biến bên trái nhất thì ta gọi đó là dẫn xuất trái nhất (leftmost) hay dẫn xuất trái. Tương tự, nếu biến bên phải nhất được thay thế ở mỗi bước dẫn xuất, đó là dẫn xuất phải nhất (rightmost) hay dẫn xuất phải. Nếu chuỗi w  L(G) với CFG G thì w sẽ có ít nhất một cây dẫn xuất ra nó và tương ứng với các cây này, w chỉ có duy nhất một dẫn xuất trái nhất và duy nhất một dẫn xuất phải nhất. Dĩ nhiên, w có thể có nhiều dẫn xuất trái (phải) nhất vì nó có thể có nhiều cây dẫn xuất.

Questions & Answers

where we get a research paper on Nano chemistry....?
Maira Reply
nanopartical of organic/inorganic / physical chemistry , pdf / thesis / review
Ali
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
Google
da
no nanotechnology is also a part of physics and maths it requires angle formulas and some pressure regarding concepts
Bhagvanji
hey
Giriraj
Preparation and Applications of Nanomaterial for Drug Delivery
Hafiz Reply
revolt
da
Application of nanotechnology in medicine
what is variations in raman spectra for nanomaterials
Jyoti Reply
ya I also want to know the raman spectra
Bhagvanji
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
Nasa has use it in the 60's, copper as water purification in the moon travel.
Alexandre
nanocopper obvius
Alexandre
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
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