|
|
Formalni jezici i gramatike - definicija generativne gramatike
Formalni jezik čini odredjeni skup reči u nekom konačnom alfabetu. Reči koje pripadaju nekom formalnom jeziku grade se pomoću odredjenih pravila. Sistem takvih pravila odredjuje formalnu gramatiku. Redosled primene pravila koja se koriste za generisanje neke pravilne reči, predstavljaju izvodjenje te reči. Jezik kao skup previlnih reči , odredjen je alfabetom i pravila. Takav jezik predstavlja formalni sistem tipa asocijativnog računa. Po načinu zadavanja pravilnih reči razlikuju se generativne i prepoznavajuće formalne gramatike. Generativna gramatika omogućuje dobijanje svake pravilne reči uz ukazivanje na njenu strukturu. Prepoznavajuća gramatika omogućuje da se za proizvoljnu reč utvrdi da li je pravilna i ako jeste da se odredi njeno gradjenje.
Generativna gramatika se definiše kao uredjena četvorka G=(A,Vn,δ,P), gde je A={a1,...,am} osnovni terminalni alfabet ; Vn - neterminalni (pomoćni) alfabet ; δ E(pripada) Vn - početni neterminalni simbol ; P={u1 ->'strelica'v1|i=1,2,...,k } - konačan sistem usmerenih zamena u kojima su u1, v1 reči od slova unije terminalnog i neterminalnog alfabeta V=A U Vn.