Derivation là gì?

Trong automata, dẫn xuất (derivation) là một chuỗi các luật sinh (production rule). Nó được sử dụng để lấy chuỗi đầu vào thông qua các luật sinh này. Trong quá trình phân tích cú pháp, chúng ta phải đưa ra hai quyết định. Những điều này như sau:

• Chúng ta phải quyết định kí hiệu không kết thúc (nonterminal) nào sẽ được thay thế.
• Chúng ta phải quyết định luật sinh nào mà theo đó kí hiệu không kết thúc sẽ được thay thế.

Chúng ta có hai tùy chọn để quyết định kí hiệu không kết thúc nào sẽ được thay thế với luật sinh: dẫn xuất trái nhất (leftmost derivation) và dẫn xuất phải nhất (rightmost derivation).

Ví dụ tìm dẫn xuất của chuỗi "9-5+2" sử dụng dẫn xuất trái nhất bằng cách văn phạm phi ngữ cảnh (context-free grammar) có các luật sinh sau:

S → aB | bA  
S → a | aS | bAA  
S → b | aS | aBB  

S  
aB            S → aB      
aaBB          B → aBB  
aabB          B → b  
aabbS         B → bS  
aabbaB        S → aB  
aabbabS       B → bS  
aabbabbA      S → bA  
aabbabba      A → a  

Dẫn xuất (derivation hoặc yield) của cây phân tích cú pháp (parse tree) là chuỗi (string) cuối cùng thu được bằng cách nối các nhãn của các nút lá (leaf node) của cây phân tích cú pháp từ trái sang phải, bỏ qua các Null. Tuy nhiên, nếu tất cả các nút lá là Null, thì dẫn xuất là Null.

Ví dụ giả sử cho một CFG {N, T, P, S} là N = {S}, T = {a, b}, ký hiệu xuất phát (start symbol) = S, luật sinh (production rule) P = S → SS | aSb | ε

Một dẫn xuất từ CFG ở trên là "abaabb"

S → SS → aSbS → abS → abaSb → abaaSbb → abaabb