Greibach Dạng bình thường
CFG ở dạng Greibach Normal nếu Sản phẩm ở các dạng sau:
A → b
A → bD 1 … D n
S → ε
trong đó A, D 1 , ...., D n là không đầu cuối và b là đầu cuối.
Thuật toán chuyển đổi CFG thành Dạng chuẩn Greibach
Step 1 - Nếu ký hiệu bắt đầu S xảy ra ở một số bên phải, tạo một biểu tượng bắt đầu mới S’ và một sản xuất mới S’ → S.
Step 2- Loại bỏ các sản phẩm Null. (Sử dụng thuật toán loại bỏ sản xuất Null đã thảo luận trước đó)
Step 3- Loại bỏ các sản phẩm đơn vị. (Sử dụng thuật toán loại bỏ sản xuất đơn vị đã thảo luận trước đó)
Step 4 - Loại bỏ tất cả các đệ quy trái trực tiếp và gián tiếp.
Step 5 - Thực hiện thay thế thích hợp các sản phẩm để chuyển nó thành dạng GNF thích hợp.
Vấn đề
Chuyển đổi CFG sau thành CNF
S → XY | Xn | p
X → mX | m
Y → Xn | o
Giải pháp
Đây, Skhông xuất hiện ở bên phải của bất kỳ sản phẩm nào và không có đơn vị hoặc sản phẩm rỗng trong bộ quy tắc sản xuất. Vì vậy, chúng ta có thể bỏ qua Bước 1 đến Bước 3.
Step 4
Bây giờ sau khi thay thế
X trong S → XY | Xo so | p
với
mX | m
chúng tôi đạt được
S → mXY | mY | mXo | mo | p.
Và sau khi thay thế
X trong Y → X n | o
với phía bên phải của
X → mX | m
chúng tôi đạt được
Y → mXn | mn | o.
Hai sản phẩm mới O → o và P → p được thêm vào tập hợp sản xuất và sau đó chúng tôi đi đến GNF cuối cùng như sau:
S → mXY | mY | mXC | mC | p
X → mX | m
Y → mXD | mD | o
O → o
P → p