Formalsprog

Fra Wikipedia, den frie encyklopædi
(Omdirigeret fra Formelt sprog)
Gå til: navigation, søg

Formalsprog betegner en abstraktion fra den normale opfattelse af hvad sprog er. 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.

Fastlæggelsen af et formalsprog[redigér | redigér wikikode]

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 \Sigma. Man bruger kleene-operatoren til at fremstille en vilkårlig streng \Sigma^*. Et formelt sprog L defineres herefter som:

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

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

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. \Sigma udtrykkes kun eksplicit hvis det ikke fremgår af sammenhængen.

Genkendelse og accept[redigér | redigér wikikode]

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.

Sprogklasser[redigér | redigér wikikode]

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: 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.

Se også[redigér | redigér wikikode]

Eksterne links[redigér | redigér wikikode]