Dilbilgisini Chomsky Normal Formuna Dönüştürmek?

Question

Aşağıdaki dilbilgisini Chomsky Normal Formuna dönüştürün. Tüm ara adımları verin.

S0 -> S 
S -> AB | aB | B 
A -> aab 
B -> bbA | bb 

: İlk yaptığım şimdi ben o zaman lambda tüm kuralları kaldırıldı

S0 -> S 
S -> AB | aB 
A -> aab|lambda 
B -> bbA 

sahip S0

yeni bir başlangıç ​​değişken eklemek nedenle

S -> AB | aB 
A -> aab|lambda 
B -> bbA 

Tamam

Daha sonra S->S ve A->B türlerini kontrol ettim olmayan kurallar. Bu benim ortaya koyduğum cevaptı, daha fazla bir şey yapmam gerekiyor mu yoksa yanlış bir şey mi yaptım?

Answer 1

Vikipedi diyor:

bilgisayar biliminde

, bir bağlam-gramer üretim kurallarının tüm formunun ise Chomsky normal formda olduğu söylenir:

• A ->BC veya
• bir -> α veya
• S -> ε

burada bir, B, Cı terminal olmayan semboller, α bir bitiş simgesi, S başlangıç ​​sembolüdür ve ε boş bir dizge olmasıdır. Ayrıca, ne B ne de C başlangıç ​​sembolü olabilir.

çalışmanızı devam edelim: Bunun yerine farklı seçenekleri belirtmek için | kullanmanın

S0 -> S 
S -> AB | aB | B 
A -> aab 
B -> bbA | bb 

, birden fazla kurala içine bir kural bölün. yakında onları gerekir çünkü

S0 -> S 
S -> AB 
S -> aB 
S -> B 
A -> aab 
B -> bbA 
B -> bb 

yeni kurallar Y -> a ve Z -> b oluşturun. a bir terminal, çünkü

S0 -> S 
S -> AB 
S -> aB 
S -> B 
A -> aab 
B -> bbA 
B -> bb 
Y -> a 
Z -> b 

S -> aB formu S -> BC ait değildir.Yani Y içine a değiştirin:

S0 -> S 
S -> AB 
S -> YB 
S -> B 
A -> aab 
B -> bbA 
B -> bb 
Y -> a 
Z -> b 

B -> bb kural için de yapın:

A -> aab için

S0 -> S 
S -> AB 
S -> YB 
S -> B 
A -> aab 
B -> bbA 
B -> ZZ 
Y -> a 
Z -> b 

, C -> YY oluşturmak; kural S sağ tarafta oluştuğu

S0 -> S 
S -> AB 
S -> YB 
S -> B 
A -> CZ 
C -> YY 
B -> DA 
D -> ZZ 
B -> ZZ 
Y -> a 
Z -> b 

S -> B, bir kural çoğaltmak ve satır içi:

S0 -> B 
S0 -> S 
S -> AB 
S -> YB 
A -> CZ 
C -> YY 
B -> DA 
D -> ZZ 
B -> ZZ 
Y -> a 
Z -> b 

Anlaşma ile B -> bbA için, D -> ZZ oluşturmak Sağ tarafa sola katılarak S0 -> B ve S0 -> S kuralları diğer kuralların el tarafları. Ayrıca, (LHS sembolü RHS kullanılan geçmez) yetim kuralları silin:

S0 -> DA 
S0 -> ZZ 
S0 -> AB 
S0 -> YB 
A -> CZ 
C -> YY 
B -> DA 
D -> ZZ 
B -> ZZ 
Y -> a 
Z -> b 

Ve bitti. Uf!

Answer 2

Alternatif cevap: gramer yalnızca yani 6.

S -> aabbbaab | aabbb | bbaab | bb | abbaab | abb. 

Artık elle Chomsky Normal Form bunu geri yoğunlaşmasına olabilir, dizeleri sınırlı sayıda üretebilir.

---

