formelle sprog

Formelle sprog, tegnsystemer, der afdækker den logiske struktur i en teori, og som er resultat af en formalisering. Fx kan en matematisk teori udvikles i et naturligt sprog vha. ord som "hvis — så", "alle", "nogle" osv., men kan ved en formalisering af disse udtryk omdannes til et formelt sprog. Se også logik.

Inden for lingvistikken og datalogien betegner formelle sprog kunstige sprog, hvori alle udtryk er dannet efter undtagelsesfri regler. Det var især lingvisten og filosoffen Noam Chomsky, der gjorde formelle sprog kendt, da han i årene 1956-59 foreslog at tage dem som modeller for naturlige sprog, men de formelle sprog anvendes også i forbindelse med programmer til computere.

Det sæt af regler, der beskriver alle de mulige udtryk på et formelt sprog, kaldes en grammatik, idet grammatikker for almindelige naturlige sprog også kan opfattes som samlinger af regler for, hvordan en sætning kan bygges op. Et sprogs grammatik fortæller, hvordan en sætning opbygges korrekt, men siger ikke noget om, hvorvidt sætningen giver mening.

I naturlige sprog interesserer man sig hovedsagelig for regler til opbygning af sætninger. I formelle sprog derimod siger man, at de grammatiske regler beskriver opbygningen af korrekte ord. Men det er den samme grundtanke, at rent syntaktiske regler specificerer sammensætningen af korrekte udtryk, mens meningen af de dannede udtryk fastlægges gennem sprogets semantik.

I formelle sprog siger man, at ordene er opbygget vha. sprogets egentlige alfabet og et sæt hjælpesymboler til brug i beskrivelsen af reglerne for orddannelse. Det egentlige alfabet kaldes terminalerne, og hjælpesymbolerne kaldes non-terminaler. Blandt non-terminalerne er der et specielt startsymbol. Hver enkelt regel beskriver en måde til lovligt at danne et nyt ord ud fra et allerede dannet ord, i hvilket der optræder hjælpesymboler. Reglerne kaldes produktionsregler. Sprogets syntaktisk korrekte ord er dem, der kan dannes ved at begynde med startsymbolet, anvende produktionsregler et varierende antal gange og ende med et ord, der kun indeholder terminaler.

Et computerprogram skrives i et programmeringssprog, der hyppigt ligner naturlige sprog, fx engelsk. Et programs væsentligste egenskab er imidlertid at give en utvetydig beskrivelse af en lovlig sekvens af operationer, der skal udføres på programmets inddata. Utvetydigheden og lovligheden skal kunne kontrolleres automatisk vha. et computerprogram, der i samme proces omformer beskrivelsen til en form, der umiddelbart kan forstås af computeren. Dette kaldes oversættelse eller kompilering og kræver, at programmet er bygget op efter et meget præcist regelsæt (programmeringssprogets syntaks), som fastlægger, hvilke programmer der er lovlige. Et program er således i sin helhed et ord i det formelle sprog, der bestemmes af programmeringssprogets syntaks.

Når formelle sprog anvendes i forbindelse med computere, ønsker man naturligvis, at grammatikken for programmeringssproget er så simpel som mulig, samtidig med at de resulterende programmer kan blive af stor kompleksitet. Grammatikker klassificeres normalt groft i Chomskyhierarkiet. Her er de enkleste grammatikker de regulære, der også kaldes type 3. Derefter følger de kontekstfri (type 2), de kontekst-sensitive (type 1) og endelig de helt generelle grammatikker (type 0). De regulære grammatikker er for simple til at danne basis for programmeringssprog, men klassen af kontekstfri grammatikker har vist sig at rumme delklasser, der giver en god kombination af udtrykskraft og simpelhed ved programoversættelse. Hver type grammatik giver anledning til en tilsvarende klasse af formelle sprog, således at et sprog fx kaldes kontekstfrit, hvis der kan angives en kontekstfri grammatik for sproget. De fire klasser af sprog kan overraskende nok også karakteriseres ved fire beregningsmodeller for maskiner, der afgør, om et forelagt ord er med i et givet sprog: endelige automater, stakautomater, lineært begrænsede automater og Turingmaskiner. Denne dualitet mellem egenskaber ved et sprogs grammatik og egenskaber ved en automatisk ordgenkender udnyttes intensivt i forbindelse med anvendelserne af formelle sprog. Se også generativ grammatik og sprog.