Formaali kielioppi

Formaali kielioppi on rakenne, joka kuvaa tarkasti formaalin kielen. Käsitettä käytetään niin tietojenkäsittelytieteessä kuin kielitieteessäkin. Yleensä kielioppi on joukko sääntöjä, joka tuottaa (yleensä äärettömän) joukon äärellisen pituisia merkkijonoja (yleensä äärellisestä) aakkostosta. Formaalin kieliopin nimitys on analogia luonnollisten kielten kieliopeille.
Formaalit kieliopit voidaan jakaa kahteen pääluokkaan: generatiivisiin ja analyyttisiin.
Generatiiviset kieliopit.
Generatiivinen kielioppi koostuu joukosta sääntöjä, joilla merkkijonoja voidaan kirjoittaa uudelleen eli muuttaa toisiksi merkkijonoiksi. Jonon tuottaminen alkaa yksittäisestä lähtösymbolista, johon kieliopin sääntöjä sovelletaan mielivaltaisen monta kertaa. Kieli koostuu kaikista niistä merkkijonoista, jotka voidaan tuottaa tällä tavoin. Jos saman merkkijonon voi tuottaa monella eri tavalla eli useammalla kuin yhdellä produktiojonolla, kieliopin sanotaan olevan moniselitteinen.
Otetaan esimerkkinä kielioppi, jonka aakkosto on {a, b}, lähtösymboli S ja johon sisältyvät seuraavat säännöt:
tai lyhyemmin
 formula_3
Aloitamme lähtösymbolista S ja valitsemme siihen sovellettavan säännön. Jos valitaan sääntö 1, S korvataan merkkijonolla aSb. Jos nyt sovelletaan uudemman kerran sääntöä 1, saadaan tulokseksi aaSbb. Tätä prosessia toistetaan kunnes tuloksena on ainoastaan aakkoston merkeistä a ja b (päätemerkeistä) koostuva merkkijono. Voimme esimerkiksi soveltaa jonoon aaSbb sääntöä 2, jolloin lopullinen merkkijono on aababb. Prosessin voi kirjoittaa lyhyemmin: formula_4. Kieliopin tuottama kieli on niiden merkkijonojen joukko, jotka voidaan tuottaa kieliopista tällä tavoin: {ba, abab, aababb, aaababbb, ...}.
Formaali määritelmä.
Ensimmäisessä Noam Chomskyn ehdottamassa formalisaatiossa generatiivinen kielioppi koostuu seuraavista komponenteista:
 joukon formula_5 merkkijono formula_6 joukon formula_5 merkkijono 
(missä formula_8 on Kleenen tähti ja formula_9 on yhdiste sillä rajoituksella, että produktion vasemman puolen tulee sisältää ainakin yksi välike)
Yleensä tällainen kielioppi esitetään nelikkona (N, Σ P, S). Kieliopin G tunnistamaa kieltä merkitään L(G).
Esimerkki.
Määritellään kielioppi G siten, että N = {S, B}, Σ = {a, b, c}, P koostuu seuraavista produktioista
ja välike S on lähtösymboli. Joitakin esimerkkejä kielen L(G) merkkijonojen tuottamisesta
Kussakin askeleessa korvattu osajono on lihavoitu.
Kielioppi tuottaa kielen formula_17. an tarkoittaa merkkijonoa, jossa on peräkkäin n kappaletta a:ta. Siten kieli koostuu merkkijonoista, joissa on jokin positiivinen määrä merkkejä a, niitä seuraa saman verran merkkejä b ja edelleen sama määrä merkkejä c tässä järjestyksessä.
Chomskyn hierarkia.
Kun Noam Chomsky ensimmäisen kerran formalisoi generatiiviset kieliopit 1950-luvulla, hän jakoi ne neljän luokkaan (ns. Chomskyn hierarkia). Mitä suurempaan luokkaan mennään, sitä rajoittuneempi on kielioppi ja sitä vähemmän formaaleja kieliä kieliopilla voidaan tuottaa. Esimerkkejä Chomskyn luokista ovat yhteydettömät ja säännölliset kieliopit. Vastaavasti näillä kieliopeilla voidaan kuvata yhteydettömät ja säännölliset kielet. Vaikka nämä luokat ovat ilmaisuvoimaltaan paljon rajoittuneempia kuin rajoittamattomat kieliopit, jotka voivat kuvata minkä tahansa Turingin koneen tunnistaman kielen, käytetään pienempiä luokkia useammin koska niille voidaan toteuttaa jäsentäjät tehokkaasti.