Forma normale di Chomsky

Nella teoria dei linguaggi formali, una grammatica libera dal contesto si dice essere nella forma normale di Chomsky (CNF,^[1] o FNC, dall'inglese Chomsky normal form) (scoperta da Noam Chomsky)^[2] se tutte le sue regole di produzione sono nella forma seguente:^[1][3]

${\displaystyle A\rightarrow BC}$ o

${\displaystyle A\rightarrow a}$ o

${\displaystyle S\rightarrow \varepsilon }$,

dove ${\displaystyle A}$, ${\displaystyle B}$ e ${\displaystyle C}$ sono simboli non terminali, ${\displaystyle a}$ è un simbolo terminale (un simbolo che rappresenta un valore costante), ${\displaystyle S}$ è l'assioma di partenza, ${\displaystyle \varepsilon }$ è la stringa vuota, e ${\displaystyle B\neq S\land C\neq S}$.

Tutte le grammatiche nella forma normale di Chomsky sono non contestuali e, viceversa, tutte le grammatiche non contestuali possono essere trasformate in grammatiche equivalenti in FNC. Per eseguire tale trasformazione sono stati ideati più algoritmi. Tuttavia, come fatto notare da Lange e Leiß,^[4] lo svantaggio di queste trasformazioni sta nel grande aumento della dimensione della grammatica, dove tale dimensione equivale alla somma delle dimensioni delle regole di produzione, le quali, a loro volta, equivalgono a 1 più la lunghezza della parte destra. Denotando con ${\displaystyle |G|}$ la dimensione della grammatica originale ${\displaystyle G}$, la crescita di tale dimensione nel peggiore dei casi è compresa fra ${\displaystyle |G|^{2}}$ a ${\displaystyle 2^{2|G|}}$ (dipende dall'algoritmo di trasformazione utilizzato).

Definizione alternativa

Forma ridotta di Chomsky

Un altro modo per definire la forma normale di Chomsky normal form è:

Una grammatica formale è in forma ridotta di Chomsky se tutte le sue regole di produzione sono nella forma seguente:

${\displaystyle A\rightarrow \,BC}$ o

${\displaystyle A\rightarrow \,a}$,

dove ${\displaystyle A}$, ${\displaystyle B}$ e ${\displaystyle C}$ sono simboli non terminali e ${\displaystyle a}$ è un simbolo terminale. Solo le grammatiche context-free che non ammettono epsilon-produzioni possono essere rese in questa forma.

Forma normale di Floyd

In un articolo in cui propose la Backus-Naur Form (BNF), Donald E. Knuth suggerì una «sintassi [BNF] in cui tutte le definizioni aventi tale forma sono dette essere in "forma normale di Floyd"»:

${\displaystyle \langle A\rangle$ ::=\,\langle B\rangle \mid \langle C\rangle } o

${\displaystyle \langle A\rangle$ ::=\,\langle B\rangle \langle C\rangle } o

${\displaystyle \langle A\rangle$ ::=\,a} ,

dove ${\displaystyle \langle A\rangle }$, ${\displaystyle \langle B\rangle }$ e ${\displaystyle \langle C\rangle }$ sono simboli non terminali e ${\displaystyle a}$ è un simbolo terminale. Il nome si riferisce a Robert W. Floyd, che nel 1961 scoprì che ogni sintassi BFN può essere convertita in tale forma.^[5]

Convertire una grammatica nella FNC

1. Introdurre ${\displaystyle S_{0}}$

   Introdurre un nuovo simbolo di partenza, ${\displaystyle S_{0}}$ e una nuova regola ${\displaystyle S_{0}\rightarrow S}$, dove ${\displaystyle S}$ è il precedente assioma.

2. Eliminare tutte le ${\displaystyle \varepsilon }$-produzioni

   Le ${\displaystyle \varepsilon }$-produzioni sono regole della forma ${\displaystyle A\rightarrow \varepsilon }$, dove ${\displaystyle A\not =S_{0}}$ e ${\displaystyle A\in V}$ e ${\displaystyle V}$ è l'alfabeto delle variabili della grammatica CF.

   Rimuovere ogni regola con ${\displaystyle \varepsilon }$ alla propria destra. Per ogni regola con ${\displaystyle A}$ alla propria destra, aggiungere un insieme di nuove regole consistente delle possibili combinazioni di ${\displaystyle A}$ sostituito o meno da ${\displaystyle \varepsilon }$. Per esempio, esaminando la seguente grammatica ${\displaystyle G}$:

   ${\displaystyle S\rightarrow AbA\mid B}$

   ${\displaystyle B\rightarrow b\mid c}$

   ${\displaystyle A\rightarrow \varepsilon }$

   ${\displaystyle G}$ ha una ${\displaystyle \varepsilon }$-produzione. Quando ${\displaystyle A\rightarrow \varepsilon }$ viene rimossa, la grammatica va modificata nella maniera seguente:

   ${\displaystyle S\rightarrow AbA\mid Ab\mid bA\mid b\mid B}$

   ${\displaystyle B\rightarrow b\mid c}$

   Da notare che a partire dalla prima regola ne sono state aggiunte tre nuove (${\displaystyle S\rightarrow Ab\mid bA\mid b}$), in ciascuna delle quali almeno un simbolo ${\displaystyle A}$ viene sostituito con ${\displaystyle \varepsilon }$.

3. Eliminare tutte le regole unitarie

   ${\displaystyle A\rightarrow B;A,B\in V}$

   Dopo aver rimosso le ${\displaystyle \varepsilon }$-produzioni, vanno rimosse tutte le regole unitarie e le regole che nella parte destra non hanno simboli terminali.

   Per rimuovere ${\displaystyle A\rightarrow B}$

   ${\displaystyle \forall B\rightarrow U}$, dove ${\displaystyle U}$ è una stringa di variabili generiche, aggiungere ${\displaystyle A\rightarrow U}$ a meno che non sia una regola unitaria già rimossa.

4. Sistemare le rimanenti regole di produzione che non sono ancora nella FNC.

   Sostituire ${\displaystyle A\rightarrow u_{1}u_{2}\dotso u_{k},k\geq 3,u_{1}\in V\cup \Sigma }$ con ${\displaystyle A\rightarrow u_{1}A_{1},A_{1}\rightarrow u_{2}A_{2},\dotsc ,A_{k-2}\rightarrow u_{k-1}u_{k}}$, dove ${\displaystyle A_{i}}$ sono nuove variabili.

Note

1. Ausiello, 2003, p. 128.
2. (EN) Noam Chomsky, On Certain Formal Properties of Grammars, in Information and Control, vol. 2, 1959, pp. 137–167, DOI:10.1016/S0019-9958(59)90362-6.
3. Hopcroft, Ullman (1979); Theorem 4.5, sect.4.5, p.92; see also p.106
4. (EN) Martin Lange, Hans Leiß, To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm (PDF), su ddi.cs.uni-potsdam.de, 2009.
5. Donald E. Knuth. 1964. Backus Normal Form vs. Backus Naur Form. Communications of the ACM, 7(12):735–736, December.

Bibliografia

• Richard Cole, Converting CFGs to CNF (Chomsky Normal Form) (PDF), Università di New York, 17 ottobre 2007.
• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 4.)
• Daniel Jurafsky e James H. Martin, Speech and Language Processing, 2nd, Pearson Prentice Hall, 2008, ISBN 978-0-13-187321-6.
• John Martin, Introduction to Languages and the Theory of Computation, McGraw Hill, 2003, ISBN 0-07-232200-4. (Pages 237–240 of section 6.6: simplified forms and normal forms.)
• Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997, ISBN 0-534-94728-X. (Pages 98–101 of section 2.1: context-free grammars. Page 156.)
• Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Linguaggi modelli complessità, Milano, Franco Angeli Editore, 2003, ISBN 88-464-4470-1.

Voci correlate

• Backus-Naur form
• Algoritmo CYK
• Forma normale di Greibach
• Forma normale di Kuroda
• Pumping lemma per i linguaggi liberi dal contesto

Portale Informatica

Portale Matematica