Chomsky normál alak

Kapcsolódó fogalmak: 
környezetfüggetlen nyelvtan (CFG)
Kapcsolódó fogalmak: 
nem záró szimbólum
Kapcsolódó fogalmak: 
záró (vagy terminális) szimbólum
Rövid szöveges bemutatás: 
A Chomsky normál alakot használjuk akkor, ha egy nyelvtant kell létrehoznunk, azonban nem tudjuk, hogy mekkora szabályrendszert kell alkotnunk és nem rendelkezünk semmilyen információval a szabályok méretével kapcsolatban. Minden nyelvtani szabályt át lehet írni ebbe az alakba. Mely: X → Y Z, X → t, ahol X, Y és Z nem záró, míg t záró szimbólum. Némi további strukturálás után n^3 + n*v szabályt kapunk, ahol "n" a nem záró szimbólum, "v" a záró szimbólumok száma. Csak kis nyelvtanok esetén érdemes alkalmazni.