Formelt sprog

Fra Wikipedia, den frie encyklopædi

Et formelt sprog er i datalogien en mængde af endelige strenge. For at kunne definere et formelt sprog skal man have et alfabet. Et alfabet er en mængde af tegn og kaldes Σ. Man bruger kleene-operatoren til at fremstille en vilkårlig streng Σ ^* . Et formelt sprog L defineres herefter som:

eller

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

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

[redigér] 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 input-streng giver beregningsmodellen svaret Ja eller Nej om den er indeholdt i sproget.
• Sproget kan accepteres: For en given input-streng giver beregningsmodellen et positivt svar, hvis den er indeholdt i sproget, ellers looper den.
• Sproget kan hverken genkendes eller accepteres. Nogle af disse sprog kan beskrives og andre kan ikke.

Det er kendt datalogisk faktum at den sidste gruppe er den største og mængden er overtællelig i modsætning til mængden af sprog der kan accepteres, som er tællelig.

[redigér] Sprogklasser

En sprogklasse er en mængde af sprog. En sprogklasse kendetegnes oftes ved at den genkendes af en given 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:

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. Dette er hvad faget beregnelighed handler om og undersøger i dybden.