Chomsky normál forma

A Chomsky normálforma egy formális nyelvtan tulajdonsága , ha minden kimenete a következő alakú:

A

\rightarrow \,BC

vagy

A

\rightarrow \,\alpha

vagy

S

\rightarrow \,\epsilon

ahol , és nem terminálok, egy terminálkarakter (konstans értéket jelent), egy kezdőkarakter, és egy üres karakterlánc . Ezenkívül sem , sem nem lehet kezdő karakter. $A$ $B$ $C$ $\alpha$ $S$ $\epsilon$ $B$ $C$

A Chomsky normál formájú nyelvtanok mindegyike kontextusmentes , és fordítva, minden kontextus nélküli nyelvtan hatékonyan konvertálható egy ekvivalens nyelvtanra Chomsky normál formában.

Egy lehetséges szabály kivételével (amely akkor használatos, ha a nyelvtan képes előállítani az üres karakterláncot), a Chomsky normál formájú nyelvtani szabályok nem rövidítenek; azaz egy karakterlánc kiadása során minden terminál- és nem-terminális lánc mindig vagy ugyanolyan hosszúságú, mint az előző, vagy még egy elem. Egy hosszúságú karakterlánc nyomtatása mindig pontosan lépésekből áll. Ezen túlmenően, mivel minden nemterminális következtetési szabály egy nemterminálist pontosan egy terminálra vagy pontosan két nemterminálisra fordít le, a Chomsky-féle normálforma nyelvtanon alapuló elemzési fa egy bináris fa, amelynek magasságát a karakterlánc hossza korlátozza. $S$ $\rightarrow \,\epsilon$ $n$ $2n-1$

Ezeknek a tulajdonságoknak köszönhetően a formális nyelvek elméletében és a kiszámíthatóságban számos bizonyítás használja a Chomsky normálformát. Ezek a tulajdonságok különböző hatékony algoritmusok alapjául is szolgálnak - például a CYK algoritmus , amely meghatározza, hogy egy adott karakterlánc generálható-e egy adott nyelvtan által, Chomsky normál formát használ.

Nevét Noam Chomskyról , az amerikai nyelvészről kapta, aki a Chomsky-hierarchiát javasolta .

Alternatív definíció

Egyes források a Chomsky normálformát némileg eltérően határozzák meg.

Egy formális nyelvtan Chomsky normál formájú , ha minden kimenete a következő alakú:

A

\rightarrow \,BC

vagy

A

\rightarrow \,\alpha

ahol , és nem terminálok, és a terminál szimbóluma . Ennek a definíciónak a használatakor a és kezdő karakterek lehetnek. $A$ $B$ $C$ $\alpha$ $B$ $C$

Ez a definíció abban különbözik az előzőtől, hogy kizárja az üres karakterlánc létrehozásának lehetőségét . Továbbra is igaz, hogy bármely kontextusmentes nyelvtan , amely egy nyelvet generál, hatékonyan átalakítható egy Chomsky-normál formává, amely létrehozza a . Az utolsó definíció fő előnye, hogy a bizonyítások általában némileg leegyszerűsödnek, mivel az egyes levezetési lépések soha nem csökkentik a kapott karakterlánc hosszát. Természetesen a hátránya, hogy külön mérlegelni kell azt az esetet, amikor a nyelvtan generálja a -t . $\epsilon$ $L$ $L-\{\epsilon \}$ $\epsilon$

Irodalom

Michael Sipser Bevezetés a számításelméletbe . - PWS Publishing, 1997. - ISBN 0-534-94728-X . (A 2.1. szakasz 98-101. oldala: környezetfüggetlen nyelvtanok. 156. oldal.)
John Martin . Bevezetés a nyelvekbe és a számításelméletbe . - McGraw-Hill Education , 2003. - ISBN 0-07-232200-4 . (6.6. szakasz 237-240. oldala: egyszerűsített űrlapok és normál űrlapok.)
John E. Hopcroft és Jeffrey D. Ullman, Bevezetés az automataelméletbe, nyelvekbe és számításba , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X . (Lásd a 4. fejezetet.)
Michael A HarrisonBevezetés a formális nyelvelméletbe (neopr.) . - Addison-Wesley , 1978. - ISBN 978-0201029550 . (103-106. oldal.)