Forskel mellem versioner af "Formalsprog"

1.159 bytes tilføjet ,  for 5 år siden
syntaks, layout, plus se også, eksterne kilder og kat lingvistik
m (Sechinsic flyttede siden Formelt sprog til Formalsprog: kommunen bruger formelt sprog, matematikeren bruger formalsprog. Artiklen her handler om formalsprog)
(syntaks, layout, plus se også, eksterne kilder og kat lingvistik)
'''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.
Et '''formelt sprog''' er i [[datalogi]]en en mængde af endelige [[Tekststreng|strenge]]. For at kunne definere et formelt sprog skal man have et [[Alfabet (datalogi)|alfabet]]. Et alfabet er en mængde af tegn og kaldes <math>\Sigma</math>. Man bruger [[kleene-operator]]en til at fremstille en vilkårlig streng <math>\Sigma^*</math>. Et formelt sprog ''L'' defineres herefter som:
Konceptet indgår i [[Sprogvidenskab|lingvistiske]] og [[filosofi]]ske terminologier, og anvendes også i [[datalogi]] og [[matematik]].
 
== Fastlæggelsen af et formalsprog ==
Formalsproget er en mængde af endelige [[Tekststreng|strenge]] - der typisk nok hovedsageligt består af [[Alfabet|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.
 
Et '''formelt sprog''' er i [[datalogi]]en en mængde af endelige [[Tekststreng|strenge]]. For at kunne definere et formelt sprog skal man have et [[Alfabet (datalogi)|alfabet]]. Et alfabet er en mængdeMængden af tegn ognoteres kaldessom <math>\Sigma</math>. Man bruger [[kleene-operator]]enoperatoren til at fremstille en vilkårlig streng <math>\Sigma^*</math>. Et formelt sprog ''L'' defineres herefter som:
:<math>L \subseteq \Sigma^*</math> eller <math>L \in 2^{\Sigma^*}</math>
 
Nogle sprog kan formuleres direkte som en mængde af strenge. Et eksempel er:
 
:<math>L = \lbrace\ s \in \Sigma^* \ |\ \mbox{length}(s) < 5 \ \rbrace \quad ,\ \Sigma = \lbrace \mbox{X}, \mbox{Y} \rbrace</math>
 
Her betegner ''L'' det sprog der består af X og Y og hvor alle strenge er kortere end 5 tegn. <math>\Sigma</math> 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 accepteresgenkendes: For en given input-streng giver beregningsmodellen etsvaret positivtJa svar,eller hvisNej om den er indeholdt i sproget, ellers looper den.
 
* Sproget kan genkendesaccepteres: For en given input-streng giver beregningsmodellen svaretet Japositivt ellersvar, Nej omhvis den er indeholdt i sproget, ellers looper den.{{bør uddybes}}
* 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 ergår for at være kendtet datalogisk faktum at den sidste gruppe er den største. Mængden af 'sprog' der ikke kan genkendes og mængdenaccepteres er ''overtællelig'' i modsætning til mængden af sprog der kan accepteres,; deres sommængde er [[Tællelig mængde|tællelig]].
[[Beregnelighed]]en af enkelte udsagn - også kaldet ''kompabilitetsteori'' - er et emne i [[diskret matematik]].
 
== Sprogklasser ==
 
En sprogklasse er en mængde af sprog. En sprogklasse kendetegnes ofteseksempelvis 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:
 
# Regulære sprog, der kan genkendes af en [[endelig automat]]. Disse har relation til [[regulære udtryk]].
# Alle sprog: <math>2^{\Sigma^*}</math>
 
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.
 
== Se også ==
* [[Algebra]] og [[Logisk operator|logiske opratorer]]
 
== Eksterne links ==
* {{Citation
|first = Lars Marius
|last = Garshol
|date = 2008
|title = BNF and EBNF: What are they and how do they work?
|work = Stuff by Lars M. Garshol
|publisher = garshol.priv.no
|url = http://www.garshol.priv.no/download/text/bnf.html
}}
* {{Citation
|first = Klaus
|last = Thomsen
|date = 2006?
|title = DYNAMIK PÅ CANTOR MÆNGDEN
|work = Personal Web pages at the Department of Mathematics
|publisher = home.math.au.dk
|url = http://home.math.au.dk/matkt/RUC.pdf
}}
 
{{autoritetsdata}}
 
 
[[Kategori:Implementation af programmeringssprog]]
[[Kategori:Lingvistik]]
[[Kategori:Softwareudvikling]]
2.754

redigeringer