Formalsprog: Forskelle mellem versioner
Content deleted Content added
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 |
||
Linje 1:
'''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.
▲
:<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
* Sproget kan
▲* 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
[[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
# Regulære sprog, der kan genkendes af en [[endelig automat]]. Disse har relation til [[regulære udtryk]].
Line 29 ⟶ 33:
# 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
== 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:Lingvistik]]
[[Kategori:Softwareudvikling]]
|