Formalsprog

Et formalsprog er kendetegnet ved at være en planlagt konstruktion med en bestemt prædikation. Konceptet indgår i lingvistiske og filosofiske terminologier, og anvendes også i datalogi og matematik.

Formalsproget er en mængde af endelige strenge - der typisk nok hovedsageligt består af alfabetiske tegn. Et alfabet er i denne sammenhæng simpelthen en defineret tegnrække der ikke nødvendigvis stemmer overens med et naturligt sprogs alfabet.

Mængden af tegn noteres som ${\displaystyle \Sigma }$ . Man bruger kleene-operatoren til at fremstille en vilkårlig streng ${\displaystyle \Sigma ^{*}}$ . Et formelt sprog L defineres herefter som:

${\displaystyle L\subseteq \Sigma ^{*}}$  eller ${\displaystyle L\in 2^{\Sigma ^{*}}}$ 

Nogle sprog kan formuleres direkte som en mængde af strenge. Et eksempel er:

${\displaystyle L=\lbrace \ s\in \Sigma ^{*}\ |\ {\mbox{length}}(s)<5\ \rbrace \quad ,\ \Sigma =\lbrace {\mbox{X}},{\mbox{Y}}\rbrace }$ 

Her betegner L det sprog der består af X og Y og hvor alle strenge er kortere end 5 tegn. ${\displaystyle \Sigma }$  udtrykkes kun eksplicit hvis det ikke fremgår af sammenhængen.

Genkendelse og accept

Man bruger forskellige beregningsmodeller til at genkende eller acceptere forskellige typer af sprog. Der er følgende muligheder:

• Sproget kan genkendes: For en given streng giver beregningsmodellen svaret Ja eller Nej om den er indeholdt i sproget.
• Sproget kan accepteres: For en given streng giver beregningsmodellen et positivt svar, hvis den er indeholdt i sproget, ellers looper den.^{[bør uddybes]}
• Sproget kan hverken genkendes eller accepteres. Nogle af disse sprog kan beskrives og andre kan ikke.

Det går for at være et datalogisk faktum at den sidste gruppe er den største. Mængden af 'sprog' der ikke kan genkendes og accepteres er overtællelig i modsætning til mængden af sprog der kan accepteres; deres mængde er tællelig. Beregneligheden af enkelte udsagn - også kaldet kompabilitetsteori - er et emne i diskret matematik.

En sprogklasse er en mængde af sprog. En sprogklasse kendetegnes eksempelvis ved at den genkendes af en given prædikerende beregningsmodel. Her er nogle sprogklasser, som hver især er en ægte delmængde af den efterfølgende:

1. Regulære sprog, der kan genkendes af en endelig automat. Disse har relation til regulære udtryk.
2. Kontekstfrie grammatikker, der kan genkendes af en push-down automat.
3. Rekursive sprog, der kan genkendes af en turingmaskine.
4. Rekursive enumerable sprog, der kan accepteres af en turingmaskine.
5. Alle sprog: ${\displaystyle 2^{\Sigma ^{*}}}$ 

Alle sprog der er rekursive kan genkendes. Sprog som ikke er rekursive, men rekursive enumerable kan kun accepteres. Sprog der ikke er rekursive enumerable kan ikke engang accepteres.

• Backus-Naur form (BNF)
• Udvidet Backus-Naur form (EBNF)
• Algebra og logiske operatorer
• Attributgrammatik - formelt sprog med semantisk databehandling

• Garshol, Lars Marius (2008), "BNF and EBNF: What are they and how do they work?", Stuff by Lars M. Garshol, garshol.priv.no, arkiveret fra originalen 11. februar 2010, hentet 5. september 2015
• Thomsen, Klaus (2006). "DYNAMIK PÅ CANTOR MÆNGDEN" (PDF). Personal Web pages at the Department of Mathematics. home.math.au.dk.{{cite web}}: CS1-vedligeholdelse: url-status (link)