Chomsky Normal Formu

Üretimler aşağıdaki biçimlerde ise bir CFG Chomsky Normal Formundadır -

• A → a
• A → BC
• S → ε

A, B ve C'nin terminal olmadığı durumlarda ve a terminaldir.

Chomsky Normal Formuna Dönüştürülecek Algoritma -

Step 1 - Başlangıç ​​sembolü S sağ tarafta ortaya çıkarsa, yeni bir başlangıç ​​sembolü oluştur S’ ve yeni bir üretim S’→ S.

Step 2- Null yapımları kaldırın. (Daha önce tartışılan Boş üretim kaldırma algoritmasını kullanma)

Step 3- Birim üretimleri kaldırın. (Daha önce tartışılan Birim üretim kaldırma algoritmasını kullanarak)

Step 4 - Her üretimi değiştirin A → B₁…B_n nerede n > 2 ile A → B₁C nerede C → B₂ …B_n. Sağ tarafta iki veya daha fazla sembol bulunan tüm üretimler için bu adımı tekrarlayın.

Step 5 - Herhangi bir üretimin sağ tarafı formda ise A → aB nerede bir terminaldir ve A, B terminal değilse, üretimin yerini alır A → XB ve X → a. Formda olan her üretim için bu adımı tekrarlayınA → aB.

Sorun

Aşağıdaki CFG'yi CNF'ye dönüştürün

S → ASA | aB, A → B | S, B → b | ε

Çözüm

(1) Dan beri S RHS'de görünüyor, yeni bir durum ekliyoruz S₀ ve S₀→S üretim setine eklenir ve -

S ₀ → S, S → ASA | aB, A → B | S, B → b | ∈

(2) Şimdi boş yapımları kaldıracağız -

B → ∈ ve A → ∈

B → ε kaldırıldıktan sonra üretim seti -

S ₀ → S, S → ASA | aB | a, A → B | S | ∈, B → b

A → ∈ kaldırıldıktan sonra üretim seti -

S ₀ → S, S → ASA | aB | a | AS | SA | S, A → B | S, B → b

(3) Şimdi birim üretimleri kaldıracağız.

S → S kaldırıldıktan sonra üretim seti -

S ₀ → S, S → ASA | aB | a | AS | SA, A → B | S, B → b

S ₀ → S kaldırıldıktan sonra üretim seti -

S ₀ → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → B | S, B → b

A → B kaldırıldıktan sonra üretim seti -

S ₀ → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → S | b

B → b

A → S kaldırıldıktan sonra üretim seti -

S ₀ → ASA | aB | a | AS | SA, S → ASA | aB | a | AS | SA

A → b | ASA | aB | a | AS | SA, B → b

(4) Şimdi, RHS'de ikiden fazla değişken bulacağız

Burada, S ₀ → ASA, S → ASA, A → ASA, RHS'de iki Terminal Olmayan'ı ihlal ediyor

Bu nedenle, CNF'deki aşağıdaki son üretim setini elde etmek için 4. ve 5. adımları uygulayacağız -

S ₀ → AX | aB | a | AS | SA

S → AX | aB | a | AS | SA

A → b | AX | aB | a | AS | SA

B → b

X → SA

(5)Üretimleri değiştirmemiz gerekiyor S ₀ → aB, S → aB, A → aB

Ve son üretim seti -

S ₀ → AX | YB | a | AS | SA

S → AX | YB | a | AS | SA

A → b A → b | AX | YB | a | AS | SA

B → b

X → SA

Y → a