Grammatiche Regolari

Una grammatica G e` una quadrupla
<VT,VN,P,S> dove:

VT e` un insieme finito di simboli terminali;
VN e` un insieme finito di simboli non terminali, tale che VT intersezione VN=0;
P e` un sottoinsieme finito di(V* VN V*) X V*, detto insieme delle regole di produzione della grammatica G;
S e` un elemento particolare di VN detto l'assioma.

Sia G=<VT,VN,P,S> una grammatica. Se ogni regola di produzione alfa->beta in P soddisfa le seguenti condizioni:

|alfa|=1 cioe` alfa appartiene aVN;
beta e` nella forma aB oppure a, con B in VN e a in VT, o che e`lambda;

allora G e` una grammatica regolare.