Redigerer Formell grammatikk

'''Formell grammatikk''' (også kalt kun '''grammatikk''') er i teoretisk [[informatikk]] en [[mengde]] [[Formasjonsregel|formasjonsregler]] som definerer hvilke [[Streng (informatikk)|strenger]] fra [[Alfabet (informatikk)|alfabetet]] til et [[formelt språk]] som er [[Syntaks (informatikk)|syntaktisk]] gyldige (det vil si grammatikalske) i dette språket. En grammatikk beskriver kun plasseringa til og manipulasjonen av strengene i språket og ingenting annet. Egenskapene til formelle grammatikker studereres særlig av fagfeltet ''formell språkteori''. Teorien tas i bruk i blant annet [[informatikk]] og [[lingvistikk]].

En formell grammatikk består av en mengde regler for omskriving av strenger, med et bestemt startsymbol. Språket som beskrives, er den mengden strenger som kan genereres ved å starte med startsymbolet og ta i bruk disse reglene, uavhengig av rekkefølga på dem. En grammatikk ses derfor ofte på som en språkgenerator, men den kan også brukes som grunnlag for en gjenkjenner som bestemmer om en gitt streng er grammatikalsk (om den tilhører språket).

[[Noam Chomsky]] delte i 1956 inn formelle grammatikker i ulike typer. Disse typene plasseres i det som er kjent som [[Chomskyhierarkiet]]. Grunnlaget for inndelinga er formasjonsreglenes grad av kompleksitet, og dermed også hvor mange formelle språk de kan beskrive.

==Eksterne lenker==
* [http://cs.haifa.ac.il/~shuly/fg/ Den årlige konferansen i formel grammatikk]
{{Autoritetsdata}}

[[Kategori:Formelle språk|Grammatikk]]