Forma normală Chomsky

Forma normală Chomsky este o proprietate a unei gramatici formale dacă toate rezultatele sale sunt de forma:

A

\rightarrow \,BC

A

\rightarrow \,\alpha

S

\rightarrow \,\epsilon

unde , și sunt non-terminale, este un caracter terminal (reprezentând o valoare constantă), este un caracter de început și este șirul gol . De asemenea, nici , nici nu poate fi un caracter de început. $A$ $B$ $C$ $\alfa$ $S$ $\epsilon$ $B$ $C$

Fiecare gramatică în forma normală Chomsky este fără context și, invers, fiecare gramatică fără context poate fi convertită eficient într-o gramatică echivalentă în forma normală Chomsky.

Cu excepția unei posibile reguli (folosită atunci când gramatica poate produce șirul gol), toate regulile gramaticale în forma normală Chomsky sunt nescurtatoare; adică, în procesul de ieșire a unui șir, fiecare lanț de terminale și non-terminale are întotdeauna fie aceeași lungime ca și cel precedent, fie încă un element. Imprimarea unui șir de lungime durează întotdeauna exact pași. În plus, deoarece toate regulile de inferență nonterminale traduc un nonterminal într-un singur terminal sau exact în două nonterminale, arborele de analiză bazat pe gramatica formei normale Chomsky este un arbore binar a cărui înălțime este limitată de lungimea șirului. $S$ $\rightarrow \,\epsilon$ $n$ $2n-1$

Datorită acestor proprietăți, multe dovezi în teoria limbajelor formale și a calculabilității folosesc forma normală Chomsky. Aceste proprietăți servesc și ca bază pentru diverși algoritmi eficienți - de exemplu, algoritmul CYK care determină dacă un șir dat poate fi generat de o anumită gramatică folosește forma normală Chomsky.

Numit după Noam Chomsky , lingvistul american care a propus ierarhia lui Chomsky .

Definiție alternativă

Unele surse definesc forma normală a lui Chomsky oarecum diferit.

O gramatică formală este în forma normală Chomsky dacă toate rezultatele sale sunt de forma:

A

\rightarrow \,BC

A

\rightarrow \,\alpha

unde , și sunt non-terminale și este simbolul terminal al . Când utilizați această definiție , și pot fi caractere inițiale. $A$ $B$ $C$ $\alfa$ $B$ $C$

Această definiție diferă de cea anterioară prin faptul că exclude posibilitatea de a genera un șir gol . Este încă adevărat că orice gramatică fără context care generează o limbă poate fi transformată efectiv într-o formă normală Chomsky care generează . Avantajul principal al ultimei definiții este că dovezile în general sunt oarecum simplificate, deoarece fiecare pas de derivare nu reduce niciodată lungimea șirului rezultat. Desigur, dezavantajul său este că necesită o analiză separată a cazului în care gramatica generează . $\epsilon$ $L$ $L-\{\epsilon \)$ $\epsilon$

Literatură

Michael Sipser Introducere în teoria calculului . - Editura PWS, 1997. - ISBN 0-534-94728-X . (Paginile 98-101 din secțiunea 2.1: gramatici fără context. Pagina 156.)
Ioan Martin . Introducere în limbaje și teoria calculului . - McGraw-Hill Education , 2003. - ISBN 0-07-232200-4 . (Paginile 237-240 din secțiunea 6.6: forme simplificate și forme normale.)
John E. Hopcroft și Jeffrey D. Ullman, Introducere în teoria automatelor, limbaje și calcul , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X . (Vezi capitolul 4.)
Michael A HarrisonIntroducere în teoria limbajului formal (neopr.) . - Addison-Wesley , 1978. - ISBN 978-0201029550 . (Paginile 103-106.)