Formaalne grammatika

Formaalseks grammatikaks nimetatakse informaatikas ja keeleteaduses formaalse keele täpset kirjeldust, mis tähendab keele kuuluvate stringide (sõne (informaatika)) määratlemist. Formaalses grammatikas on kaks põhilist kategooriat. Esimene neist, "generatiivsed grammatikad" tegeleb reeglitega kuidas keelde kuuluvaid stringe genereerida. Teine, "analüütilised grammatikad" tegeleb reeglitega kuidas on võimalik stringe analüüsida, et aru saada, kas see kuulub keelde. Lühidalt, analüütiline grammatika kirjeldab kuidas ära tunda stringe mis kuuluvad mingisse hulka, samal ajal kui generatiivne grammatika kirjeldab kuidas kirjutada ainult neid stringe, mis kuuluvad mingisse hulka.
Generatiivsed grammatikad.
Generatiivne grammatika koosneb reeglitest, mille abil konstrueerida stringe. Selleks, et genereerida keelde kuuluvat stringi tuleb alustada grammatika algussümbolist ning seejärel rakendada teisi sobivaid reegleid. Reegleid võib kasutada suvalises järjekorras ja suvaline arv kordi. Reeglite rakendamise tulemusena saadakse string, mis kuulub grammatikaga määratud keelde. Osad grammatikad võimaldavad saada sama stringi mitmel eri viisil reegleid kohaldades, neid grammatikaid nimetatakse "mitmeseks". Grammatikat, mille abil saab kõiki stringe ainult ühtviisi reegleid rakendades genereerida nimetatakse "üheseks".
Näiteks võtame keele, milles on kaks tähte - formula_1 ja formula_2 ning 2 reeglit:
 1. formula_3
 2. formula_4
Alustame formula_5-st mis on "algussümbol". Valides esimese reegli, asendame me formula_5-i formula_7-ga ja saame stringi formula_7. Valides reegli 1 veel üks kord saame stringi formula_9 ja seejärel rakendades reeglit 2 saame stringi formula_10. Lühidalt kokkuvõttes oli tuletuskäik järgmine: formula_11. Grammatikaga määratud keeleks on kõikide nende stringide hulk mida antud reeglite abil on võimalik genereerida: formula_12.
Formaalne definitsioon.
Noam Chomsky pakkus 1950 aastatel välja formaalse grammatika definitsiooni. Grammatika "G" koosneb 4 komponendist:
 formula_16
 Lahtiseletatuna, iga produktsioonireegel seob ühe stringi teisega, vasakul pool peab olema vähemalt üks sümbol mitteterminalide hulgast. Juhul kui paremal pool on tühi string (string, milles ei ole ühtegi sümbolit), siis kasutatakse selle väljanäitamiseks sümbolit epsilon (formula_17).
 formula_20
Tavaliselt viidatakse grammatikale kui nelikule: formula_21. Formaalse grammatika formula_22 poolt määratud "keel" (formula_23) on defineeritud kui kõikide nende stringide hulk, mis koosnevad ainult sümbolitest hulgast formula_14 ja mida on võimalik genereerida alustades algussümbolist formula_5 ja seejärel rakendades produktsioone hulgast formula_15 kuni sõnad koosnevad ainult terminalidest (ei leidu sümboleid mitteterminalide hulgast formula_13).
Näide.
"Nende näidete jaoks on formaalsete keelte spetsifitseerimiseks kasutatud set-builder notationi."
Olgu meil grammatika formula_22, kus formula_29, formula_30, formula_5 on algussümbol ja formula_15 sisaldab järgmisi produktsioonireegleid:
 1. formula_33
 2. formula_34
 3. formula_35
 4. formula_36
Mõned näited keelde formula_23 kuuluvate stringide tuletamisest oleks: 
(Selgitus: loe formula_42 kui ""L" genereerib "R"-i kasutades selleks produktsiooni number "i"" ja genereeritud osa näidatakse iga kord rasvaselt)
See grammatika defineerib keele formula_43, kus formula_44 tähendab "n" arvust formula_1 sümbolitest koosnevat stringi. Seega, see keel sisaldab stringe, milles on võrdne nullist suurem arv formula_1, formula_2 ja formula_48 stinge ning need sümbolid asuvad samas järjekorras.