Conversione della grammatica in forma normale di Chomsky?

Question

Converti la grammatica in basso in Chomsky Normal Form. Dare tutti i passaggi intermedi.

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

Ok, quindi la prima cosa che ho fatto è stato aggiungere una nuova variabile inizio S0

così ora ho

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

poi ho tolto tutte le regole lambda:

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

Quindi ho controllato il tipo S->S e A->B regole che non esistevano. E questa è stata la risposta che ho trovato, devo fare qualcosa di più o ho fatto qualcosa di sbagliato?

Answer 1

Wikipedia dice:

In informatica, una grammatica context-free si dice che sia in Chomsky forma normale se tutti i suoi disciplinare di produzione sono di forma:

• A ->aC, o
• A -> α, o
• S -> ε

dove A, B, C sono simboli non terminali, α è un simbolo terminale, S è il simbolo iniziale, ed ε è la stringa vuota. Inoltre, né B né C possono essere il simbolo di avvio.

Continuando il vostro lavoro:

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

Invece di usare | per indicare scelte diverse, dividere una regola in più regole.

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

creare nuove regole Y -> a e Z -> b perché avremo bisogno di loro al più presto.

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

S -> aB non è di forma S -> BC perché a è un terminale.Quindi cambiare a in Y:

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

fare lo stesso per la B -> bb regola:

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

Per A -> aab, creare C -> YY; per B -> bbA, creare D -> ZZ:

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

Per S -> B, duplicare la sola regola in cui S si verifica sul lato destro e inline la regola:

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

Deal con le regole S0 -> B e S0 -> S unendo il lato destro a sinistra lati della mano di altre regole. Inoltre, eliminare le regole orfani (dove il simbolo LHS non viene mai utilizzato su RHS):

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

E abbiamo finito. Accidenti!

Answer 2

risposta alternativa: La grammatica può produrre solo un numero finito di stringhe, ovvero 6.

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

È ora possibile condensare questo torna a Chomsky Normal Form a mano.

---

Per la sostituzione, si può trovare l'insieme di tutte le stringhe prodotte. Le regole iniziali:

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

Prima dividere la S regola:

S -> AB. 
S -> aB. 

Ora sostituire ciò che A e B espandersi in:

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

espandere questi di nuovo per ottenere:

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

---

Per modificare questo set finito su Chomsky Normal Form, è sufficiente farlo con la forza bruta senza alcun factoring intelligente. In primo luogo si introducono due regole terminali:

X -> a. 
Y -> b. 

Ora, per ogni stringa, che consumiamo la prima lettera con una variabile terminale e le restanti lettere con un nuove variabili. Ad esempio, in questo modo:

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. 

Abbiamo appena passare attraverso questo processo per tutte le 6 corde, generando un sacco di nuove variabili intermedie.

Answer 3

Senza entrare troppo in teoria e prove (si potrebbe guardare a questo in Wikipedia), ci sono alcune cose che devi fare quando converti una Grammatica Context Free in Chomsky Normal Form, generalmente devi eseguire quattro Normal-Form trasformazioni. Innanzitutto, è necessario identificare tutte le variabili che possono produrre la stringa vuota (lambda/epsilon), direttamente o indirettamente - (forma Lambda-Free). In secondo luogo, è necessario rimuovere le produzioni di unità - (modulo Unit-Free). Terzo, devi trovare tutte le variabili che sono vivi/utili (Utilità). Quattro, è necessario trovare tutti i simboli raggiungibili (Raggiungibile). Ad ogni passo potresti o non potresti avere una nuova grammatica. Così per il vostro problema questo è ciò che mi è venuta ...

---

Context-Free Grammar

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

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

Rimuovere lambda/Epsilon

ERRASABLE(G) = { A } 

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

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

unità Rimuovi 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 | }) 

Determinare simbolo live 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 | }) 

Rimuovere irraggiungibile

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 | }) 

sostituire tutte le stringhe misti con nonterminals solidi

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 forma normale

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 | })