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!
: Puoi dire perché abbiamo bisogno di fare n-1 produzioni del primo modulo. – justin
Sicuro! Ogni terminale nella stringa risultante viene alla fine formato prendendo un non terminale e espandendolo ad un terminale tramite una produzione del modulo A -> a. Ciò significa che, ad un certo punto, è necessario produrre un totale di n non terminali. Uno di questi viene gratuitamente dal simbolo di partenza. Ogni volta che esegui una produzione del modulo A -> BC, ottieni un altro non terminale. Pertanto, è necessario eseguire n-1 produzioni del modulo A -> BC in modo da poter creare i non-minuti aggiuntivi n-1 necessari. – templatetypedef
: Oh intendi dire che il '-1' dell'espressione 'n-1' viene da quando uno di questi viene liberato dal simbolo di inizio? – justin