Formell grammatikk

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

Formell grammatikk (også kalt kun grammatikk) er i teoretisk informatikk en mengde formasjonsregler som definerer hvilke strenger fra alfabetet til et formelt språk som er 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.