Sự mơ hồ trong ngữ pháp không có ngữ cảnh

Nếu ngữ pháp không có ngữ cảnh G có nhiều hơn một cây dẫn xuất cho một số chuỗi w ∈ L(G), nó được gọi là ambiguous grammar. Tồn tại nhiều dẫn xuất ngoài cùng bên phải hoặc ngoài cùng bên trái cho một số chuỗi được tạo từ ngữ pháp đó.

Vấn đề

Kiểm tra xem ngữ pháp G với các quy tắc sản xuất -

X → X + X | X * X | X | a

là mơ hồ hay không.

Giải pháp

Hãy cùng tìm hiểu cây dẫn xuất cho chuỗi "a + a * a". Nó có hai dẫn xuất ngoài cùng bên trái.

Derivation 1- X → X + X → a + X → a + X * X → a + a * X → a + a * a

Parse tree 1 -

Derivation 2- X → X * X → X + X * X → a + X * X → a + a * X → a + a * a

Parse tree 2 -

Vì có hai cây phân tích cú pháp cho một chuỗi "a + a * a", ngữ pháp G là mơ hồ.