Come posso dimostrare che le derivazioni in Chomsky Normal Form richiedono 2n - 1 step?

Question

sto cercando di dimostrare il seguente:

Se G è un contesto libero grammatica nel Chomsky forma normale, quindi per ogni stringa w appartiene L (G) di lunghezza n ≥ 1, richiede esattamente 2n -1 passi per fare qualsiasi derivazione di w.

Come farei a provare questo?

Answer 1

Come un suggerimento - poiché ogni produzione Chomsky forma normale sia ha la forma

S → AB, per non-terminali A e B, o la forma

S → x, per terminale x,

Poi derivante una stringa avrebbe funzionato nel modo seguente:

• Creare una stringa di esattamente n non terminali, quindi
• Espandere ciascun terminale non terminale su un singolo terminale.

Applicazione produzioni della prima forma aumenterà il numero di nonterminali da k a k + 1, poiché si sostituisce un non terminale (-1) con due nonterminals (+2) per un guadagno netto di +1 non terminale. Dal momento in cui inizi con un non terminale, questo significa che devi fare n-1 produzioni del primo modulo. Allora hai bisogno di n più del secondo modulo per convertire i terminali non terminali ai terminali, dando un totale di n + (n - 1) = 2n - 1 produzioni.

per dimostrare che è necessario esattamente questo molti, vorrei suggerire di fare una dimostrazione per assurdo e mostrando che non si può farlo con più o meno. Come suggerimento, prova a contare il numero di produzioni di ogni tipo che viene fatto e mostra che se non è 2n - 1, o la stringa è troppo corta, o rimarranno ancora non terminali.

Spero che questo aiuti!