<< 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

what is the guess theorem
Monu Reply
viva question and answer on practical youngs modulus by streching
Akash Reply
send me vvi que
rupesh
a car can cover a distance of 522km on 36 Liter's of petrol, how far can it travel on 14 liter of petrol.
Isaac
whats a two dimensional force
Jimoh Reply
what are two dimensional force?
Ahmad
Where is Fourier Theorem?
Atul Reply
what is Boyle's law
Amoo Reply
Boyle's law state that the volume of a given mass of gas is inversely proportion to its pressure provided that temperature remains constant
Abe
how do I turn off push notifications on this crap app?
Huntergirl
what is the meaning of in.
CHUKWUMA Reply
In means natural logarithm
Elom
is dea graph for cancer caliper experiment using glass block?
Bako
identity of vectors?
Choudhry Reply
what is defined as triple temperature
Prince Reply
Triple temperature is the temperature at which melting ice and boiling water are at equilibrium
njumo
a tire 0.5m in radius rotate at constant rate 200rev/min. find speed and acceleration of small lodged in tread of tire.
Tahira Reply
hmm
Ishaq
100
Noor
define the terms as used in gravitational mortion 1:earth' satellites and write two example 2:parking orbit 3:gravitation potential 4:gravitation potential energy 5:escping velocity 6:gravitation field and gravitation field strength
Malima Reply
can gravitational force cause heat?
SANT
yes
Kawshik
_2/3 ÷34
Isaac
what larminar flow
Rajab Reply
smooth or regular flow
Roha
Hii
Sadiq
scalar field define with example
Malik Reply
what is displacement
Isaac Reply
the change in the position of an object in a particular direction is called displacement
Noor
The physical quantity which have both magnitude and direction are known as vector.
Malik
good
Noor
Describe vector integral?
Malik
define line integral
Malik
Examples on how to solve terminal velocity
Louis Reply
what is Force?
Bibas Reply
ans:loading...
Lumai
the sideways pressure exerted by fluid is equal and canceled out.how and why?
Chaurasia
Got questions? Join the online conversation and get instant answers!
QuizOver.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