Değiştirme yoluyla, üretilen tüm dizelerin kümesini bulabiliriz. Başlangıçtaki kurallar:

: almak için tekrar bu Expand

S -> AB 
    -> (aab | lambda) bbA 
    -> (aab | lambda) bb (aab | lambda). 
S -> aB 
    -> abbA 
    -> abb (aab | lambda). 

:

S -> AB. 
S -> aB. 

Şimdi içine A ve B genişletildiğini yerine:

S -> AB | aB. 
A -> aab | lambda. 
B -> bbA. 

İlk S kural bölmek

S -> aabbbaab. 
S -> aabbb. 
S -> bbaab. 
S -> bb. 
S -> abbaab. 
S -> abb. 

---

Bu sonlu ayarını Chomsky Normal Form olarak değiştirmek için, herhangi bir akıllı faktoring olmaksızın kaba kuvvetle yapılması yeterlidir.

X -> a. 
Y -> b. 

Şimdi her dize için, biz bir terminal değişkenle ilk harfini ve yeni değişkenlerle kalan harfler tüketmek: Önce iki uç kurallar getirecek. Böyle Örneğin,:

S -> aabbb. (initial rule, not in Chomsky Normal Form) 

S -> XC, where X->a and C->abbb. 
C -> XD, where X->a and D->bbb. 
D -> YE, where Y->b and E->bb. 
E -> YY, where Y->b and Y->b. 

Biz sadece yeni ara değişkenlerin çok üreten, 6 dizeleri için bu işleme devam edin.

Answer 3

Çok fazla teoriye ve provaya girmeden (buna Wikipedia'da bakabilirsiniz), Bağlamsız Gramer'i Chomsky Normal Formuna dönüştürürken yapmanız gereken birkaç şey vardır, genellikle dört Normal Form gerçekleştirmeniz gerekir. Dönüşümler. Öncelikle, boş dizeyi (lambda/epsilon) doğrudan veya dolaylı olarak verebilen tüm değişkenleri tanımlamanız gerekir (Lambda-Free formu). İkincisi, birim yapımlarını kaldırmanız gerekir - (Birim-Serbest form). Üçüncü olarak, canlı/yararlı olan tüm değişkenleri bulmanız gerekir (Yararlılık). Dört, tüm ulaşılabilir sembolleri bulmanız gerekiyor (Ulaşılabilir). Her adımda yeni bir dilbilgisi olabilir veya olmayabilir. Yani sorun için bu ben

---

Bağlam-Serbest Gramer

G(Variables = { A B S } 
Start = S 
Alphabet = { a b lamda} 

Production Rules = { 
S -> | AB | aB | 
A -> | aab | lamda | 
B -> | bbA | }) 

Kaldır lambda/epsilon

ERRASABLE(G) = { A } 

G(Variables = { A S B } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | aB | B | 
B -> | bbA | bb | }) 

Kaldır birimi produtions

UNIT(A) { A } 
UNIT(B) { B } 
UNIT(S) { B S } 
G (Variables = { A B S } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | aB | bb | bbA | 
A -> | aab | 
B -> | bbA | bb | }) 

... ile geldi budur

Canlı sembolü belirle s

LIVE(G) = { b A B S a } 

G(Variables = { A B S } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | aB | bb | bbA | 
A -> | aab | 
B -> | bbA | bb | }) 

ulaşılamaz

REACHABLE (G) = { b A B S a } 
G(Variables = { A B S } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | aB | bb | bbA | 
A -> | aab | 
B -> | bbA | bb | }) 

katı nonterminallerin ile tüm karışık dizeleri değiştirin Kaldır

G(Variables = { A S B R I } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | RB | II | IIA | 
A -> | RRI | 
B -> | IIA | II | 
R -> | a | 
I -> | b | }) 

Chomsky Normal Form

G(Variables = { V A B S R L I Z } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | RB | II | IV | 
A -> | RL | 
B -> | IZ | II | 
R -> | a | 
I -> | b | 
L -> | RI | 
Z -> | IA | 
V -> | IA | })